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

杨利霞

数据结构——栈(Stack)与队列(Queue)的手写实例
& b) @6 }% \1 k3 N. W: X  [8 E
/ ~% ?( ^8 Q4 G! E[color=rgba(0, 0, 0, 0.74902)]文章目录

, n1 J2 c: V5 f
• 一、 栈与队列的定义
• 二、 用数组实现栈
  3 Z. V( e* }" _+ b" N
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  $ @  \, N. _0 v* \0 N- E- {8 R
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

6 a( f' k8 j% @一、 栈与队列的定义
6 q8 K& s$ s: {+ _+ P' a, X栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
8 ]1 B/ C- }+ S" t6 M
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。

+ i: i& s3 ]( ], A" I' j0 p- a: h
9 z9 K! }% |! }+ h. X& _: l+ M
二、 用数组实现栈1、栈的接口定义
/**
0 g6 c8 j) l& E/ U' m: F" E! f * 定义栈的接口
*
2 [9 ]5 Y0 Y+ i, e * @Author zhuhuix
$ N8 C9 v" j/ R, r$ v * @date 2020-05-01
*/
# S3 P' S3 Z. H' }$ t3 Rpublic interface Stack {
    /**
6 @, I3 }8 y% ?6 _$ I     * 入栈
     * @param object 入栈元素
     */
' l( r8 x$ R% W& V4 s/ i+ F8 F6 I    void push(Object object);
) N% r! K2 J+ c3 z
, z- ?8 W0 F5 g& ]* t; {& _, T" Q. e    /**
     * 出栈
     * @return 出栈元素
     */
    Object pop();

    /**
     *  获取元素个数
     * @return 元素个数
  l' P0 ?) n# w, b     */
    int getElementCount();

    /**
     * 遍历栈的元素
% {- J4 |9 k/ u8 c9 a* O- l     */
    void traverse();
; ~5 q' c6 N4 D. v) w9 V' c6 t
, q, @* x7 b3 P* V4 W}
2、栈的接口实现
6 O- p) L0 t; q4 y5 U/**
* 栈的接口实现
*
* @author zhuhuix
, j0 p6 {. _0 N * @date 2020-05-01
! P- I4 c" n! z6 R9 X, k' q */
public class StackImpl implements Stack {
       
9 M/ o' G3 U/ ]- \7 }7 ^    protected Object[] element;
1 D$ d" R) t) P8 h9 Z/ n
    protected int elementCount;
1 V8 S, j; y$ D( Z+ W
    private int defaultSize = 16;
2 U3 N% N6 \& Y3 _
( [) Q2 I" P  I/ }    private int maxSize;

    StackImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
    }
7 c6 f3 K: t$ b- d1 S! T
    StackImpl(int size) {
* E8 q  X/ c$ K* ~        element = new Object[size];
5 k- u3 m# {1 @( @8 S' @        maxSize = size;
    }

    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
+ a2 U, @6 R) {9 K) I            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
        element[elementCount++] = object;

    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
3 i5 |# Q8 A# e: E    @Override
    public Object pop() {
( O* ~8 V: p/ f3 R' i2 P1 q        if (elementCount == 0) {
3 t- C. O  i5 B9 o. v            throw new ArrayIndexOutOfBoundsException("栈中无元素");
" D5 h6 ]( T7 m/ {        }
        Object object = element[--elementCount];
        element[elementCount] = null;
; `9 r% I$ S4 m  z8 I5 j. a+ ?        return object;
4 ?) r/ g' ?1 `3 K1 h7 |0 s" y    }

    @Override
    public int getElementCount() {
        return elementCount;
    }

6 u1 B5 o8 E: t; [# }# m6 S    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
3 V! M+ F1 x% [6 p            System.out.print(element + ",");
* j9 f1 j' i  T6 S2 P; }        }
        System.out.println();
2 Y) p2 U  D) X' M% k    }
0 ~7 x0 Y; ~  ^! P}
" @  N! I/ U5 J. F8 W% a; y3、栈的测试
% I3 ^% |& |% Vpublic class StackTest {
    public static void main(String[] args) {
6 J* C1 K# K- ^% x' z7 T4 B2 N        Stack stack = new StackImpl();

4 r) d9 L" {1 E3 Q! S; ?0 E        //第一次入栈:压入1-15
' v- v4 x. C! @- S( I5 ?        for (int i = 0; i < 16; i++) {
% t6 O" G4 b: ~. F7 c2 {* E) K            stack.push(i);
  b) w( F( c) M" [        }
, u; J0 D: o1 y" ?        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();
: B9 z% E8 J" J' J. Z; S
        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
            stack.push(i);
2 i9 h; i/ K: ~$ F8 D$ ]        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
- I$ _* E0 S9 R/ K% f6 v# u1 ?        stack.traverse();

7 }# o4 d5 r; \/ S        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
5 S) D; ], }* h, f& j' m2 E            stack.pop();
        }
