数据结构——栈(Stack)与队列(Queue)的手写实例

杨利霞

数据结构——栈(Stack)与队列(Queue)的手写实例

[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  0 v: G3 j8 L2 [$ s
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

6 O6 D4 o* e/ t5 V! _1 O, c
7 ?0 {! l7 k1 C/ I  {& W一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
/ V8 F5 ~' J1 I6 Q" }
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
" \$ @+ W; F, K' f5 Y; ]
2 \, @" X  G4 Z" y* I0 _: s
5 N1 j4 y; N6 p# ~
二、 用数组实现栈1、栈的接口定义
6 b. ~* }4 G) V% F" W/**
* 定义栈的接口
2 _; \  L- @/ Q3 f *
* @Author zhuhuix
* @date 2020-05-01
*/
public interface Stack {
  U5 G) X6 a) }! [9 n9 v8 c    /**
     * 入栈
, \# X& s6 ?9 {* H     * @param object 入栈元素
     */
) j  j# M) e! r7 g" w' f/ r    void push(Object object);

    /**
     * 出栈
; B0 @; F! G7 Q- y( X: @% Q     * @return 出栈元素
     */
    Object pop();

, Q, n0 N! q/ G% A# B$ U    /**
6 {3 C+ U( s3 s4 [: F9 e) g4 G     *  获取元素个数
6 K9 x' x# M  c0 C2 v     * @return 元素个数
0 G$ J" \, Z. A' R' a- Y     */
0 n! s+ k7 i4 E' O( X, ~7 q    int getElementCount();

    /**
     * 遍历栈的元素
     */
    void traverse();
4 a) Q. m; v6 h8 ~& i
}
7 p) [' M- O3 l( O3 |- }7 `2 m2、栈的接口实现
/**
. r% h+ E3 r* W2 u$ ]( t' c4 r  t * 栈的接口实现
*
* @author zhuhuix
' @/ _7 K& ^/ T( H# U, y2 l; F5 G  U * @date 2020-05-01
% i- {* h+ D3 n5 \) P7 @ */
public class StackImpl implements Stack {
, `( \, U1 L, }" B2 K9 P, _       
    protected Object[] element;
, g5 N9 x3 R5 k* i
    protected int elementCount;
3 G) w/ f3 x$ g
- n" q$ @3 c7 ^# |! t    private int defaultSize = 16;
' n$ ~% O/ n" ]  y1 Z6 v) [+ q
# y& J% t$ P0 Y6 O6 I    private int maxSize;
! P8 e$ _5 D3 K; V! J6 U
3 i2 I9 |# [* u    StackImpl() {
        element = new Object[defaultSize];
! ]8 C/ G# w) e! I6 B. S$ z9 S        maxSize = defaultSize;
    }

! A9 w: f2 `% q! z0 ^+ D: x3 Y    StackImpl(int size) {
        element = new Object[size];
" @- z7 x& j2 _/ k& u/ |        maxSize = size;
1 `7 Q( A) j, l; @- {+ H3 |( ^    }

5 ]2 G1 [& ~0 x  D) `    @Override
: D- |: m, x  o9 H$ K$ J, L" j9 M2 N    public void push(Object object) {
2 u% x5 S. ^/ S        //如果元素个数已经达到数组的最大个数，则进行扩容
% J6 u  S3 y; `% ]& W& P        if (elementCount == maxSize) {
- l* L% P9 R3 n' }, Z            element = Arrays.copyOf(element, elementCount + defaultSize);
9 E7 }5 U5 B% F  w' x" i% Q        }
        element[elementCount++] = object;

    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
    public Object pop() {
        if (elementCount == 0) {
5 a1 [/ M4 q) a- K* R: l- i; t            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
- D, y3 j$ t& |8 e9 Q        element[elementCount] = null;
/ t5 k2 d' O4 d1 X) {, m% a$ F3 j9 `# i        return object;
    }

5 Z  g! L( Q" ~6 B( Z/ w+ }    @Override
    public int getElementCount() {
        return elementCount;
! V# s' p6 m- G( M7 V, e8 ?* w3 f    }

& ]! H4 V& e! U3 s4 B2 X8 ?  O1 @. k: W    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
5 \/ C/ |  B; ^& S# Z" j0 d            System.out.print(element + ",");
        }
        System.out.println();
    }
: S; z: X0 r+ G' X}
3、栈的测试
public class StackTest {
; h" z8 N0 ?# j7 P3 d8 K    public static void main(String[] args) {
        Stack stack = new StackImpl();
; H# B# c( X( {0 F6 `' f" L0 I" e/ j
2 l, Z, F. Z2 s/ D        //第一次入栈:压入1-15
: O5 J7 T9 _! {        for (int i = 0; i < 16; i++) {
, o+ n4 s( b; s5 t            stack.push(i);
9 j& U* f+ s1 L- X        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
& N0 J/ w! m; B5 z) M        stack.traverse();

        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
* B% ]. C: t) ~* T            stack.push(i);
! d$ L& x2 j1 ^% p6 m& w1 j        }
4 c# v  _# t( s2 e* [        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
6 t3 G5 B# E) C% ?% C  Z
        //第一次出栈:取出31-16
  F; v& \' C2 K% s' J! h0 s        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //第二次出栈:取出15-0
1 }3 K. t) j8 \6 [% U. d  r) U9 Z        for (int i = 0; i < 16; i++) {
1 a( \' H! `- C6 ^, [8 @- l0 U$ X, D            stack.pop();
        }
/ M* x7 f! t$ m& e        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

, F+ ?( v3 R- A2 o; F8 Z        //栈中无元素，出栈报错
, c. p( b! v) Z2 C4 r        stack.pop();

    }
}
1 }) S* i' \8 F! z5 G
% X. X, S  P8 U& o- A8 I( c

5 ~7 Y6 u) {) |( y  C
# B, Z! S- E, T: ^! h- s三、 用数组实现队列1、队列的接口定义
/**
6 ]- q/ L1 K4 `+ e) w6 k * 定义队列的接口
*
3 B& X. X7 }/ D8 _7 \9 u+ } * @author zhuhuix
$ S8 t6 O1 g' J& B. a1 j; j4 ^ * @date 2020-05-01
7 y+ o1 m6 R  K' ~* N */
  a$ A4 |/ y# a! `9 ?6 X( Kpublic interface Queue {

    /**
     * 获取队列大小
3 ?2 g0 j3 s  C; b; x! t4 K! p     * @return 队列大小
0 V& `( {4 R( m$ p2 m. s, [# Q2 h8 p     */
    int getMaxSize();
( e5 H& m' x( k& q/ K
    /**
     * 入队
- V: w$ |  T' M) ^$ m$ I' A# s     * @param object 入队元素
( {; `/ h, l1 V. v" X- B- [     */
$ ]5 O! A) D4 e. p: ~" C/ h$ v    void push(Object object);

