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

杨利霞

6 c, ^7 D" X, S! D/ @3 z' A数据结构——栈(Stack)与队列(Queue)的手写实例
, t# ~* o# F+ L) v+ J# R, e
[color=rgba(0, 0, 0, 0.74902)]文章目录

' m4 n& p* k9 {. R
• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    9 N' r+ ]+ n" D
• 三、 用数组实现队列
  ; [+ y6 G; V) w0 k/ L4 `  t+ f
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    / v8 i) J' P2 H! j

9 @" N$ u) e! z- a; }7 Y& X- f一、 栈与队列的定义
6 o- o. u( i7 s! t0 ^7 L  w栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。

. K) a: C7 G: b( U% s$ f0 \  u　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。

% K2 f6 a7 _) b/ k! y, s: \; z

二、 用数组实现栈1、栈的接口定义
- T" Q" m( f) S; ?* V/**
* 定义栈的接口
  }" X8 o) d- j' T6 `0 o  D" Z *
6 J( U$ ~& E- a( f; d" Z * @Author zhuhuix
) c7 E( g  k# n3 G0 i6 {; j * @date 2020-05-01
( T  b( ]/ _+ G+ |. T% ?1 Y */
# g3 y& f7 c6 Epublic interface Stack {
5 z" Q$ y  w2 }    /**
     * 入栈
     * @param object 入栈元素
' \: ?( S6 f# \$ k  S5 N! M     */
    void push(Object object);

* ^9 T6 T6 l0 y, ?    /**
' u8 ~; A6 O6 ?     * 出栈
/ L* @- v% r) I% v& i* b     * @return 出栈元素
     */
2 R0 K. f% m4 L: g    Object pop();

    /**
     *  获取元素个数
, o& U* i# `, |. j( L' ?$ L     * @return 元素个数
     */
    int getElementCount();
/ s/ Z" Q! x1 F' r; }
    /**
     * 遍历栈的元素
2 N% K6 Z1 A- \; W! E) n9 c' Q- _     */
8 S  E; c$ d5 E6 d1 F% C' Z$ N* E    void traverse();
3 X0 x$ p- S% O6 b7 z
}
# G) `% [6 T* Y2、栈的接口实现
& @3 T3 D& ^( k' u0 D: n/**
* 栈的接口实现
*
* c6 k* |2 T) @% X. l& `7 l- k * @author zhuhuix
/ Z, f, }, v3 y) S( U, L/ _ * @date 2020-05-01
9 n# W* X4 j3 e0 @1 [+ l" A */
public class StackImpl implements Stack {
       
    protected Object[] element;

) d7 S% r" Q) s# A, C# w    protected int elementCount;
1 e" J2 i+ S  i" A, q
( `! S% B0 ~- k% G  d4 j    private int defaultSize = 16;
$ z) @. Q4 u+ s5 H: E  _
+ P/ A/ p4 `$ u( b  j/ d    private int maxSize;

% @  a" q+ `5 s" V* L    StackImpl() {
: O1 a2 f; g. M$ K+ e  O4 ^8 U        element = new Object[defaultSize];
1 U- b% f8 Z8 k0 Z7 e( y( u5 C        maxSize = defaultSize;
5 ?. Y0 b$ R& G    }

    StackImpl(int size) {
: {/ L$ f$ e0 I2 a7 \5 D        element = new Object[size];
3 D; t2 C9 t- }: ~5 C: x/ C3 v        maxSize = size;
    }
3 i" m6 Y" S, ]- }3 ^6 c
' Y/ t" m. {1 @, B3 q    @Override
; Q# k, y  L) j+ W, _, Q    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
3 ~4 a( Y2 _( t9 [! _  k1 k0 ?" a( q            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
        element[elementCount++] = object;

    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
7 d4 ^- a' C4 R    public Object pop() {
0 ~: e0 N: l7 S2 i( u1 S        if (elementCount == 0) {
& ^* e4 e" ]) S0 O$ N            throw new ArrayIndexOutOfBoundsException("栈中无元素");
& b* m, q- F/ v0 m/ j- ^        }
3 o. |. m6 w/ V5 l" O        Object object = element[--elementCount];
& w1 }9 C) W$ T1 w) Y        element[elementCount] = null;
: S* o6 F$ r. K" d3 o6 u; ]        return object;
7 P: A1 K% y/ b4 k    }
! B; m9 G( U5 R+ J8 ?  W! I/ W' k
8 z& Y9 ^9 a. z    @Override
4 _8 S1 D/ D4 X2 l" w; N    public int getElementCount() {
/ e! f& y# U$ T- i  _        return elementCount;
    }
0 c4 X- A: g( M. p
    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
- v3 \- q/ J+ n3 d/ R        }
9 j9 F' f/ T9 C/ c5 O2 }; X; j        System.out.println();
9 j: t, ^4 P8 a    }
. l5 c4 R3 E7 j0 b& {}
- H% V+ [8 ~% c+ }4 t6 Q% |" ?" t3、栈的测试
public class StackTest {
& \/ P" d4 [9 u    public static void main(String[] args) {
        Stack stack = new StackImpl();

