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

杨利霞

8 M, m. X0 E- G" u' M7 C5 \数据结构——栈(Stack)与队列(Queue)的手写实例

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

% s2 Q) d8 u4 P
• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

一、 栈与队列的定义
% d) k( W- [& o9 ?$ l栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
5 b8 |9 V: Q* n. F, A& ?, v( j
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。


( I0 ~9 C7 P0 F6 N1 Q+ G
二、 用数组实现栈1、栈的接口定义
' _2 V7 e; ^, z3 C: T$ w8 ]/**
* 定义栈的接口
4 X3 k# K: u! M2 F2 I/ S8 \& c+ i4 P *
* @" [- q/ ?' ?4 u- Z6 \3 X * @Author zhuhuix
( b1 _  C0 X9 X) f  q$ _ * @date 2020-05-01
0 z+ |& n' x! k* m: e" X# U */
public interface Stack {
    /**
     * 入栈
+ k- S7 {$ [2 q- _  L     * @param object 入栈元素
     */
    void push(Object object);

    /**
     * 出栈
4 ^5 `/ D/ }! j( a' b$ W: g     * @return 出栈元素
     */
# i5 H' S4 H" s( y  D) C    Object pop();

8 m6 d) Q+ e& c/ j) Q    /**
     *  获取元素个数
     * @return 元素个数
; G- N1 T) z0 v; s0 {& |3 P* n: [: }     */
4 A# b8 R3 [2 K6 u- g+ H( I% r. Z    int getElementCount();
/ T, Z7 _( {3 b, G# U. M: M
, T+ F$ R* l9 B+ ^/ I9 N1 a( u' i    /**
     * 遍历栈的元素
     */
+ N- t' a' T3 u1 e" h    void traverse();
2 N4 F/ n( j* [6 _! r8 l8 E
6 C8 ?: }5 y! i' a2 Y# j}
2、栈的接口实现
) D& K# g3 M5 `' }5 ]/**
* 栈的接口实现
) L# X2 l2 z' n  o: C+ V *
* @author zhuhuix
* @date 2020-05-01
& b! J: N* Y2 `1 m) f& [: @ */
6 C- r3 w( h9 \: Tpublic class StackImpl implements Stack {
; p5 x8 u! F9 p0 q2 {2 i8 l$ c       
    protected Object[] element;
4 v0 k  E1 l: y0 b4 ^& e, Y9 L
/ [7 Z2 F0 d; u+ _- E: N    protected int elementCount;

    private int defaultSize = 16;
7 B  S9 H! p* a  q
    private int maxSize;
; b- \: ^. a2 k4 y1 k
    StackImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
. }7 F* V* O3 z7 c7 t3 `1 k    }
0 k& \  \1 b$ s- g! e3 a
4 Q+ ~. P6 M7 M6 y2 A8 t3 F    StackImpl(int size) {
        element = new Object[size];
' J5 P" R- o% w% a' v; ~/ E        maxSize = size;
    }

$ |: I* H9 B- U- k- u7 s    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
" n2 I# E$ _5 x) P3 X        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
9 x, ~$ U& Q$ ~0 o* p        }
        element[elementCount++] = object;
7 H9 a4 N$ {$ g2 U( b4 b
    }
& j; ]! @6 N0 Q& K, w  r  S        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
    public Object pop() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
; l. Y8 I: {' s( Y! ^        Object object = element[--elementCount];
        element[elementCount] = null;
/ _9 [! U( `0 e5 c( n9 i        return object;
    }
" A$ D9 _' Q0 S
4 ^& H  P' r; y( k1 s    @Override
! x0 ^0 T3 N4 d    public int getElementCount() {
, x: e% `, y$ r/ M" N        return elementCount;
    }
' c  ^  h# ]4 C6 D2 m
    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
        }
5 t% i9 {" V( a# i, i, e        System.out.println();
) }( M  p; ]- E  c/ ~  Q+ w    }
}
) ~% n! n& M1 Z! b7 l! X, t$ }4 ~+ \! u3、栈的测试
& ?$ _" ~4 N( h; [7 ~' }2 K' Qpublic class StackTest {
    public static void main(String[] args) {
8 @% C% U- Y2 B        Stack stack = new StackImpl();
. h/ q% k, I4 r/ G: W: i
- ~/ ^! ~4 q/ u' J% k        //第一次入栈:压入1-15
        for (int i = 0; i < 16; i++) {
            stack.push(i);
        }
/ u' b' ?# |! m/ r" L        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
& Z+ f1 |$ ?* m3 k        stack.traverse();
# a( [; v, a5 [# z3 K- S
3 D$ O5 ?( k* H# Q" K9 `; n  L. A        //第二次入栈:压入16-31
! }8 S0 l6 K4 \        for (int i = 16; i < 32; i++) {
& D& L8 I$ _& R8 W$ ~2 e            stack.push(i);
0 @9 h' W9 p# ^6 o4 x6 K        }
- i: u/ |" c1 ]        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
. m% v, O0 {5 R  `& R
        //第一次出栈:取出31-16
5 d" H- E$ k8 s; g) |        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
8 Q5 y; v& J: K# P7 Z- J0 v- L        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
/ J% F, u0 W: J) m" y3 j8 s6 r        stack.traverse();
  v- H) X) s4 R, ^2 I
6 K) b# M% w  j: d. N        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
) o6 Y& N" Z" j1 O            stack.pop();
# t# k+ j; b  k/ }; m. I. F4 o        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

% ?+ Z# [( c; V$ o        //栈中无元素，出栈报错
. p0 H4 l& P! {, b4 d        stack.pop();
( G% `. y" r: j; h' u# U
    }
}

0 n+ R+ Q/ M- x" q4 a  R9 J
5 e) P4 U8 [. ^5 P

+ ?9 X8 w) a2 _三、 用数组实现队列1、队列的接口定义
/**
9 ^% V% t# ]7 i, q3 V) s * 定义队列的接口
1 U' }+ Z. u3 a( w9 m *
* @author zhuhuix
* @date 2020-05-01
*/
public interface Queue {
2 [+ @% O( k5 E2 M
    /**
: {8 E2 X4 \  z2 [     * 获取队列大小
     * @return 队列大小
) H* N* s8 ^" r& U     */
    int getMaxSize();
: K" G9 ]1 _8 S- `* s) n
7 u; g/ Q+ m5 S" S8 k, J; }    /**
9 _7 C8 n5 e7 y0 J- K- E) D     * 入队
3 }+ b0 U1 F3 m. ^8 n' J0 g1 o     * @param object 入队元素
     */
( l( T! S, h! o    void push(Object object);

    /**
     * 出队
     * @return 出栈元素
  c) y$ r/ P! ~     */
    Object pull();

) ]9 Z; ]2 I" v5 Y4 h3 q6 m: r    /**
/ e# c5 C4 G- t. o, u; i     *  获取元素个数
% T+ ]9 E* F0 ^2 |; @     * @return 元素个数
     */
