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

杨利霞

数据结构——栈(Stack)与队列(Queue)的手写实例
0 Y$ m0 T1 x6 N7 [8 n% R
[color=rgba(0, 0, 0, 0.74902)]文章目录

& |0 x. S) k2 k
• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    ( C8 k: ~2 N, i0 m$ r1 k- w
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    / J- A& x1 S/ n" s1 K( {

7 P/ j- O% r! W8 M, g8 A
4 x' b- E8 z0 e4 d一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。

( A6 a# r' a) X# @" n3 B4 C* y　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
2 W3 [& ~) ~2 p  d4 X) n


+ e, Z/ O7 q' r. o4 G7 U" @5 r二、 用数组实现栈1、栈的接口定义
3 i% h+ b3 y( h5 j/**
, V* H3 M* Q7 u * 定义栈的接口
$ O" b' p1 @; M% N  T *
* o9 u* m# h" Q4 W: V8 ~# W * @Author zhuhuix
. x  H& A' V+ I * @date 2020-05-01
/ R, [4 s7 _/ T: K" N  G: F */
6 J7 g/ z+ S9 L0 D3 gpublic interface Stack {
    /**
: X0 X) V/ G& l* X     * 入栈
     * @param object 入栈元素
     */
; T+ N% H% b* N  T    void push(Object object);
! n5 N, ]& d( J- B5 c1 C
5 \8 T' G0 K/ L. F" b$ K    /**
# b) h; r( \+ H$ \     * 出栈
     * @return 出栈元素
     */
1 }  Q# v9 n! s: Z& `    Object pop();
6 t1 Z% U0 g7 \/ {: E
    /**
     *  获取元素个数
9 L$ u1 E# J  ^) K     * @return 元素个数
     */
    int getElementCount();

1 P( _! h+ |: y; k$ p' q    /**
; b, Z9 {8 v6 d  \2 Q     * 遍历栈的元素
     */
    void traverse();
# q9 E+ U( Q& @' b! g  F7 H
, O, z' @6 v( J8 g' C3 `}
; j5 J1 g  I7 X9 [! B2、栈的接口实现
7 g) W" N: J0 h* h+ n/**
# T9 r: P( |: ]& [ * 栈的接口实现
4 y$ g! }; E4 ~4 h *
* @author zhuhuix
* @date 2020-05-01
% d- f) v& D' k- i */
public class StackImpl implements Stack {
  i/ i' M3 B' M       
    protected Object[] element;
& r* L) S" T" _! _4 ~
    protected int elementCount;

$ ^6 O# I6 D: [0 W1 d    private int defaultSize = 16;
' b7 P2 @; h4 \) q4 f
    private int maxSize;
) N7 {/ l/ L: V- q- G- M
    StackImpl() {
2 S5 w0 ~4 {5 M  U1 J, p        element = new Object[defaultSize];
! P8 R" p# l6 g3 g        maxSize = defaultSize;
' ]' n6 ?0 e6 A6 ^* t3 x5 N# j+ l; w    }
8 e; V" ]0 A) `9 }5 Q
7 U- \) s& Z1 ]; j2 G    StackImpl(int size) {
( A: i2 N( {- b, e) }        element = new Object[size];
        maxSize = size;
    }

2 Z3 |: V0 S8 C# \, H. [# w    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
$ u) {, r. j( J3 O        }
# W; ^5 l$ C8 g  t7 m" |2 }8 e        element[elementCount++] = object;

' l2 F( {- d4 }* ^$ N4 I    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
- |6 E8 ?+ q6 Q4 R" w) m8 {8 b- n    @Override
    public Object pop() {
- h9 P: I2 O( a        if (elementCount == 0) {
7 H6 b; c. @4 T8 E            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
; q( [3 j" J4 \        element[elementCount] = null;
0 K4 [/ @! y; z5 g9 r& V; M        return object;
- o# {6 X7 u/ [& E% K  Q8 o8 Y. q    }

; g$ N2 {5 h' u1 `0 B  p7 j    @Override
4 f# x. z; x2 Q9 J& `- X( B    public int getElementCount() {
" R* t* P; G9 h/ _* F6 c( z+ V# f        return elementCount;
$ e; ?* d# e7 d) R$ U9 q    }
! I; ?% _$ _9 V2 A: E* o! G9 e  D
    @Override
* ^& J+ Q, M0 n4 x    public void traverse() {
$ D8 g: B: y  X" i, ^        for (int i = 0; i < elementCount; i++) {
# J! W# f# Y8 j$ F8 _  w4 X            System.out.print(element + ",");
        }
6 z1 K4 A/ ^* o5 R$ d        System.out.println();
0 H  U% c  S2 f  R    }
6 L  j% N3 U1 T}
3、栈的测试
& X9 l1 w' Q7 S( D7 m2 P8 G0 Hpublic class StackTest {
6 d! N& y' v& K1 F. M    public static void main(String[] args) {
8 }% V2 E) }' i# W        Stack stack = new StackImpl();
9 W0 z$ _* D/ j4 C2 }, o, `
8 F! W* [! k' R        //第一次入栈:压入1-15
' o8 t3 @, t8 U$ w2 M2 J        for (int i = 0; i < 16; i++) {
            stack.push(i);
3 l+ ]+ Y0 W" ?        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();
! }6 P+ d) `" i" H/ c
        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
% C2 R5 f1 ~1 G( v: }' Z5 G            stack.push(i);
+ o2 P2 k1 h1 _* v1 i7 ~  L9 f" z        }
) T! h* y9 q8 _. T        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
% P: R3 C5 L+ H  o) ?        stack.traverse();
2 k7 `, z$ W) y: u6 x2 _3 A$ O7 a
        //第一次出栈:取出31-16
! W. c, V0 E5 m. ^7 ]3 R  d        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
8 g2 f/ O* b1 A( F0 r* M        stack.traverse();
* ?# r" s5 x& Q! n
        //第二次出栈:取出15-0
  Z' w( m- D$ l+ P1 Y8 c+ H# h        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //栈中无元素，出栈报错
; K  ?: r+ P; T) Y& v) c        stack.pop();

: J. n% N( q* C" n8 N0 e    }
}
# [4 v' G' L5 @) E


$ [% |5 _/ A  D
三、 用数组实现队列1、队列的接口定义
( u5 z& ?1 E- P7 b* u/**
* 定义队列的接口
7 x7 l$ T, H% `. [9 a# f *
* F  x- [& |% G: _, f * @author zhuhuix
* @date 2020-05-01
- Y/ a/ z( A( ^; E- A) U4 v$ } */
public interface Queue {

) L3 v( _9 p5 p% l    /**
     * 获取队列大小
     * @return 队列大小
+ |0 S3 A  {& _6 ~5 N& |! a     */
9 j) _* a& ?  I; H, }    int getMaxSize();

    /**
     * 入队
+ J0 X& @& r% v( A# {     * @param object 入队元素
     */
    void push(Object object);

    /**
     * 出队
     * @return 出栈元素
% i3 `$ Z' Z: W3 C/ z     */
    Object pull();

    /**
     *  获取元素个数
     * @return 元素个数
     */
# I. q4 [0 Q2 |, G* a2 F# f    int getElementCount();

# h& M7 I+ E. Q! Z    /**
     *  获取队头元素
, M- v2 k$ z4 B& ~9 ~     * @return 队头元素
     */
8 Z/ U2 q3 u0 M+ o3 S1 M8 i    Object getFront();

    /**
9 k6 k- Q3 A2 X. D+ c% t# v% w1 Y1 R$ z     *  获取队尾元素
( b0 a3 N" r9 K' H3 |/ [. B5 ]     * @return 队尾元素
     */
    Object getRear();
$ Q7 S5 u( E: B9 t% f0 w
8 C* y1 F4 }, @$ w    /**
& U$ `; K+ m. }3 x. }4 [     * 遍历队列的元素
     */
4 O$ D; p, m8 |' p9 {    void traverse();
1 P+ V4 F; q1 f* L9 c$ ]}
1 c8 Z9 M0 ]7 N# ^; n$ ^; x/ W: U2、队列的接口实现
/**
0 e, @6 q( E# s; U% A1 | * 队列的接口实现
) M4 k7 D, Q9 C; A1 c0 P/ E+ i *
  X# K* ]  `3 X$ Y * @author zhuhuix
* @date 2020-05-01
*/
public class QueueImpl implements Queue {

" _5 v! L  h1 }) \" I+ c6 b    protected Object[] element;
  T% A% }! z0 A: Q& |( v( L( Y, h
3 z8 l+ J$ K  e    protected int elementCount;
. J" n9 G) Q+ G' ?
( q' U% n3 U0 H. @' i3 g9 t0 |7 I2 a    //队头
5 w0 d' c+ P# f9 [: o1 \    private int front;
; e! U* u6 f* G
    //队尾
    private int rear;
) f% \& M4 d9 X( }$ T$ V& I) w
2 m# I3 c# h6 q    private int defaultSize = 16;

7 d" Z/ r5 o/ n: S& S$ M! R    private int maxSize;
; _% A  w0 ~2 D/ @6 ^, r
    QueueImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
. b4 `9 s) @$ k9 x: N9 r        front = 0;
+ S4 u3 E# n, P( ]        rear = -1;
    }

% J1 N, T4 Q4 z& b& U    QueueImpl(int size) {
! Z0 Y# L. A' e        element = new Object[size];
        maxSize = size;
4 c  l" {1 D% f6 I; U. E6 c        front = 0;
' L" T  g- ^; w: K( P! G        rear = -1;
- ]: K0 w. `0 [! X7 P6 y' x    }
0 u; b6 ~5 `; t3 l/ l
1 |) c( c4 U- j+ G) m' h9 v( Z5 u    @Override
+ z  B5 y/ S0 ~& X1 i, {    public int getMaxSize() {
, A& N, o: M) D% K- `        return maxSize;
    }
4 |9 D3 E& Y8 A2 E+ S
' [6 w9 o/ j9 U4 `4 {  N    @Override
( A' |  ?# P& A2 B& Z    public void push(Object object) {
( O0 m, v/ e$ _$ R* B, x  R: S        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
, h" Y  ~2 |' F$ o2 }: X        }
9 V3 ^& w# d, e+ Z& J; Z  \        element[++rear] = object;
        if (rear == element.length) {
! b# H% A) [& a8 v+ }            rear = -1;
( h, q4 j7 h* m! r        }
7 }: [. b( i! i' L: |; x        elementCount++;
    }

    @Override
    public Object pull() {
0 Q7 M2 ^( z% H        if (elementCount == 0) {
2 }+ Z% y7 ^$ w# m2 R            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
        Object object = element[front];
9 S9 |- C: _" O0 T$ H4 k; w        element[front] = null;
        front++;
        elementCount--;
( w' {8 M# G0 A7 [: Q3 f        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
            front = 0;
            rear = -1;
. I! K- o; G9 h  |8 j1 P+ g% M  b/ E        }
! _6 K7 e" Y0 I; `$ O8 j        return object;
    }

    @Override
    public int getElementCount() {
- V! v$ X, l5 i! C% y        return elementCount;
    }
7 a& ^- z0 H  ], O* G) _$ z- e
0 ^+ o9 g' X, D& ~! L' v. @2 L    @Override
. p5 I8 f3 e  T- o4 q) W2 B    public Object getFront() {
9 L- P' }" i* u' h% `6 S. u        if (elementCount == 0) {
8 p3 Q! X! w5 v; i# j& [! H            System.out.print("队头无元素");
# e+ E# a; q4 [1 ~9 p5 R            return null;
, I, k& K1 \" y+ s- _; B5 r        }
7 y2 z9 U, J* N, O! L; }        return element[front];
    }
( X; [  R8 E. k; h
' R/ x1 M+ j; n6 z; `    @Override
' G% u: h; O$ _) A    public Object getRear() {
( Z5 s2 J/ G# z! a+ A' W) [. j" A        if (elementCount == 0) {
1 d  b* t9 {7 a9 [            System.out.print("队尾无元素");
, }0 _8 D$ a0 u$ T5 |( p            return null;
0 Z$ G$ d2 e0 _# r9 L/ ?9 |. [        }
. z* j" j1 Q" G" p& B        return element[rear];
  T: |: z: a6 ^" I) F1 P    }
7 r  B3 {: s3 E. N
    @Override
" n* W6 `6 W$ V* [. ^* _" n( M2 J    public void traverse() {
        if (elementCount == 0) {
            return;
        }
7 \. e! S! a+ d; }3 |        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
  w" e6 p4 I3 X1 B" l. B        }
/ H4 E/ k& V# A- m( s        System.out.println();
    }
}

+ U' y0 V, ?! E; F8 B
4 i8 g! }5 c9 w+ x3、队列的测试
$ }. R0 U! R- x8 Jpublic class QueueTest {
" t' ~& g% j- o5 W    public static void main(String[] args) {
        Queue queue = new QueueImpl();

        //获取队列大小
% a6 }4 l4 Q2 ?9 L/ J        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

3 q, j- x2 ~7 `7 m1 T8 G: h# t        //第一次入队列:压入1-15
" ]$ {2 t/ ?4 ^# h/ V+ I        for (int i = 0; i < 16; i++) {
, b# Y; p  u# @; u8 p" [            queue.push(i);
3 J7 B, L  B3 ^$ j! J4 |        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
1 V- i$ Q0 {* n9 B  u; N, x5 {8 s! U        queue.traverse();
. [; g9 o+ d$ n' B5 h: T  e        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

( A9 r, D% _# `* U; e" R        //第一次出队:取出0-15
: w2 t6 y- ]; W7 T& N# L        for (int i = 0; i < 16; i++) {
0 V' }9 x3 D$ ^& k+ y            queue.pull();
        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
) W8 V' g3 O+ I8 V        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
$ {* {* f5 y: E( }0 m
+ o0 A" P4 i2 l) {# f) H' I/ P" `0 J
/ i( _9 F+ i) m; }  Z        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
- B4 X2 H2 U  p! L            queue.push(i);
# q; K- x& c4 f) c        }
: {9 p/ `: b8 ?0 D        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
! [- G+ ]' I5 L$ z& ~3 S" `2 o        queue.traverse();
* C& O2 @9 U- ^

        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
2 M0 `8 k7 N( y0 L0 Z1 b4 m/ ?        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();

6 C, G- E" g% Y; u7 o        //空队列出队报错
        queue.pull();

2 l0 r& v! i+ X$ i9 Z) j: r1 }    }
}
$ n/ c9 y3 }% A$ E2 g4 Y! x

6 s, J( _' J$ w! r4 O
" t# U3 B% L4 r) C7 q



* G; M" n! ?% F; {


; T2 m$ j6 }  c7 ]& Y# u
' R  ~  @( Y. \$ V& [- c. U

3 N0 V3 y7 u# \+ E
0 `& Z& f3 L) ^: r* P! m: q" |
————————————————
8 k1 V. L/ ]  q4 k  |5 _版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
- N% D: p+ I( h0 Q- c+ V原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785

, j+ W: B/ ?  U% G- g