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

杨利霞

& Q" ]- r+ `7 i数据结构——栈(Stack)与队列(Queue)的手写实例

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

• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

一、 栈与队列的定义
9 R) F" N6 B# O" Z& N+ P# V( }栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。

　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。


, l- M4 b) ~4 F8 G; N, P/ K3 }
: d1 U+ H3 m7 ^# }: C- R二、 用数组实现栈1、栈的接口定义
% M9 ]; ~  {2 Q& ]% V# z# B* Y/ G/**
* 定义栈的接口
*
* @Author zhuhuix
0 R! e# A9 j' X6 T$ H: H * @date 2020-05-01
*/
public interface Stack {
" B; N, _: A0 e5 J    /**
     * 入栈
. ~$ C, ~- U) F0 f+ H) Z* U# b     * @param object 入栈元素
     */
5 k7 j! o  X, X; S9 h    void push(Object object);

    /**
' I) U0 \# V1 K* d     * 出栈
     * @return 出栈元素
     */
/ R0 t* j- ~. m/ c. J    Object pop();
. t! {6 g- X, j4 w6 {: P0 w9 J8 C% P
# _+ i; ]% B9 j# E: Z5 m: G9 i    /**
0 I" P6 j) j9 @, F     *  获取元素个数
     * @return 元素个数
# g# U* w! @; ]     */
    int getElementCount();
- F) v& c/ K- p: D/ Y3 z( i
+ o7 ~" {4 u+ [# M6 q0 L0 z    /**
4 w& j  v  n( ]9 w     * 遍历栈的元素
     */
% [) o6 m0 T9 O; u% X3 V    void traverse();
7 `7 F2 C% z/ k: |2 l6 i, A
, ]9 U, z) F5 \& _% ]}
% }% T4 a* y# H# m2、栈的接口实现
; n+ I  p$ p4 @, j/**
0 k6 M3 `6 I& R" P+ `/ d$ P9 } * 栈的接口实现
' l5 R% I  F' m% ^9 @: K *
  l7 \; J7 Y( S' L0 o$ w3 ~ * @author zhuhuix
* @date 2020-05-01
+ s. c% I1 _5 S" {$ v */
" u# Z7 d. K. ?9 F' P3 Upublic class StackImpl implements Stack {
       
( ?, q! z. \6 H( D4 k$ z) N; y    protected Object[] element;
$ r: ^! {. E" K* h
5 h/ G7 N0 m9 X0 L4 t: b    protected int elementCount;
/ X- l5 [( r1 O/ z$ n+ M
    private int defaultSize = 16;

# O5 P! i, W2 r2 C    private int maxSize;

( a; M  I3 C+ I1 J    StackImpl() {
; i# _  r, ~+ _) x9 J! p0 g: t% P        element = new Object[defaultSize];
& N2 s5 J- t) _; c, }5 q. P        maxSize = defaultSize;
    }
8 m" c! D8 \4 W8 J! H8 j
0 s& g: c/ D  s0 |: ?; U0 |    StackImpl(int size) {
4 H3 O/ \% {* N" `- F6 m0 l" m9 j        element = new Object[size];
6 W. W5 E/ P$ O9 f        maxSize = size;
    }
) R# b( |6 B4 p) K9 z! C
    @Override
0 \2 A: o6 f  Y8 g% a& ]9 ^    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
, e! V, t2 I8 d7 p  m+ v        element[elementCount++] = object;

* Z: B) ?7 R2 Y' V    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
    public Object pop() {
        if (elementCount == 0) {
( D5 ~% ?8 T% ^$ m& }  l            throw new ArrayIndexOutOfBoundsException("栈中无元素");
% `& Y. @& i4 T' R5 i5 W% ^  m4 |        }
  J% U' r/ k. U        Object object = element[--elementCount];
        element[elementCount] = null;
        return object;
9 q4 u6 I8 @1 ~    }
, W+ `. L# `% K9 q! @& b
    @Override
: h8 R: t" k2 ^; j3 Z4 t9 _    public int getElementCount() {
* e2 s, l; V; `; L( V        return elementCount;
    }

, C# y0 n& {% `$ k3 a5 Q6 I    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
  h/ n* ?1 G. [+ ~            System.out.print(element + ",");
        }
: g( T7 M1 L- b$ c8 g7 W0 n        System.out.println();
! L1 h! }  L# q/ N4 G7 R3 w7 A    }
& ~# X% a/ z& C8 ?2 |* d}
) z" R" R: Q* M6 P3、栈的测试
" H/ D! K/ W& ?+ epublic class StackTest {
2 |. X5 B9 a* ~0 v: Y/ g' s$ [7 ^    public static void main(String[] args) {
: o9 L; Z6 e; _# S        Stack stack = new StackImpl();

' a, {: e+ W1 l, \        //第一次入栈:压入1-15
+ B! B+ A% v# R  b7 p1 T" L4 S) G        for (int i = 0; i < 16; i++) {
            stack.push(i);
        }
. k  c! Q7 n4 S$ z( l. B$ R        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();
* r7 X# E2 f7 A# R' G  j8 T; {0 [
        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
+ M1 v/ q( ^  X+ m* P            stack.push(i);
        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
% {9 v2 l0 C. H
        //第一次出栈:取出31-16
+ Z) H. ^# _8 M  n* p! P4 v4 |8 b        for (int i = 0; i < 16; i++) {
. r" j) d. G, U: S0 W            stack.pop();
        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

" f2 o/ t. Z5 X& f' t        //第二次出栈:取出15-0
7 q* a6 J4 v* O        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
* p5 _7 ]# l1 W) `9 G- W        stack.traverse();

        //栈中无元素，出栈报错
        stack.pop();

    }
( Y4 W( O5 Q3 Z7 R}
) D& z2 |$ t8 k: W! B$ o
% R$ T/ K& Q5 f* u. K/ \% n


三、 用数组实现队列1、队列的接口定义
/**
8 F( Q& Q" a5 `4 q5 _8 w# Q# `4 t8 Y * 定义队列的接口
*
* @author zhuhuix
* @date 2020-05-01
*/
public interface Queue {

% J' I  E  P! l1 G    /**
8 o& I. a& |( I3 k9 ^: ^     * 获取队列大小
     * @return 队列大小
: x" [3 t5 Y  R: S6 `; v0 B     */
    int getMaxSize();
3 S- h- r8 i# j) m
    /**
     * 入队
     * @param object 入队元素
     */
5 u2 W% ?) g) Q3 r    void push(Object object);

    /**
     * 出队
     * @return 出栈元素
6 m  z7 G& O! T+ A4 f1 p% y9 x     */
    Object pull();
! o4 M. Q: Z/ U" R7 G! d( U
  M( h$ P) h8 g* S4 a    /**
     *  获取元素个数
     * @return 元素个数
     */
    int getElementCount();

    /**
     *  获取队头元素
. `% x. l! f; v0 D# L8 G     * @return 队头元素
; G9 p6 d3 a, M0 C2 {9 o& X     */
    Object getFront();

: O. W2 b7 S/ v    /**
     *  获取队尾元素
     * @return 队尾元素
+ `: v3 N$ u# [& d+ e2 l     */
/ S  a7 e: ^' E. V! @    Object getRear();

$ q& [' W: i9 I9 u% ^7 a( o    /**
     * 遍历队列的元素
  d% K5 o. {% u* E4 U4 W     */
    void traverse();
8 p. W3 K4 ~3 m}
2、队列的接口实现
/**
* 队列的接口实现
*
9 A- M3 ]$ l- D0 [5 t * @author zhuhuix
* @date 2020-05-01
*/
public class QueueImpl implements Queue {
7 d3 G4 u% E5 `, Q+ t4 n1 p( ^4 _. N
0 k) k6 a) [. s! t    protected Object[] element;
, C' [; W! p. [7 u
6 O- ~/ j6 L% P9 Y* W0 T3 S    protected int elementCount;
4 g. Y3 E4 K" m* x8 l
    //队头
. A! Q/ g+ @3 u. d    private int front;
+ F3 O7 \6 C4 M5 p; P* v4 N
. q3 I/ K% Z: R4 y) }1 ~8 X    //队尾
    private int rear;
" m) s; J$ _) O# S- {& c0 r
    private int defaultSize = 16;

; U' A: E" I4 \0 ~    private int maxSize;
' @/ n) O# f, P/ ^( b
    QueueImpl() {
+ Q2 X! p) V! w5 U8 {        element = new Object[defaultSize];
* [$ A% d  @2 a2 d$ X3 j        maxSize = defaultSize;
+ P' Z2 v+ w* Q, O# i        front = 0;
        rear = -1;
9 Z, M* p" `9 O6 B5 |    }
- W6 V5 J+ Z5 l" g
, F% I8 g, ~! u0 I    QueueImpl(int size) {
        element = new Object[size];
        maxSize = size;
3 X# g, T- }6 ~! p* G3 y        front = 0;
. j5 T  U' e+ @/ D5 f- U) |: L        rear = -1;
    }
# ?7 r2 W) r7 J2 c9 Y  Z
; l) l  b9 ?9 ]) d5 v    @Override
! d* v9 M( Z/ s+ Q    public int getMaxSize() {
        return maxSize;
1 O4 U, f  m) l8 w$ [    }

; s: N; ?# [. Q; z/ _' n6 \    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
4 b% \' u( F, s# S" M# t0 r1 D* d; s# \            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
  M8 |) X+ S9 C        element[++rear] = object;
        if (rear == element.length) {
            rear = -1;
# m! T. u* U# s& p* @0 b) [0 I        }
        elementCount++;
; X7 _& K5 j: e    }

6 k% {9 i5 m1 t2 S( R    @Override
' Q% H# ^. a4 _2 P    public Object pull() {
: R. p5 k. F+ e& X, j* ]5 M        if (elementCount == 0) {
0 V% n% I  Y% x1 d! l            throw new ArrayIndexOutOfBoundsException("队列中无元素");
8 s6 e( F( d  d$ Y! Q# B2 {$ L8 Z        }
        Object object = element[front];
+ r; [" E1 |4 P        element[front] = null;
5 `& {) d( M+ ^" @+ |+ g* ?        front++;
        elementCount--;
; x, s9 a) x4 @- e        //队列清空，队头队尾恢复初始值
* \  c  \8 D7 o4 c0 M* x        if (elementCount == 0) {
6 a1 t: X# Y' u) [+ J  \            front = 0;
2 q6 r+ V* s0 ]+ A            rear = -1;
        }
        return object;
    }

. X' @- t$ k2 S. ]( G! I    @Override
    public int getElementCount() {
* z* z9 J; l& T        return elementCount;
    }
7 D' ?* b2 \: b2 c6 I
    @Override
    public Object getFront() {
+ y3 `9 P0 |2 d% K% c        if (elementCount == 0) {
            System.out.print("队头无元素");
  x/ m! P# `" Z  M! R  W0 e            return null;
* ?/ V, F7 u' m; E9 Z        }
9 x: O, C' T& b. m) o# H) [9 m        return element[front];
; l8 U. Q: n7 [4 m    }
8 p( Y! d7 Q+ E( [6 E6 o6 D  [
2 t: u+ f, M1 D    @Override
    public Object getRear() {
1 H6 ~. [) G6 v, ]0 @) G        if (elementCount == 0) {
            System.out.print("队尾无元素");
            return null;
        }
        return element[rear];
* M7 r/ S; @* ~  Q    }

; o$ _( f* F+ e, I" Z$ b. B    @Override
$ x* ^5 f0 L+ x. S    public void traverse() {
3 h) [7 Z% k% ]        if (elementCount == 0) {
: ]- i0 z/ M1 r+ }3 S5 l" G' G3 I            return;
        }
! K& \2 [9 v% J: b: D6 V) G0 s5 ~3 X- R4 d        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
        }
        System.out.println();
4 l+ K: g6 C/ ~9 E& T+ ?    }
}

7 p! B/ s7 X" p# I( R, U7 Q
- ~8 r8 D, a: j3、队列的测试
public class QueueTest {
9 ]5 d( ^8 [- q9 V    public static void main(String[] args) {
! O4 F# {" }; E( C        Queue queue = new QueueImpl();

        //获取队列大小
8 v0 X; Z% \) S. L2 ^  ?        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
1 T/ y8 o# Q7 Z; H4 V- U6 O
        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
! Y& n/ n4 r& F* [8 S            queue.push(i);
        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
( |- @  q0 h8 Q) x) X2 e
9 C" T# j& V2 r/ m" N$ _- D        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
2 P  a; C5 \+ f. {4 q        queue.traverse();
" }  r) D5 R1 a        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());


; n' ^* g5 ~$ W) X$ T9 ]! V" i        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
            queue.push(i);
        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
, a, k& R( o9 X5 S. k, j. V        queue.traverse();

- O! x4 P' \3 k
        //第二次出队:取出16-31
0 m2 s: N! J9 S9 d& Y        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
+ T4 @) y/ f; ]  `
: A  ?% V8 n6 O, X, C        //空队列出队报错
        queue.pull();
$ M% v) X  `8 Y% U% H/ |
    }
' v) B+ n* e) @" X6 v) G4 q}



& M4 v( O  i' d2 O% f

& _% H) @: }$ `4 G

- e5 b: f) F; p: R4 E* y* a- o4 w
  s& i& K1 |, |; W1 ]

: M% Z& u$ R( q& z) s

( b% M% S2 E8 u1 {7 t, ?1 f
9 c+ v2 |7 C4 O  K9 Z
) R/ `- Z5 A5 I( S
4 }. a% @0 _; t  ?$ ?: l% k) `————————————————
5 i) e% F% b9 x( c. Q版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 e$ K5 _! H0 q$ Y, K原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785

9 C& q) Z1 w" M4 K