* R3 S( b: j- d7 N    int getElementCount();
& W0 F3 p: s# \4 |- H( w
" c+ ?4 B1 }. U3 x' p9 L    /**
     *  获取队头元素
3 Q) J. w! m# Q     * @return 队头元素
     */
    Object getFront();
5 e+ @9 n; m; a/ Z  T7 q: \
% S& {0 K. D; M! ?1 \9 O7 O    /**
: f: z, {: H& Z3 L  P/ Q5 P     *  获取队尾元素
: _  h8 q( q# q  F     * @return 队尾元素
8 d. Z# b2 y9 q. T/ l     */
    Object getRear();

3 r" Y, d( H2 _+ t0 y% Y    /**
$ J" ]$ H# ~( @/ A# c: g9 \, A9 D( q2 X     * 遍历队列的元素
     */
    void traverse();
7 H6 \+ E7 |' R: y) C# ^  o' B$ l% L}
1 b' N8 k3 n% u' T8 }2 }2、队列的接口实现
1 R2 \! P) N, c* f% Q/**
+ ]9 K" {0 B1 y8 @: o& M% k+ o9 z * 队列的接口实现
) `" R! Q  z' e- x1 q, d *
* @author zhuhuix
* @date 2020-05-01
1 _) f1 \* b, ^/ N */
3 I+ _2 G% l2 E) j( q7 o3 ^- Zpublic class QueueImpl implements Queue {
5 v' a# n: t/ s- L
    protected Object[] element;
4 ?" s3 r6 H5 o2 O- ?3 z# _* W
3 d* p: }8 h8 O    protected int elementCount;
# f; ]* W! M# q$ B0 F" L
    //队头
0 h& H7 w* M+ K# ]+ A2 Z    private int front;

7 G# M- c2 B$ T; e! N" x) |9 F    //队尾
5 O) |) G3 E* t0 \* I    private int rear;
2 x1 k+ R6 O7 q9 I1 _
    private int defaultSize = 16;
; c5 ^: @1 S3 @" v8 I  x
    private int maxSize;

    QueueImpl() {
3 h, a1 i) \8 v2 p% o7 Q% ^! e' W        element = new Object[defaultSize];
, ?  Z0 M) D8 D& b- m: b. Y        maxSize = defaultSize;
        front = 0;
        rear = -1;