        //第一次入栈:压入1-15
  h! ?8 n* b, V0 W        for (int i = 0; i < 16; i++) {
9 j' @) u5 d8 a; u3 |* E6 a* A            stack.push(i);
- }# R5 O7 Y8 ^2 E% j        }
; g* ]% T* X; W2 D! |        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();

' U6 N3 Z8 J2 V% B        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
1 e! x" G* l) i1 }            stack.push(i);
        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
; |4 n$ }! N' H7 c( W* s% E        stack.traverse();

7 Y, p& `; h$ u# m  O8 [8 P) V/ ~        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
$ b! ?8 D, c; N1 u        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
- W5 Z2 a9 G9 n( S5 m
        //第二次出栈:取出15-0
2 f% T  J# G5 ]8 G: g0 r( a  w: q        for (int i = 0; i < 16; i++) {
            stack.pop();
" V% S- l' r3 k' k6 a5 p. |        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
* y8 t3 B4 l1 f" p- B        stack.traverse();

0 w( Y; {8 g8 a* V6 F        //栈中无元素，出栈报错
        stack.pop();

  I2 ?* [1 C6 Q3 x3 k: E    }
  O5 E4 H5 E. m8 G. b3 d/ |}

6 q4 D* W7 Q6 B& N: e5 R: S) p' c, d


! M+ l  z- ~& Z# O三、 用数组实现队列1、队列的接口定义
- E6 K* L) \; Z1 Y% h  E- d% h/**
* 定义队列的接口
" S/ \' b. R, l$ O- D  L *
* @author zhuhuix
* @date 2020-05-01
*/
: [% j8 X" V$ [% fpublic interface Queue {
9 S. i7 i0 o: @; f
; t- ~, h  T* d8 `8 R" G    /**
     * 获取队列大小
     * @return 队列大小
     */
    int getMaxSize();

    /**
+ N7 V0 z) M/ P  m! H5 R9 W! ]) }8 x     * 入队
9 F* |' _1 `4 L1 H; v- r$ ?8 ]     * @param object 入队元素
% f8 G6 i8 {- z7 u1 }  m5 ~* ?     */
    void push(Object object);
$ P% _3 f0 W# O' O5 H
    /**
     * 出队
     * @return 出栈元素
0 J6 Q0 R6 g0 T4 s2 B  b4 R9 w     */
    Object pull();
6 X. n1 [" P9 ?' }. s7 d/ `: R. `" o
. m" u+ Y6 s  b9 A& ^' C! \+ q  U    /**
+ G6 E! U: a! R     *  获取元素个数
- }( Z- K2 [# R     * @return 元素个数
. A4 c  a( R/ w5 ]     */
    int getElementCount();
: d$ c# `( a, l- x) I& k2 Y
3 M1 O6 g. S+ Y7 E6 x2 i* S    /**
4 q# e& x. P% D5 w2 i# A% u     *  获取队头元素
     * @return 队头元素
# R# ]3 i2 h+ p' ?     */
    Object getFront();
; f8 a) F  ~5 n4 e1 Z
    /**
4 T& k3 [; V: ]" |$ x" @     *  获取队尾元素
     * @return 队尾元素
     */
( X7 m: C8 Z8 Y6 A3 @7 g    Object getRear();
! U" o( E+ I& J+ c3 O' o4 T4 Q
: f. r& D* R  p6 {/ M/ H* J    /**
4 g$ ^4 h; m+ o& j- E     * 遍历队列的元素
3 |' a2 ~+ k7 j$ U/ Y; M     */
- _% M! |1 i. Y0 S: p    void traverse();
}
# D  j9 M6 i2 q& t3 G0 {% n0 g2、队列的接口实现
/**
* 队列的接口实现
5 e8 @9 ~2 x* T/ L/ @# u *
* @author zhuhuix
" E" ^+ e  E4 n9 [4 r * @date 2020-05-01
- T6 X; r  [1 n3 f! B# M( Z* k" u */
7 H- u  |" e$ e: K% opublic class QueueImpl implements Queue {
  y! ?/ X. S- p
9 ~. F  U% m; I) d1 j$ d0 f9 }% [    protected Object[] element;

    protected int elementCount;
  \' S+ c3 A; B& n* l/ i
    //队头
    private int front;

    //队尾
    private int rear;

$ O3 d" `! W! n" |! `: ~    private int defaultSize = 16;

    private int maxSize;

0 ~6 t4 A$ F( }* C$ v    QueueImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
        front = 0;
9 e: }- n+ b% q' t/ s( m9 B        rear = -1;
    }

    QueueImpl(int size) {
        element = new Object[size];
$ S* ?8 p  C! P4 j+ ~( `        maxSize = size;
# {; p: d% g" J  n) n        front = 0;
$ a- G% n# c% T  G' x! I        rear = -1;
# R. [& A2 y2 |0 ]/ y* H    }

# h& K# e' L5 c" b    @Override
) U& D7 k+ m4 r/ B    public int getMaxSize() {
4 ]; |) G1 g# D# `- }7 R        return maxSize;
    }
3 k% Y1 b5 O1 f. t# i
    @Override
