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

杨利霞

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

+ j) L9 h( V. A[color=rgba(0, 0, 0, 0.74902)]文章目录

% @1 {- Z6 X2 Z3 R* P
• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    # Z! F" X0 {  [+ s9 G
• 三、 用数组实现队列
  7 O1 M# O' i* x) S% d9 v# a& j, |* j4 I
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

2 \' K7 F& n4 [- _' z/ X( r) j. {0 B一、 栈与队列的定义
$ e" G( l1 b# u+ _' G. |: v栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
# h: y( s+ E% r( r/ f/ `4 O
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
1 K  \2 W- q- r, h


二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
/ U& q4 v4 u! }: U0 m *
( L  y. ?9 I  S: G9 S * @Author zhuhuix
: e6 Q# V9 i$ c. u, S8 [8 f * @date 2020-05-01
*/
0 m3 h/ w& w( I* E7 apublic interface Stack {
! j8 v. Y$ a" B: X) T( h1 k    /**
; S: k  t- j0 i/ e3 ~0 v( ^     * 入栈
     * @param object 入栈元素
     */
9 N) P% V( L) l9 V9 n    void push(Object object);

1 r' \( E& h1 M) L    /**
     * 出栈
- _) T+ n; z3 G     * @return 出栈元素
     */
    Object pop();

) p. z: d* O# }( r9 M    /**
     *  获取元素个数
+ }: Z( Z% J# s- w6 e- w     * @return 元素个数
     */
    int getElementCount();

+ W" `( K3 w/ o: z    /**
" A! e8 v& @6 x     * 遍历栈的元素
     */
    void traverse();
! D% ?0 L$ i7 `# G  Q  f" @
, R0 z% }/ x& k}
2、栈的接口实现
' |+ J( ]1 k+ h0 \5 D/**
) ?% z" F0 m) q * 栈的接口实现
! e8 S# m- Z5 o& U/ Z$ c' C6 h* t *
* @author zhuhuix
* @date 2020-05-01
*/
public class StackImpl implements Stack {
       
    protected Object[] element;

    protected int elementCount;

' P* g! g' r+ G    private int defaultSize = 16;
* v' w9 D. Y* n  c
9 i5 Y3 Q2 R  O    private int maxSize;

    StackImpl() {
: q7 Y7 a5 g' R6 O  }        element = new Object[defaultSize];
1 J3 a6 C6 F3 B- i/ [2 s        maxSize = defaultSize;
8 h; f4 p; M- g: U$ a    }

    StackImpl(int size) {
9 Z7 Q) u8 o/ z& q7 X* v        element = new Object[size];
8 {  V: s  D$ }! M3 h$ }7 u        maxSize = size;
! V+ }: E2 _" S% ?, d: ~: o    }

    @Override
$ U/ N. B$ K& k+ ]& Z    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
% f: c5 m2 M% M* B            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
/ y5 K3 A0 ]9 Q$ ?. i        element[elementCount++] = object;
; ^% |, Q, h8 Z# T1 }- V; U% S
& C2 u6 x. I4 M/ \5 `- h5 Z' D    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
( l8 i: x4 f3 B    @Override
    public Object pop() {
6 b4 V! u3 S" y; i1 |        if (elementCount == 0) {
+ J8 B7 v0 _: ~8 I, r- K- F1 s% o            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
: T1 d8 t% F/ t* b6 n$ `8 }5 u8 }        Object object = element[--elementCount];
/ X# ?' |* I; V) \/ e+ [        element[elementCount] = null;
        return object;
3 \; `3 L& l% q    }
4 x/ _6 Y" H7 t. X. u+ ]. |: h
    @Override
    public int getElementCount() {
+ w) ]. `" Y, Z( {        return elementCount;
1 E# L4 y" ]2 y& I2 D    }
( N, t! J, L4 v, G9 g
7 n- D& p. D1 r    @Override
    public void traverse() {
0 `7 t; t3 V+ w  {        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
' O" G) p9 U; ]+ t: p/ C+ ]        }
        System.out.println();
    }
}
7 S9 k" {% ]) Y: y* \3、栈的测试
- y3 c: }! [+ m# F, Y" G+ ipublic class StackTest {
% c7 V% o: B& m2 z" d% O; L    public static void main(String[] args) {
        Stack stack = new StackImpl();
) N: c8 D8 k# {2 [
        //第一次入栈:压入1-15
        for (int i = 0; i < 16; i++) {
; P% d- C, H8 b            stack.push(i);
        }
$ b5 y- `1 Y9 N$ r, V( f  R9 I- e  \        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
  V* F, b* t( x$ `        stack.traverse();
, m4 i) m& K- @9 @. ]$ I
        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
            stack.push(i);
        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
4 n8 y: a0 A  g2 _        stack.traverse();

        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
5 L2 F( D' z- f4 y( K/ Z7 {            stack.pop();
        }