: v& j5 _7 X& a! M4 Y( R    }
3 c3 b; [* Q! w& c$ U
# f- o2 t" ^5 ^% A- `6 |) H) n7 ]" Q    QueueImpl(int size) {
        element = new Object[size];
6 B5 X' H+ _/ ~, c" L( j6 \+ {4 C& v        maxSize = size;
        front = 0;
: k- v# u' z0 q' g+ F" p* R        rear = -1;
    }
) P* N8 N0 h; ~/ Q" T4 {. Z
! O2 W+ Y; R. v' h3 U    @Override
    public int getMaxSize() {
* }( m, d( q- t  s( g4 V7 H: u: K        return maxSize;
( D& X% B! v0 N$ f# X    }

: G  M% g- _, |    @Override
9 Y+ Q7 ]) r& R0 @9 f. T    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
! q" p8 P( l! ~8 a! E6 ?0 W        }
        element[++rear] = object;
        if (rear == element.length) {
! E& d: |! C: l4 i4 d! R            rear = -1;
( d; E' B+ c, j' W( l8 g3 |        }
        elementCount++;
+ A9 l/ `6 A3 G3 B' b; q    }
8 }) x2 X" f( j! i# I
6 v. k2 z% l3 H# R2 z    @Override
  y7 W8 H& j) ]& t' k2 ]1 U    public Object pull() {
2 {+ Q- }) y. \  }& ]        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
        Object object = element[front];
        element[front] = null;
        front++;
- w/ Z0 D- ^% Z# ?# k        elementCount--;
/ \8 V/ y! k& C2 f0 o9 m( Z        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
+ ]  ~2 D7 q' w7 p            front = 0;
            rear = -1;
        }
        return object;
    }

% `7 o  b0 z1 ]# z    @Override
+ @2 a; j. l7 B. N    public int getElementCount() {
        return elementCount;
    }
8 [; ?- P$ j' N% P
    @Override
    public Object getFront() {
5 S2 L6 X: X# ~: I        if (elementCount == 0) {
            System.out.print("队头无元素");
; F+ p: K4 v3 l7 I            return null;
        }
. N. {+ f: ^( P7 c; [$ U+ D        return element[front];
9 P" k$ o- m: U4 u2 Y  ^8 \    }

  {$ y( C5 w; c- y- O( a    @Override
7 }: h1 a: A* W9 h/ e    public Object getRear() {
        if (elementCount == 0) {
            System.out.print("队尾无元素");
            return null;
        }
0 d) O+ [, ?1 v4 K9 |- S1 b        return element[rear];
    }
& g7 {* j9 r& q, f+ d0 O
* J8 e4 g* x# \! i, J  \    @Override
% d9 G- m% f+ H% I0 O9 W# a& F    public void traverse() {
        if (elementCount == 0) {
- `4 o% x' D9 @& {            return;
        }
        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
* j- [/ I: Z/ P) e- g5 {$ i        }
        System.out.println();
5 y' ~- E. d! q7 Y: L    }
0 L% N+ o5 U% }7 m0 u}
  G0 P8 S$ |7 t; g
3 \- [6 V( Y* ~9 @1 I
2 N  C  d! J1 X+ l9 O9 V3、队列的测试
, ]: \1 \' A: k# N: qpublic class QueueTest {
    public static void main(String[] args) {
! G: i+ q9 b0 A        Queue queue = new QueueImpl();
: R, C# i$ p9 E3 d) Q( h
6 y$ l, X5 C  c5 m        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

; j$ U  Q2 d* p( b$ a( I        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
            queue.push(i);
        }
1 B4 A* q& x+ h: J        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
, Q+ a0 A- s9 d) V- l3 }  ]        queue.traverse();
1 C2 O, A1 k2 t7 ?        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
! s) Z0 \: }. b% S! e6 Q
7 }% o+ o& G5 `7 H) w2 \9 z# j        //第一次出队:取出0-15
* l. d7 j0 I1 u% V        for (int i = 0; i < 16; i++) {
: i. T, R; |" k            queue.pull();
        }
# z  c: V- ?+ t! x        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());


3 c' e- i% P) v5 E* a* E* a9 h        //第二次入队列:压入16，31
  P6 r* Y$ n/ \; b2 |        for (int i = 16; i < 32; i++) {
: u: \" Q- i/ p/ |. X            queue.push(i);
( c8 p, W) z+ G1 J* G% D        }
" `$ d0 m5 K/ r. U' I# {7 K        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
& H. q6 i2 E4 u; l! `8 d! A        queue.traverse();


8 ^% ~: N* ]- _5 h3 V7 l3 c        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
. z3 X" @: a1 U            queue.pull();
        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();

        //空队列出队报错
        queue.pull();

; ^$ b) x+ F. S5 ^' F    }
}
4 f1 j* G8 K( i* W% |) [
" W/ n9 U1 {+ r/ @7 m
* H3 R% W, H$ a" y! Z* y

- X$ \, j2 z- v1 m. w2 W/ Y, W, T* M

# F7 L& O- M( D6 v' h+ i






3 e% {: ]) e' `( a' F/ q8 g

————————————————
) f: i( g7 y" F+ i- p版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
7 p: |5 I. [( D* |原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785