2 ]6 Y) L% e$ G$ i    public void push(Object object) {
3 n1 d% b- j% }* ^        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
; a7 j' P5 j- A/ q$ _$ t" `            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
9 p% O3 N9 e2 H/ {" {        }
        element[++rear] = object;
8 S' _  O  O0 K" l% c& Q$ T        if (rear == element.length) {
            rear = -1;
        }
        elementCount++;
    }

    @Override
1 [1 B: D+ n/ `0 g5 b8 g  A* p- P    public Object pull() {
2 M& e# N% t1 g/ j" l        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
        Object object = element[front];
        element[front] = null;
        front++;
5 k) }5 a, ~2 ]" C5 u7 _        elementCount--;
        //队列清空，队头队尾恢复初始值
" X( o2 E# u- S9 j- H4 F6 M" o        if (elementCount == 0) {
            front = 0;
- w3 v9 d9 ]) K: s; v. P7 b% V3 ~            rear = -1;
        }
        return object;
    }
1 Z( J$ }6 I6 c2 S  a* e' @/ E
0 X0 ]! j; I3 i0 L    @Override
& i5 z8 b5 Q  m$ K: t    public int getElementCount() {
3 T6 M' {5 i; m3 e7 T' n& a        return elementCount;
: Y5 w4 M5 I) h/ Q    }
3 w% J9 p: ~6 k. l/ p! {/ h) _; Z
    @Override
    public Object getFront() {
        if (elementCount == 0) {
6 b! J. I# R5 S* \$ w8 B0 z# b8 M            System.out.print("队头无元素");
            return null;
$ o/ ~( D4 L- o8 O        }
        return element[front];
    }

0 S' p6 B: ?  T; m8 H- z+ ?) t6 j& h    @Override
/ C( Y- B! \& R( q    public Object getRear() {
        if (elementCount == 0) {
& o4 @" S+ F6 x, W. S5 m! \            System.out.print("队尾无元素");
  D9 l  G: B$ S' P/ J2 [* \8 v            return null;
        }
        return element[rear];
    }

    @Override
/ E5 ~% F; [2 Y/ t  Y( t: ]+ V$ _    public void traverse() {
        if (elementCount == 0) {
: h& E$ a- w; }            return;
        }
* M5 G) c# j. ~        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
1 y) p! o, H% W# s- ]$ ]% _& p' |        }
- z! F+ N4 H, ?& N2 Y        System.out.println();
    }
7 v5 J0 i/ R, M: E}
& s; Y- K* O3 N  ~

3、队列的测试
public class QueueTest {
$ I* K  ?8 V6 ^/ h    public static void main(String[] args) {
        Queue queue = new QueueImpl();

        //获取队列大小
6 U0 B$ [+ `/ w. R6 b0 R3 s        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
% R! Y- A9 h5 D: c# v" z0 k1 @
        //第一次入队列:压入1-15
- i. x. S0 g* D; E- K, q, g$ g        for (int i = 0; i < 16; i++) {
            queue.push(i);
  K: m! K2 t  ?2 e( ^/ w! r        }
, A$ W7 @9 ?% N1 A- f        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
: o* H2 E& K# w7 {6 \) H5 z: i5 z        queue.traverse();
' T' H4 g8 L' h9 v2 ~% z        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

- U& U3 X7 b) D9 G" q1 z& m" `        //第一次出队:取出0-15
6 t* U6 ~! m' C5 d% R        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
8 Q/ Y1 P3 U, U: v: F, W% Y; K. A  d        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
2 P4 A5 }( o6 w2 }4 [        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
) e  L- F0 _( m; R# F

2 E" y0 M  @: n9 {0 P        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
            queue.push(i);
* S$ A  i: `" Q4 o  j" ~, x        }
/ i5 W3 c; c% g* x        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
  O! T6 d( H$ i( v. m, Y! |        queue.traverse();

- _4 a7 |/ W: d# Y' U! G. M
9 l( H' L! S3 ]: B) T        //第二次出队:取出16-31
8 `; H% e4 X$ a$ z( N        for (int i = 0; i < 16; i++) {
: p$ s8 e, z7 T$ T; Z! b            queue.pull();
5 e# v( w2 v. }' K! k        }
) {  \8 e- Y+ Z$ n2 Q% O" @  A) J        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();

0 c  Q; [4 D0 g1 @6 ^5 ^        //空队列出队报错
        queue.pull();
. ?3 e7 D- F7 H' j) u
" H1 I- @$ d: L+ d5 Z( e9 F' P( e    }
}
$ j5 }) S' c) S% O6 K5 [* A+ E
% h& m' o5 Y; I/ I" e) J! s; B
5 X  a; q7 `: [) ^# R9 u: O4 q" \


* e# R4 {' T* O
$ ]0 J; L+ L  @6 p) @
  x8 ~7 V- |: j
1 }5 l# f% E8 V$ k5 M
) a% I7 M, Z0 l' _) c



7 G- q2 I& ]) ?) V

) K" g5 P- q& Y& H————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
+ r1 Q0 r* b0 k2 B+ ^: Q: a原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
: I1 `  v5 b5 I7 c

  K. ]3 K% j$ n& A9 ]. J