% l; y7 ]2 o- Q6 O        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
1 `" L* {$ r+ k( S+ h$ F        stack.traverse();
  J  I- e4 F( \7 i2 E  u
        //栈中无元素，出栈报错
0 F5 x" }) o3 G- u4 q% h6 r        stack.pop();

7 y$ n6 N' y7 [. X    }
  E6 f" X- b: j6 j3 C% M. ?}
2 J1 ~& z9 `0 P! B: ^- ^$ v3 n# t! G3 D5 m

5 s% F; {- c$ J* X0 ~3 N, c

; K' w  h/ k3 J  ?5 p三、 用数组实现队列1、队列的接口定义
/**
" V. ~  k0 Q; i4 l5 E0 Y' f * 定义队列的接口
*
" ?3 c- T5 C/ [/ v) K4 n& u * @author zhuhuix
* @date 2020-05-01
0 O% T; G" q. h$ j  E; Z */
public interface Queue {
* i2 b$ G+ R! A3 U+ g/ I) ^5 _# x
    /**
7 M! e5 N! Y$ Y3 F; \     * 获取队列大小
     * @return 队列大小
6 L2 B/ m/ g2 w' T9 y% @$ f     */
" w4 Z: A( x4 |6 R    int getMaxSize();

    /**
     * 入队
# W# ?4 g2 r/ P2 ^3 e( m. ?$ a     * @param object 入队元素
     */
    void push(Object object);
' r* y5 G3 l" r& ~( o
7 j$ ~" c6 {& j8 w( d    /**
     * 出队
; U3 z6 X) _  F) U     * @return 出栈元素
     */
% _2 f: R1 ^4 H: A8 R    Object pull();

7 ~" f. ~9 c. N: E+ C( H2 ~    /**
     *  获取元素个数
     * @return 元素个数
     */
    int getElementCount();
5 R2 V3 U4 R  t
8 }( S6 R4 B4 L    /**
6 t1 C! k  ?$ |* e  Z; j- ~& x     *  获取队头元素
& E. \2 c7 p( C3 b: }     * @return 队头元素
- g0 J+ x3 \% k  Z  N# M! R     */
    Object getFront();
, v# }4 c/ G! y+ d5 t! ?3 m1 T
    /**
     *  获取队尾元素
     * @return 队尾元素
     */
    Object getRear();

* ^, M$ J9 L  ~3 S# j2 E1 b' \    /**
1 z/ o5 e# Z: }1 a8 h     * 遍历队列的元素
     */
    void traverse();
! S! I; a9 k6 [/ a/ g4 @: a}
2、队列的接口实现
- z7 v* d! r+ X( U: Q" a/**
+ S1 }/ B& r7 t- n- F9 ?3 u * 队列的接口实现
. i$ J) {) H4 x5 |1 p: U *
* h4 W7 m  |- |; z+ X) j- i5 H * @author zhuhuix
; a3 [8 W. F% L8 p7 H1 { * @date 2020-05-01
*/
public class QueueImpl implements Queue {
2 \/ B3 y! h  D+ B' b
    protected Object[] element;

    protected int elementCount;

- K: I/ E2 Y8 \' r- j- i' A    //队头
    private int front;
6 d* F9 c8 L: R( _2 l( K
6 p  ~/ G- ?! M2 ]' j    //队尾
    private int rear;
+ S$ ^( J2 h0 o; a2 F% }' k
% y5 f) R- K' e, T    private int defaultSize = 16;
* W: H3 A" O) w
, i0 L  C, s( E. C3 b    private int maxSize;
. B3 ^  s. Q+ }2 G9 q/ A: H# G
    QueueImpl() {
: r- z) \* J4 L8 i8 W/ H        element = new Object[defaultSize];
        maxSize = defaultSize;
3 c1 P0 Q$ `' P        front = 0;
. r5 [" m* i. S& V  _& v+ N! w        rear = -1;
    }
5 C7 `- ^& `$ G! v5 i. h" t; \
    QueueImpl(int size) {
- b/ i+ h( f6 M5 V        element = new Object[size];
        maxSize = size;
; s3 C8 v, `+ w2 f$ r# I3 O        front = 0;
* |4 l+ Z7 o" B" j1 U$ Q! H# _7 j        rear = -1;
    }

    @Override
# O" U( M! P* U    public int getMaxSize() {
( e8 D  g0 \4 F; O2 h; C, F9 S        return maxSize;
    }

' q4 D' l, E& X: g  S2 x4 S2 Q$ a    @Override
2 U5 N# N6 @" z5 C    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
! _8 p1 q% s4 I6 a, |, f8 k: g            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
# k3 b3 p  x+ n1 y        element[++rear] = object;
3 A$ b: l/ Q% F        if (rear == element.length) {
            rear = -1;
7 \% }  p& C$ A% ~0 D; j) m# B: o        }
        elementCount++;
    }

    @Override
