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

杨利霞

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

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

4 A$ o, a( @' j! f& C. m- j+ X: s' H
• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  2 r( o6 O+ M; t, c
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    9 Z7 U& Q; i  J

一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
6 ?6 X' m  k/ J' Q1 c/ A
3 i4 p* B: V7 u　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
  V7 W9 S! h! G) B  M1 i
2 {% B: y9 B) `8 \% j3 a! ?3 |

二、 用数组实现栈1、栈的接口定义
/**
, G* q+ ~( I0 ?( F0 v: t; g * 定义栈的接口
*
* @Author zhuhuix
8 q- b) |- V# P; \ * @date 2020-05-01
*/
% I% q5 V- U/ ~: L% [/ Mpublic interface Stack {
6 M: F8 F7 W1 Z: G! _    /**
     * 入栈
+ }( a' k9 ]% s3 q1 \5 ]. t     * @param object 入栈元素
     */
5 D1 m6 `* F  M" i    void push(Object object);
/ R" B$ |% g# S
    /**
     * 出栈
  |% i  R& s, m     * @return 出栈元素
7 p/ A/ j' C( a7 X* [% v$ q6 t     */
7 o) H; p9 V  G    Object pop();
7 E) l; Y7 m; U( W7 F0 D& U
    /**
     *  获取元素个数
* e7 C. \( Z: T8 v     * @return 元素个数
0 |1 W8 {6 E3 m  d2 L, K     */
' U, I# e1 h- K+ T    int getElementCount();
& @# W; T* H9 x; @6 ^, k7 @1 Q
    /**
     * 遍历栈的元素
, I7 @; s' @. A* b8 N4 [' C     */
& j% N# m3 O0 Z5 j* c" H6 ]9 n    void traverse();
0 B0 _6 a, J* k' _4 c
* G0 ]- }: S" x% m. [. |}
2、栈的接口实现
% C- D  S) A3 w( o) x/ t* s/**
* 栈的接口实现
# S; D/ E5 m6 E4 @- \, c& O+ H4 b *
* @author zhuhuix
* @date 2020-05-01
5 Z% u- @7 H5 F */
3 i$ c+ ~, |" [: d: a3 bpublic class StackImpl implements Stack {
       
% \# u+ U0 j5 k* \- d    protected Object[] element;

    protected int elementCount;
# Q8 d  v  u; V( q- p
    private int defaultSize = 16;
9 y( C; g$ t9 x, s; w; @; R
    private int maxSize;
$ d' B, Y/ P+ R" @' W' l. @
    StackImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
    }
. c0 z3 v! r' m: `
% Z1 n0 R7 h0 f( V8 Q' h& c! t    StackImpl(int size) {
0 h2 L3 i/ c- P% m( w8 N* r; ~        element = new Object[size];
        maxSize = size;
$ G; U! r# O* C/ O    }

% E+ l4 a5 E% u    @Override
    public void push(Object object) {
) w5 Z7 f) R8 [" F& u# w( R        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
. R1 Y) V2 g! T7 M: F, ]; _            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
, u. q) D0 g6 V- w3 z) @        element[elementCount++] = object;
7 p" t6 L6 }# F% T; |" W
    }
) t5 t, ]' w5 u. B" @        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
( g  Y# h% \2 E" e    public Object pop() {
6 i8 G# g( ?  B! [; d5 P$ P% H        if (elementCount == 0) {
4 ]: F* R7 t2 F! @. i5 C            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
! Q# c2 h+ L' R# \/ Q        Object object = element[--elementCount];
        element[elementCount] = null;