$ ]0 W  h% k) s( C' ?$ C. A        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
2 {; P3 Q) A$ q1 C        stack.traverse();
6 ^: d7 B' Y# F; ]9 O% i; u
3 D. D0 _- p9 }        //第二次出栈:取出15-0
& g+ l! w, _/ |$ L        for (int i = 0; i < 16; i++) {
$ K& X# O' \/ s$ N, Y1 o8 |            stack.pop();
        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
6 s; D0 c; K% F
' R% @4 }. K# Q. s  s' J        //栈中无元素，出栈报错
9 w, \$ e/ O: A, m9 D& e. y8 t        stack.pop();
- p! u/ _3 w6 U" @7 m( ?/ T1 f( G
    }
}

( M* n: o* |3 n9 Y- B6 a


三、 用数组实现队列1、队列的接口定义
/**
* 定义队列的接口
*
* @author zhuhuix
* @date 2020-05-01
8 \( m6 x( b. h5 N% F */
" Z) K! b9 {  ^" S, p1 t$ m/ Upublic interface Queue {
: Z$ l0 M5 p5 H' {$ D5 n. S
    /**
  h! L8 ^8 J5 d4 v/ A3 {' D! _     * 获取队列大小
+ O! w% k7 L3 O     * @return 队列大小
" a7 c2 ~5 z" o, F     */
    int getMaxSize();
) y& ^) D9 H/ a! X; t- N" [
+ f% i) G/ p2 i5 l6 L    /**
) W  L( ]( T$ m4 W     * 入队
     * @param object 入队元素
     */
    void push(Object object);

2 l2 S; e3 }7 B& T7 L    /**
     * 出队
     * @return 出栈元素
4 \+ o" X) ^' q. X2 \) A4 C. }     */
    Object pull();

) m1 Q: i, l/ A2 T/ I8 z    /**
     *  获取元素个数
     * @return 元素个数
     */
0 W% b- H1 N( V    int getElementCount();

2 q6 T; t7 {/ g" m. D    /**
/ m# y; u6 Y' J  e. V- {" ]     *  获取队头元素
+ }( v. @9 P6 v" G& V6 a2 p" e+ j     * @return 队头元素
     */
    Object getFront();

4 k- }6 S" l# E( T2 a" \    /**
     *  获取队尾元素
) v! L2 s* G$ |2 r* k6 W& p6 i     * @return 队尾元素
     */
! L% m# B( d$ g* |% ^1 C2 J0 {    Object getRear();

6 L  e& ~+ N7 g, v5 e- g/ P& K, A# N: }    /**
4 Z7 P7 {, f/ T0 Y) q0 g. h     * 遍历队列的元素
# Y  |) L3 b4 M0 _3 R+ c6 p0 ^     */
4 ]1 O7 _+ t. z+ b, q    void traverse();
}
2、队列的接口实现
" B1 i+ B1 m. _: h/**
* 队列的接口实现
% I! n* O: P$ ^+ Y# d1 q *
7 Y3 G, o6 d4 u# C  U* N * @author zhuhuix
" K! h& o8 s  x% ~& H) T * @date 2020-05-01
*/
$ Y6 n' P. W: `2 ~1 Gpublic class QueueImpl implements Queue {

+ a6 v5 }; |7 T+ I6 G+ D    protected Object[] element;
* J$ o& r7 U2 u, B
7 E1 Y1 w$ T, |, s  U    protected int elementCount;

: q" S0 x3 f0 a+ E$ H" ~    //队头
1 z) Z* a: X8 K) B# Y! U    private int front;

  s! i+ `( p5 k4 F1 M    //队尾
. K0 h" v9 F6 f. v    private int rear;

    private int defaultSize = 16;

    private int maxSize;
) r# ?2 G+ D. p" m7 s% H- C
# Z  `; K8 i0 n/ m0 R    QueueImpl() {
- J9 `$ e% }' z" g( Z- E* _        element = new Object[defaultSize];
        maxSize = defaultSize;
        front = 0;
) q" |7 B! @- J6 {4 F2 z+ F: r        rear = -1;
; n- X- ^4 K3 n# i9 G7 C    }
: k0 w1 ]% f( G) @) V
4 F& d6 V, F1 X7 H    QueueImpl(int size) {
! l- A0 w4 Z9 d- t        element = new Object[size];
        maxSize = size;
& V( B3 k6 f. i3 A/ Z! G& M        front = 0;
        rear = -1;
    }
6 _0 z" B/ ~+ e+ i& E" k
    @Override
! m; B$ h# o8 ]4 F3 E8 Y% f    public int getMaxSize() {
        return maxSize;
    }
4 i# _$ }; d# T2 F& k  ?7 q" k
    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
' e/ Y3 F( i  N; n0 O" q            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
        element[++rear] = object;
        if (rear == element.length) {
            rear = -1;
; H4 W5 p: E9 ^        }
        elementCount++;
    }

# f9 r. c& y2 @4 S& b  v    @Override
5 s3 ~* o. l7 I    public Object pull() {
        if (elementCount == 0) {
3 n& }2 S5 W; c1 M( ~4 V            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
        Object object = element[front];
& l$ u' [" t. T; [; k/ t        element[front] = null;
        front++;
        elementCount--;
        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
            front = 0;
" r% p( u/ n& ^! x+ G  f            rear = -1;
7 |" d* c7 x7 g" c( `. u        }
        return object;
    }