5 [2 `+ R* D2 Z. f    public Object pull() {
8 R) r4 ]# P& b" Y6 \* |        if (elementCount == 0) {
+ l0 p" q. E6 l) \' T6 E            throw new ArrayIndexOutOfBoundsException("队列中无元素");
! A% V7 `# n; C        }
) D, Q/ d4 h; e: T( p; [        Object object = element[front];
        element[front] = null;
" G2 [% r1 A, p* h1 h5 g        front++;
        elementCount--;
        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
            front = 0;
            rear = -1;
9 q* \2 ]" E9 P& L7 l        }
        return object;
, a/ c2 f2 o3 U: E    }
2 R4 W! Z3 @% ?0 L3 w9 z1 v; n
! \1 r2 A4 U, m: X! X0 ]4 E    @Override
    public int getElementCount() {
        return elementCount;
& }5 j' o( y8 ^; }' e+ s    }

    @Override
1 W' t4 w( J3 Y! J    public Object getFront() {
1 x" C- C) i+ _% q/ J        if (elementCount == 0) {
0 e% o' ?1 Q9 C: A            System.out.print("队头无元素");
            return null;
8 m4 @6 V2 }2 K0 ~: X* a        }
        return element[front];
) [: ?0 `* O0 J: {5 r    }

9 t/ {+ v, T  T, W    @Override
    public Object getRear() {
        if (elementCount == 0) {
1 c- D9 ^- O& a* U9 l. u8 L+ J            System.out.print("队尾无元素");
            return null;
        }
        return element[rear];
    }
6 X3 L/ g5 B: {! s
7 t  I% D# ]* {. u4 {/ r* X    @Override
' P0 z. ~: S' i- J5 [8 J& a; G    public void traverse() {
        if (elementCount == 0) {
- X- {1 E1 @4 L& n            return;
: d) n7 {# H9 Y$ Y# h  I. t        }
        for (int i = front; i <= rear; i++) {
5 G  D7 H& ?3 S, J            System.out.print(element + ",");
        }
! y1 l6 d! z: A2 B% l% G: B4 @        System.out.println();
    }
9 I2 m& s' g; m}
8 O, p! [( H1 ?! }: G
' w4 \) ]; H  l" M: A  \' m
3、队列的测试
( M6 g% ]5 y. O6 u3 dpublic class QueueTest {
    public static void main(String[] args) {
8 ?' ]" @+ ]& `7 |# t+ ~5 N        Queue queue = new QueueImpl();
" Q: q$ e6 X, j, K$ n. Z" L
. Z/ E8 L4 s) v: I, J        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
' \+ J* A* D( p# J, |. u7 n
        //第一次入队列:压入1-15
  T8 `+ F2 a8 K; G; I        for (int i = 0; i < 16; i++) {
            queue.push(i);
) O" E, Y  ?# U% W6 X9 L/ H( o        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
/ R; v. e4 Y/ ?2 {! Q2 H        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
, P/ \; v  Q# c" ~! w
4 }& t4 ]# y8 N7 N& r% x6 S        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
            queue.pull();
; t: ]3 t. b! X( t7 Y2 g6 D7 J        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
% P' e9 D# B/ \( [: Q' B6 {) V
3 F* k% B# y2 x
        //第二次入队列:压入16，31
6 d6 ?% u4 Q# G. P! }( S        for (int i = 16; i < 32; i++) {
+ P& d, v8 S+ c            queue.push(i);
        }
  H: z( X  M* B+ M  V6 M; y$ J. n4 k        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();

- z7 j- x7 m: ~2 {0 R" A# C3 l
/ b- k* ?1 L) O6 U! |        //第二次出队:取出16-31
+ p' J- r4 Z: w/ m' W  k1 Q        for (int i = 0; i < 16; i++) {
            queue.pull();
  h+ H& M1 Y& J8 [        }
- o% K  y! j& Q0 M3 {        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
$ L: j7 D' z+ e& j$ ]        queue.traverse();
7 I) K" T2 z' K  R% |* N# Y: r
5 Y8 c: w  J" Q( ]+ X        //空队列出队报错
        queue.pull();

    }
1 S& W$ J5 F. ]' L}
+ _0 d' `2 C) J7 E& a
2 w+ r( d8 G0 K/ d6 e& g

3 c) d0 _9 R6 ^( K: \
$ P' `, @6 h. P% S
6 o( J( d% x. J# v1 y$ j
0 A6 H" e" O1 k/ V, F0 A1 X) y


- }" [7 r0 b( w

: z0 q7 y; S5 \( d0 S
: M+ j: _, A& v; b
0 h4 r& t/ Z( U, l4 K

6 M3 E& r) T0 C* i- w) d! U————————————————
  S. H- s+ B1 v2 [  }版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
+ `5 O0 [: ]) {3 w0 e1 O
6 W; o2 I  N( T