, W7 n. |6 _' J" F4 F        return object;
+ \+ h5 L- w/ D' ^: H8 E8 y    }
# d$ D7 J2 M3 [
4 O7 H6 A$ K+ c1 c    @Override
: O4 |: L  `0 V0 b& P! G8 ?7 B    public int getElementCount() {
: T/ D* s) i( a/ {        return elementCount;
    }
: d9 h; N% F6 v$ S- ?0 w
    @Override
    public void traverse() {
* I- |6 @3 U$ C& \        for (int i = 0; i < elementCount; i++) {
0 ]9 _! G( E5 L% W3 `$ [. e" z; u            System.out.print(element + ",");
: O: o5 m; y/ F3 X        }
" G3 X& s; `% y( m  d        System.out.println();
1 T* m# e3 G; s    }
}
* K8 h: _4 r* e+ J& Z; v3、栈的测试
public class StackTest {
! n* [0 ^' t- F# Z    public static void main(String[] args) {
* v( w  J' Z& q; K3 Z+ m        Stack stack = new StackImpl();
0 T' V0 @& H- Y/ l# q
        //第一次入栈:压入1-15
        for (int i = 0; i < 16; i++) {
            stack.push(i);
8 Z6 z9 ?# o; @, |& ]+ o; O' _3 W        }
3 Y/ N! h! g6 h$ }" m        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
1 [8 H: y# P- B# S2 V1 S( J; n        stack.traverse();

) L$ M. F+ Z$ X# M2 g8 Y* j7 l; e+ g        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
5 _- s" J2 z/ R* R+ x. f& C            stack.push(i);
        }
' H$ r! D9 b8 q; k" I9 S! I- E' ~& l        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
( d; z1 G. Y" g: S        stack.traverse();

        //第一次出栈:取出31-16
4 }' z5 @5 `  V2 y$ z; Z        for (int i = 0; i < 16; i++) {
            stack.pop();
3 ^) F" C* O/ k8 R0 t8 j        }
8 E' ?3 l7 _2 k4 Y: \/ _. I7 {7 E        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

* @$ ]: }. a$ X1 t        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
: L% v& ]! l5 }( Y7 W1 W            stack.pop();
* V4 v8 {% H. Q7 S$ x; s        }
! t! Q" N% L0 L( `        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
! L: Y  _1 \' R' P  `# F
- @! d9 R1 B. U/ `. l0 {        //栈中无元素，出栈报错
* Y6 m4 h- h& J        stack.pop();
7 a9 k7 y* a' K. U2 \  Z- \" t7 v
3 ~  \% o5 f7 [: {5 h    }
0 s3 m# i) N+ w# y; d}
. L2 @" C' l% ~0 ?. {. q1 V0 Z

5 h3 J4 ]- f% M7 @3 ^2 ]% n- ?
* X4 d' O6 R4 y: q0 R# a
三、 用数组实现队列1、队列的接口定义
6 }+ l" K6 L- Q& @" m. ]2 B/**
- ~( v1 B! Y+ ] * 定义队列的接口
) y# I$ J6 D6 ^5 y' I *
* @author zhuhuix
* @date 2020-05-01
. x( L; J0 s! G% B. Q */
) |$ Z# _6 w! l1 mpublic interface Queue {

    /**
% [4 s2 f3 n# M# j; Q+ G     * 获取队列大小
# ^4 [/ i7 j2 i1 k     * @return 队列大小
+ {4 }4 m4 a8 F# u% f     */
  r0 ^5 r; q: j9 X    int getMaxSize();
' o4 c! D# s+ P8 e
4 l5 I- x+ L- T2 D0 P+ ?" H4 N    /**
     * 入队
     * @param object 入队元素
     */
. z8 L1 W; z' q6 m; t3 L3 b    void push(Object object);

. t4 J. z/ w0 G7 D; m5 t: g$ f    /**
- x$ A# X! e" M0 E4 S     * 出队
( Y' o+ J+ o( x* m( _- |& w9 b     * @return 出栈元素
     */
    Object pull();
3 N8 I0 V6 Q- i. m: d" G) O' y+ S
    /**
     *  获取元素个数
     * @return 元素个数
     */
4 A1 O- V# j: W- D    int getElementCount();

. q, i+ [  E& i    /**
% I  [3 X$ [$ y0 B( }, ?     *  获取队头元素
     * @return 队头元素
4 L, K5 D9 S! I4 Y4 `6 f" \# j     */
, N( h; N. Y- k. L( D, U- M    Object getFront();
# {0 p7 l2 A3 g/ l( g5 a9 J) {! ?# A, V
    /**
0 n: U7 V/ T1 S. c: h" a     *  获取队尾元素
# A5 ], @, ?7 C% i+ s* t1 N# i- A     * @return 队尾元素
     */
    Object getRear();

    /**
     * 遍历队列的元素
; |1 ]2 s* e2 @! j3 m$ k     */
    void traverse();
}
2、队列的接口实现
/ M+ b) ?) V9 b% W* G  o, o/**
* 队列的接口实现
5 |8 X% l7 V& B- |& O7 ]4 P" I3 q- \2 K9 c *
0 o1 t, Y' h2 ?# C6 w' m" ^ * @author zhuhuix
3 j( w$ Q7 \# D. V2 ^7 X- x7 f * @date 2020-05-01
6 t6 \+ K; M5 T8 `5 _ */
, |% }( F  T( fpublic class QueueImpl implements Queue {
% C2 ]6 M; P$ Q$ A, ?
+ v5 P0 u+ u% j    protected Object[] element;
7 ^/ H6 [) v8 @" M" r
    protected int elementCount;

    //队头
    private int front;

$ q( v/ Q4 h6 s' N    //队尾
    private int rear;

4 ?# ]9 g- K! S  M& v* I    private int defaultSize = 16;
* H+ q* S) |6 ^4 ~2 S
    private int maxSize;
7 G9 |( A2 @; w8 e5 H
6 T# C- I/ p) }- S    QueueImpl() {
; Z; v, A/ r" ?1 ~+ I! X        element = new Object[defaultSize];
2 N4 q; G' j3 a- S3 b        maxSize = defaultSize;
# |; N4 s" p; U7 g        front = 0;
: C4 I) _: h# c, i1 W4 d8 u& U        rear = -1;
    }

- R" V. P" P  Q7 t2 |& ^. Y# F    QueueImpl(int size) {
6 X  b4 z4 Q' X4 x* O        element = new Object[size];
        maxSize = size;
9 e, }" M  Q2 o5 J        front = 0;
        rear = -1;
    }
