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

杨利霞

数据结构——栈(Stack)与队列(Queue)的手写实例
5 C2 q! i: @; u6 J' {5 q1 L
' t* b+ q1 t% L' X, I% x[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  # H$ G" f$ g8 {( y
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    ) }. w& _% D  @( M9 X0 P
• 三、 用数组实现队列
  0 X$ F: C, W; Y+ ~, X$ u6 G
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    : j5 B1 `4 u. c* |$ `6 l- M

3 p/ ]7 }8 X7 w' K, @一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
0 C/ ]' @; j( \
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
% _3 H1 l( K6 ?6 E+ C4 q& w/ D" o. o

, k9 P0 i. J/ l6 n* |
二、 用数组实现栈1、栈的接口定义
/**
8 c1 b  r( X" W. L * 定义栈的接口
*
* @Author zhuhuix
* @date 2020-05-01
*/
$ E  q$ `7 ?2 y+ N: t8 jpublic interface Stack {
, \4 `) M' S5 X4 e8 W, q4 C( E  u9 w( U    /**
     * 入栈
     * @param object 入栈元素
. d4 z/ R$ q! l7 Q9 j     */
    void push(Object object);
! M! H0 n6 J3 p! O3 s3 k
% B1 t% B1 h8 B    /**
     * 出栈
/ _3 {# A* L% I+ C% K* T     * @return 出栈元素
2 ~2 y8 ^2 B" |( G1 _     */
0 I: `* F/ {: L+ K; y    Object pop();
; C/ Q7 K4 G" N$ h( B* |, }0 U) V
9 U; r% j# z- a3 J& K* A. S    /**
     *  获取元素个数
     * @return 元素个数
2 Z* Y$ f1 R' G& Z+ B& p     */
    int getElementCount();

    /**
0 L0 R1 P% N0 }: m: a4 h     * 遍历栈的元素
     */
- R5 c# c0 T& |5 g/ s9 v    void traverse();

/ h3 V# Q) |6 P}
2、栈的接口实现
% g6 M2 d, `8 I. E/**
" {$ m- U' i  q, v- c0 n * 栈的接口实现
*
" k( X$ }; i3 \3 A& g6 ? * @author zhuhuix
! f% L" V. |9 M2 E * @date 2020-05-01
*/
public class StackImpl implements Stack {
       
0 K( R0 o$ N3 r8 [    protected Object[] element;

    protected int elementCount;

    private int defaultSize = 16;

/ y  k8 q6 M: G8 ]9 t" ]' b+ E    private int maxSize;
. l$ s% U. H; F2 z2 C  O
    StackImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
" y" d) Y+ B* u3 x% d4 O    }
% r% M8 ~  `! I
2 N' I9 B+ d+ J6 Q9 \; {( `    StackImpl(int size) {
( ~9 p. v- J5 `# ]        element = new Object[size];
        maxSize = size;
    }
; o. ?  w. a8 r$ X
# F0 ^' ^& S/ J; f7 Z; R. v    @Override
    public void push(Object object) {
+ z! N5 m: @+ @  P6 W. `: C/ V        //如果元素个数已经达到数组的最大个数，则进行扩容
4 `- _$ H/ O- o5 D, f. x! C        if (elementCount == maxSize) {
- ?% A5 [' R7 {4 l            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
        element[elementCount++] = object;
4 X; \4 `- g$ b" o; f
    }
1 ~: ^5 a9 f: C# W% s        // 本代码未实现数组的自动缩小，具体方法可参考JDK
" V" Z. a2 x2 `" s9 ~6 `4 x- @    @Override
    public Object pop() {
7 [( z, V6 H' h" F        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
0 V% s1 H: J  \: v8 W3 v9 o% e        }
9 I- {/ o, }! `) u1 E- W1 f! B4 x        Object object = element[--elementCount];
        element[elementCount] = null;
        return object;
    }
: Z3 |- F. m2 }9 A2 j
% D. Z3 M* P; j    @Override
. k. p" E1 }2 C. }1 t. N    public int getElementCount() {
6 B" `# E9 q3 {% _        return elementCount;
7 O8 C( H, b& }5 Q- e# H2 I    }

    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
% e' o) W6 s5 m% H( j9 Z            System.out.print(element + ",");
        }
        System.out.println();
+ h8 f7 P. z# i3 X3 \" D/ }    }
}
3、栈的测试
1 j1 a) w/ E/ F4 S# Q& Tpublic class StackTest {
, Z: n. B* C1 f    public static void main(String[] args) {
7 |3 @, W# k- O2 E% S        Stack stack = new StackImpl();
4 f( \/ Q+ F5 S$ F5 L1 y
        //第一次入栈:压入1-15
        for (int i = 0; i < 16; i++) {
- O8 w& x' J. L' X; n            stack.push(i);
        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
% C0 r9 L; T% B1 t5 c6 J4 X        stack.traverse();
6 c: W  H- z8 r
3 c( o- F- U4 B        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
            stack.push(i);
" N$ A7 M3 Z% V  ~        }
( a* Z$ |+ \( j. a& h5 I7 l        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
( |2 F9 T0 s, i7 D        stack.traverse();

        //第一次出栈:取出31-16
% @9 J4 }* \2 b: V- \        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
; l4 ]9 E, s6 W$ l) ?        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
/ D! y& u; t, `, d* s! M% ], x8 K& Y        stack.traverse();

        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
2 Z% O  V6 h" p$ T8 I            stack.pop();
        }
$ K( M. r- `7 Y        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
/ a) U( y! ]% b5 G7 S% X        stack.traverse();
  V/ t) u: k1 [! U/ f/ I
        //栈中无元素，出栈报错
1 w' ^/ z5 x0 V2 i        stack.pop();
( ?( Z' H( s- [- w" y$ ]% }
8 U' O2 |- P( Y4 E) @    }
}

* Y  G7 ^1 c4 ]+ |2 A" E7 x* i3 r7 ?


- o) M2 W( ?) t7 E4 h8 w三、 用数组实现队列1、队列的接口定义
8 a& r+ Y6 Y! ]  n+ d) ^4 @# a$ f/**
9 K% K% M. c" X+ Q/ D+ k4 k( Y * 定义队列的接口
5 Q8 k2 i8 e: A# T; A1 `! d *
* @author zhuhuix
9 \( B! _  ?# L) a  U( G* S2 G * @date 2020-05-01
; W9 [9 `7 ]/ c" n4 R */
3 t: e: ~! {* c! N, Jpublic interface Queue {
- \# f& j3 A) t: b
* q( v" l9 {/ k! @/ X    /**
     * 获取队列大小
  Q/ B) I, ~+ b  T% t     * @return 队列大小
     */
    int getMaxSize();

    /**
+ f! `2 J3 B$ b2 v     * 入队
     * @param object 入队元素
     */
    void push(Object object);
4 t1 a, B* C5 G, T" {
    /**
/ W& s  f2 ]3 ^  ?8 P1 x: g     * 出队
     * @return 出栈元素
     */
) l3 e* h! D$ U! {0 p    Object pull();

. F7 M/ b9 O% M+ k2 f    /**
     *  获取元素个数
     * @return 元素个数
- d% Z2 b! w+ x& g6 n' W     */
$ }" x( R# ^; \; Y- v6 j6 K    int getElementCount();

6 J  `# y2 f, {0 R    /**
4 w* V% ?1 \$ N% _     *  获取队头元素
  v* G  X! i7 y) o$ p     * @return 队头元素
     */
    Object getFront();

    /**
# R  N# w1 P! y2 R     *  获取队尾元素
# G( g) w0 m( `     * @return 队尾元素
     */
4 B% o7 {" h1 u    Object getRear();

) p4 U+ R5 }- _" u7 J( m# d' J    /**
5 `- f; Q7 q( ?     * 遍历队列的元素
     */
/ F9 N7 u; ^9 R$ }! T    void traverse();
8 V- I( B6 c6 Y/ |2 [2 d}
) W" [3 M8 K1 E# _1 S: y( j2、队列的接口实现
- |" W. U  }9 n9 o  P/**
& H/ ?; K8 R* {, A; H/ u6 _ * 队列的接口实现
9 [3 \- F$ E3 j2 o- c; k *
" s/ |$ z! O/ b+ l8 v) V * @author zhuhuix
* @date 2020-05-01
: h3 p) Y4 t% t* R6 h */
" ^; H$ ?7 k( a+ R# _2 p- ^5 cpublic class QueueImpl implements Queue {
( F2 P: O9 ^# {& n
& A2 [: C* \, W, [: R3 |    protected Object[] element;

    protected int elementCount;

4 R  @' H% N9 M8 a4 ?    //队头
    private int front;

/ K. j7 `/ I% A    //队尾
    private int rear;