; G6 d4 N3 V; I' w# P    /**
     * 出队
     * @return 出栈元素
+ G% U% H  E" `  l) p     */
    Object pull();

7 s  F  N$ f8 B9 v& R8 a6 V    /**
     *  获取元素个数
) k0 j1 T) t+ I/ V& ?* f     * @return 元素个数
     */
    int getElementCount();
9 P! E4 q, b" v1 c, X
0 P6 F. ]' w, T    /**
/ o! G* G2 @$ |7 X" [/ c; W# I     *  获取队头元素
+ o5 A0 P% F* z- ~- t( ^3 x1 {     * @return 队头元素
     */
( J: D& P6 A1 }. u5 C4 b4 n    Object getFront();
" l4 ^8 ]% f' I; ?" H
    /**
     *  获取队尾元素
( G- c6 N. W1 X, x% W     * @return 队尾元素
     */
    Object getRear();

2 g$ q2 C" i" q3 y+ d    /**
" P% o4 Y; I+ I+ l" l     * 遍历队列的元素
1 c- V6 ]9 m( o+ g; O3 ^6 H     */
    void traverse();
0 r5 U$ n& {3 A: u: ]}
2、队列的接口实现
7 `6 B- U  U1 e0 ?4 c/**
* 队列的接口实现
*
9 U6 z8 B3 j& }7 x% i! q * @author zhuhuix
6 r& |, _* z$ _. ?$ x9 W * @date 2020-05-01
*/
public class QueueImpl implements Queue {
" g* @6 k* o% K  M' H2 C
    protected Object[] element;
) j( B2 c0 Z( n5 |( A- r  @
    protected int elementCount;
; ~6 {6 N# A. T' p. o
! Q/ _/ C) H4 |' q% J5 p    //队头
    private int front;

    //队尾
    private int rear;
, j2 t" k$ `& @$ P9 V* K* [2 ?; n
    private int defaultSize = 16;

6 ?* B7 z7 s& ]% Q, D! B    private int maxSize;

. Q4 J1 v0 U: z3 |$ O    QueueImpl() {
        element = new Object[defaultSize];
3 A1 V! ?; a9 f        maxSize = defaultSize;
        front = 0;
) E$ y9 v% d$ P0 s# j% p2 h/ o        rear = -1;
" S  U  g; U0 ?4 W2 f    }

    QueueImpl(int size) {
        element = new Object[size];
% h* a5 Z5 K# m        maxSize = size;
1 ]9 ?3 P- P' J6 k        front = 0;
        rear = -1;
    }