! W9 i# ]2 X4 i8 B( y9 k
3 ]5 |8 L, S1 ^7 F5 z    @Override
    public int getElementCount() {
( E7 z# N1 h' C2 J        return elementCount;
) [& T6 a/ [- P* B/ K# c    }
) I! L& q1 s2 S
+ k- S3 c2 U. E; I    @Override
; T; j$ ~; ^$ O# P" n: k3 m    public Object getFront() {
" Y! r2 |  \8 e) o        if (elementCount == 0) {
            System.out.print("队头无元素");
3 W- j' y( _/ [  ]2 _0 [2 N1 N            return null;
! |$ }' M( O1 q( }        }
        return element[front];
    }

- D8 b3 k# v0 b3 \    @Override
8 S0 u/ m3 \# v0 F5 A4 Q# p0 ^- \    public Object getRear() {
        if (elementCount == 0) {
8 M5 j3 J# v1 u. G6 C            System.out.print("队尾无元素");
            return null;
, d1 i6 u' W0 g8 A: q( C# w        }
        return element[rear];
$ F% h0 L- s: c' J    }
# X1 G, d: i: R* t2 ]; ]9 Y
% W8 [2 _3 l; _* H2 n7 ^. ?    @Override
2 m& V, i2 B% ^1 H5 U    public void traverse() {
% x, b: J, R1 C! L        if (elementCount == 0) {
            return;
        }
        for (int i = front; i <= rear; i++) {
7 Q  s9 n/ N: `) H3 _$ D8 M4 }            System.out.print(element + ",");
        }
1 H( x) G: M0 Q+ G/ k1 }0 j        System.out.println();
# T) g( {: Q+ @% Q  y    }
}
" ]7 h1 V( X- h# Y1 ~* t: N
' U& [, M" ~- Q/ E8 v) c1 r
3、队列的测试
: m& Q  a% u3 d+ A9 A5 M$ ^public class QueueTest {
    public static void main(String[] args) {
4 U5 ?: X3 E/ f; @1 p9 U/ K8 S. `( N        Queue queue = new QueueImpl();
7 R7 N; v% l4 H+ V. W; k
/ R/ X, N; Y# `( u. _        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
            queue.push(i);
$ }. p: `; }, S( T1 Y. Q        }
5 s" @0 l! l+ T. O4 `        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
6 A/ p' K+ [  z        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

- k9 ^1 B/ F# ~: W' R& u        //第一次出队:取出0-15
# U( S8 g- o% N4 s  G( Y        for (int i = 0; i < 16; i++) {
8 I/ g2 _3 c) v, V            queue.pull();
        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
& R7 v2 [: ]6 O! {        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
( f0 F( |9 s9 k" [& {6 r  ~+ L
. G+ _: o9 G% C( m" a" C" b
* V5 t/ N# l( U4 a' g        //第二次入队列:压入16，31
' t' U# \8 t+ m5 g& G        for (int i = 16; i < 32; i++) {
            queue.push(i);
: t  J8 e" ~: Z& N0 T        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
2 F; D* |5 E- Z3 J9 `* @

  Y+ h) b; [1 P# w  |$ f        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
- u* }" d3 B+ j6 R5 T1 A7 W        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();

: e* }% d2 [: ?- |6 o  [        //空队列出队报错
        queue.pull();

    }
}
  T; _& s1 f) w. f  w, I2 d
: \* A$ I  @+ A8 u


! K2 I- @: E. F2 t! l$ t


- Z% Z7 Q' I+ d# s& q  \5 `

( ?7 v1 Q5 w) w
" ^% ], Z: s" E" x' T5 `, }+ ~
; C' ], ~! a0 |
% Y/ T* U) h  }3 ~
8 ^' {& E" L+ |+ y# A
/ I, V. O; `# `- K8 Q& Y. r
  f" z( _, ~0 p( r$ u————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785


3 }8 s6 T- x( o$ F' g; C( {! A; L