- s5 l. c2 ]% Y% V5 D/ H
2 H9 j$ `! ^- Z/ C$ k& E4 ]    private int defaultSize = 16;
4 y( v; Y7 a1 F! \$ a3 d3 [* g9 d" ^
    private int maxSize;
" W' }# A' p2 X# f1 w
    QueueImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
6 A6 C2 r4 ~8 a8 w- f# I/ _        front = 0;
+ I8 @/ L0 F0 t6 h4 N8 @        rear = -1;
    }

    QueueImpl(int size) {
        element = new Object[size];
- e+ o* [2 q6 d5 a9 J& z9 E0 a+ W        maxSize = size;
        front = 0;
3 O2 D: d' S8 o  K4 u3 i5 I        rear = -1;
    }
" p9 x# g/ p' s1 h* _" f! z
5 P7 E. e% w& M+ ^; o6 Y    @Override
    public int getMaxSize() {
        return maxSize;
    }

    @Override
    public void push(Object object) {
9 B  P1 R) B3 e8 B        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
0 d/ M  K- j8 u% D            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
$ v* `5 l% q9 S" B, I& [        element[++rear] = object;
5 R8 v7 x! i, ]5 h# C$ I  J/ D        if (rear == element.length) {
9 D. ]* I; M1 s3 ]5 a* p            rear = -1;
4 Y: n4 S$ v9 K) J3 V        }
        elementCount++;
) y9 q7 b* b; {7 |. A    }
* h2 p: d4 k" [1 {! S0 k
- _. w+ w1 E3 {; {, a8 ~' S    @Override
9 P  D, ?3 V$ @; X; ?, d    public Object pull() {
- O$ \4 h8 X% \. V* Z        if (elementCount == 0) {
& V0 b6 _  Q; w5 I$ Y: R            throw new ArrayIndexOutOfBoundsException("队列中无元素");
) L% q) H# B' S( x) _$ Y( i6 {        }
; V6 k" o1 j0 I        Object object = element[front];
        element[front] = null;
" F0 h) N+ \0 C$ B. Q7 s: q% q        front++;
        elementCount--;
        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
. n5 r* q1 G& r# R$ p            front = 0;
$ ?# @& M+ M. R4 P1 Q            rear = -1;
. w( O& Z' O2 G5 y5 N, K/ \        }
  F/ p3 ~8 T6 S" p8 t3 M        return object;
- O, B0 ~1 ^5 M$ X' [, Y* n    }
# m2 P4 h( p% b2 q! K4 {
    @Override
    public int getElementCount() {
" g4 G: @4 ~+ Q9 g1 n        return elementCount;
    }
, p# x2 r6 ]* [+ d8 O
    @Override
    public Object getFront() {
3 c. m$ v* M8 b% J" Z2 C        if (elementCount == 0) {
            System.out.print("队头无元素");
8 ^; @9 s! `0 g% j0 x            return null;
3 o$ h7 V& R+ c$ l( h' F* o        }
/ X  ~7 D! n  j; o3 j        return element[front];
    }
. g* a& u2 y0 c7 I7 k  i
    @Override
    public Object getRear() {
        if (elementCount == 0) {
( w% l1 |6 t, o4 S            System.out.print("队尾无元素");
2 Z. h( G6 s# O% r) n6 F            return null;
, r, k6 M6 i- c& T5 t        }
        return element[rear];
    }

    @Override
    public void traverse() {
        if (elementCount == 0) {
            return;
        }
        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
+ z5 g: P4 n/ Z' C0 B+ Q  r        }
. w% e& p2 Z# a4 l9 U& w        System.out.println();
) {) Z" \# T! z    }
}
# Y& a, O6 T3 A

3、队列的测试
) ~: E" _  u* C2 y0 O7 Lpublic class QueueTest {
4 l% R: ]+ Y# x0 \& T1 Y7 h    public static void main(String[] args) {
        Queue queue = new QueueImpl();
8 `. [8 _, \) V" ?4 f! P- Q! r
        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
! i. l, u# x* l5 }0 J
        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
            queue.push(i);
        }
: `9 {( A' B# n  F        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
' `: e) {  }  _* g: l. b! r        queue.traverse();
5 S% V  D" [& [4 c6 Z        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

        //第一次出队:取出0-15
7 B& w5 I4 P5 u8 B        for (int i = 0; i < 16; i++) {
' S% S$ D4 e/ q4 ?; f            queue.pull();
. |) C  l7 W1 `1 ]' c( R" Z        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
0 L+ R1 N& R9 q, z' Z  c8 s, D        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
5 ~  @; g3 {, Z' m

        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
            queue.push(i);
        }
: g* P  f4 {% C7 {' t        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();


2 g$ ^* m  ?6 }! ]+ [        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();

) R: [; u4 g" b  f6 o- N( u' K        //空队列出队报错
5 u3 g" d  P% ?# R# M! L, C        queue.pull();
5 Z0 P$ n9 T# f& y. |1 ~: Y
, W; I- N. u" p" B& ?' C    }
( i, \2 q5 ?" ?$ @9 l( y}
8 f, ]* |6 @; A: ?
' T( k/ U1 T% D9 Z
& y1 ?  b) Z9 U+ W' D

/ ]) B( H: q' b9 K# y* T% _
. B5 q1 Z9 }0 ~# _5 A# h
7 J4 i/ F9 U* z" g  f; z6 _; V! m, t

5 R  ]3 z+ k" c( K( V
9 h7 |. ]9 N+ t3 ?, x& c, E

" ]  d- i( g0 `8 B5 L


& F0 b$ `: F8 }- F5 L+ q
————————————————
, V* |# U  s" B% w% e5 r  n# @+ Z版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
5 }4 z1 c3 F, z  R