1 L6 u# N5 a' t
2 B3 l/ _9 l1 b    @Override
/ I$ V+ g* A! J    public int getMaxSize() {
- @3 H) U" \; f        return maxSize;
1 i# \0 a8 B# b7 ?! O: _    }
/ g& P  @: q4 O. U- C
    @Override
    public void push(Object object) {
" r$ b3 \; a  a( N' O        //如果元素个数已经达到数组的最大个数，则进行扩容
. s& @9 X5 R& m& t& z  A$ k# O        if (elementCount == maxSize) {
& W, D. G6 k. \  n, g0 A            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
" J: O/ [# E* H) D        element[++rear] = object;
7 q. y3 Y4 {) @5 `. b7 ^* z        if (rear == element.length) {
            rear = -1;
        }
1 K4 D0 r7 _  J1 |        elementCount++;
2 Z$ `3 P, G7 R1 o3 f% n0 e9 P( H: T1 s    }

4 `/ l1 j5 L: U, Y+ J! h    @Override
5 M* ?3 O( Y0 U0 M    public Object pull() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
! y) G  }0 b- B$ e1 ^6 ^4 g        }
" B1 a( p) o/ z% }7 m! Z        Object object = element[front];
        element[front] = null;
        front++;
/ r' J0 k6 z" |4 {( A, P        elementCount--;
        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
, f7 S# |- v  D' }# H5 p            front = 0;
' b% T& E$ h, {# ^( G4 F            rear = -1;
        }
        return object;
! E7 B4 y4 j. O    }

# r3 j( g7 \( t" F& L- J    @Override
' j0 G7 z. ]3 m& ^) o    public int getElementCount() {
" i! @7 y. x. a; u5 Q7 v  M        return elementCount;
    }
- V) [! S8 Y9 P3 S( u' }
, p3 e4 S3 P1 E  K+ J$ O3 A    @Override
; E  ]! N( k3 F/ V2 [0 E: D    public Object getFront() {
        if (elementCount == 0) {
            System.out.print("队头无元素");
            return null;
! C; D3 ^) }  c' p  L& R/ ^        }
        return element[front];
0 f5 I0 z3 V' Q. ?. o    }
0 F' D& m+ c$ @3 m+ F9 T% i
    @Override
    public Object getRear() {
        if (elementCount == 0) {
            System.out.print("队尾无元素");
            return null;
        }
# L: P8 h* {) ^( U9 H; I        return element[rear];
    }
. ~9 Q0 f% O3 Y, X+ o8 `+ i
# Y! i, K; l* J% n$ p9 W    @Override
& v* j# T* Z8 Y; x    public void traverse() {
        if (elementCount == 0) {
1 S* A0 @# A1 E            return;
$ c& B. a' c8 Z. \3 v        }
        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
: x0 z3 R7 v8 X+ i        }
        System.out.println();
    }
}
, n& v! r3 U+ T8 B. |6 }! S7 ?

3、队列的测试
# B  e' `9 z; o  @/ B3 q, U7 Hpublic class QueueTest {
    public static void main(String[] args) {
; y9 W+ W# g- @        Queue queue = new QueueImpl();

( q' c2 l+ ]: ^/ G. [  }3 i7 y+ V        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
- i# A& f! `6 c/ K) R
        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
            queue.push(i);
        }
; P% }2 p# o5 J' C4 c/ A        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
# p" z' Q0 d7 e4 c! z) D        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
- a2 ^) V  {9 t' Z6 y4 J. Z' e( A) A
7 m% C; e$ B+ {! X; O; n$ C        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
7 j  H: C  G1 y. F2 w        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
# G9 B: e# D1 _1 {
* H8 ~' X: g7 \( |( `4 G) r0 N
3 |  S) d5 A4 p( m* I        //第二次入队列:压入16，31
: v4 L& H! {$ F0 W. j        for (int i = 16; i < 32; i++) {
            queue.push(i);
8 _" {9 r8 M1 _" B3 |7 f7 g        }
4 W2 @& n- h2 c! s6 l* e3 p+ d. B/ N        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
. e! I* b% |$ v* K0 e. V
5 [0 A5 k# ~% T* h; F7 D" }% l0 x
4 n& r6 [+ K1 d  @& m        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
( }; p; ^3 q  @        queue.traverse();
7 S9 U3 _4 B  [6 z8 l
        //空队列出队报错
        queue.pull();

    }
}


/ Z5 B' p0 D* Q5 |
) H$ p5 H$ l* m& {  U; P0 _


3 i& B6 ?7 y% {" a$ x
# {6 _7 u9 k5 a9 C8 z



# k3 y2 a  D9 Y9 x
# }8 d- F7 z+ @$ v- {* Q

3 h. p2 U1 c5 `* K( [7 e
————————————————
, P6 X9 }' m" X% U版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785

; P  C1 o9 A' b. c5 v3 k
  b) a" v; ]  k" X" W7 I