7 q" R# u$ B- [+ N. t
6 T3 R! r& h4 _: f    @Override
    public int getMaxSize() {
        return maxSize;
8 I# `6 ~& ^5 u" n: F    }
8 T& Z7 ]/ d) U* C, k& E6 T; f# D
    @Override
; j; D: y/ S: Z6 ^5 m) _    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
' u/ w+ ?( r- ^            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
        element[++rear] = object;
        if (rear == element.length) {
- @: s: T2 B+ L            rear = -1;
        }
        elementCount++;
    }
6 H' k. T) j. ^
    @Override
, A( \; Y4 U1 M8 ?( \: H    public Object pull() {
: ~0 J. _. `' h1 Y# Q/ |9 E        if (elementCount == 0) {
' j5 A0 k  X" q  u* |" N! f7 y            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
        Object object = element[front];
" `" E# u1 {7 Q- U# P        element[front] = null;
1 r+ G! \, P4 G! N& p; V        front++;
        elementCount--;
        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
* n* l8 m8 `% ~5 J7 ~/ N            front = 0;
            rear = -1;
        }
! `& K% P' t" B4 y        return object;
( k" V7 s; a+ m, ~6 Y, q" B' z! v- d    }

0 c. k1 [- h+ E: l& A    @Override
    public int getElementCount() {
0 K$ r) P3 Y/ o$ ^+ d# e        return elementCount;
    }

5 `1 |* L; F$ d9 ?3 H; l2 ]1 p    @Override
2 D: B: e! u6 ?  V( ~  a    public Object getFront() {
& X! H7 {  z% J        if (elementCount == 0) {
            System.out.print("队头无元素");
, ?3 l/ Y) Y. }( {  A- p1 e1 Q. @7 p1 R            return null;
: ?+ k: K/ M- p' Q8 r4 }. \% |4 @; v        }
        return element[front];
    }
0 c0 N2 \, g' D
1 x2 D  ^1 Z4 q3 V    @Override
/ r/ }$ V5 J  ~' Z9 S    public Object getRear() {
        if (elementCount == 0) {
) j6 j9 f0 w2 P: d6 h- a- L            System.out.print("队尾无元素");
            return null;
4 d& D2 l2 l! h$ p7 O8 n        }
4 ~* n" N7 y  R        return element[rear];
. n3 a( t' K7 x0 I7 z1 _# _    }
/ d( K( D* Y% a7 f8 c. W
    @Override
" |+ R1 l) n4 B5 R1 n$ D3 @/ o    public void traverse() {
        if (elementCount == 0) {
1 J8 W; E# m: a7 `! ?- _. @            return;
9 _4 ]7 q( o# ]6 }9 K' z. ~7 f; _2 [        }
  u8 x1 q3 o' a* |* @& c% l        for (int i = front; i <= rear; i++) {
- {# O4 G) H8 ~* ?5 q8 T6 V( }            System.out.print(element + ",");
        }
) x6 j5 Q: F# u& c1 Q0 y        System.out.println();
" R  r4 Q4 \- y( q    }
) @' L% I4 Q$ w. m}


# K/ o  x; E( o9 S4 U1 ]* k0 s- I3、队列的测试
public class QueueTest {
: v. [* y4 b" M7 Q0 `; I    public static void main(String[] args) {
( f) f4 T& g3 h4 h        Queue queue = new QueueImpl();
4 U8 L* g% V8 _( w
        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
4 Z# V; Y+ ]2 x! y7 U) i& }2 e
        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
            queue.push(i);
7 {9 F& U- A& ^1 \4 t        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
6 Z: Z, \# H6 ^1 {; Q8 S        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

7 A3 F0 m  }7 n6 `' e' O; X        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
            queue.pull();
$ a1 o0 L& F" o  `! N        }
; L) Y) R* q3 x9 x+ l* [! q        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
1 P" i: w) K5 j+ H$ c- x2 }        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

" \5 T4 P! N' X7 R
        //第二次入队列:压入16，31
, X9 Y) R/ K& N' p' d: a        for (int i = 16; i < 32; i++) {
3 l9 e# ^/ U$ L, s            queue.push(i);
        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();


% I/ o: f6 O% y4 l        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
& q$ H& \# c( e1 M/ j- t            queue.pull();
        }
! p! b+ T3 h$ K( j" a3 W        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
1 |( e3 R6 E# ^3 q        queue.traverse();
. S9 e6 Y8 L4 v5 v
        //空队列出队报错
        queue.pull();
5 F# Y( ~% b( u4 w
. j) \( n" B% g3 X7 P2 q, f- @    }
}



& c+ k# P0 v2 V/ Q




/ j) \% ~5 A- `' P1 x% p- j5 J
7 m( G' ], h5 E+ R* N
0 M. o" v5 g. L* E- X8 L+ C+ ?  D8 o




- f& y3 t* V) w( S% t5 U9 x————————————————
# y9 u+ Q/ `. I0 O版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% q* W) Q0 z1 z# `原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
( b# e; Z8 c! L% V5 C- F
' \8 l: o0 R; }; r