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

杨利霞

9 v: P, \0 V) S. l数据结构——栈(Stack)与队列(Queue)的手写实例

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

5 a8 `, x2 Z7 x: i: ]! g, W
• 一、 栈与队列的定义
• 二、 用数组实现栈
  % P3 s- O' y+ r
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    5 D2 ]* E: A: }  B7 {
• 三、 用数组实现队列
  2 H# @: `/ D. S( Y' x5 \4 K
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

  ~+ {' f  {1 \- w' h% V+ E
, W* W& S/ U2 w) m/ y+ O一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
( {4 r8 b5 n2 N) i, O! [# Y. ]2 M
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。


$ X9 W0 P# G: r$ O
* y. `* ^" l0 @( H5 w4 o3 x5 b  N, e二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
*
* @Author zhuhuix
. }) {: [. u" p# x& }$ V& h. X* K0 i * @date 2020-05-01
3 A3 _8 E: @6 G- B" L9 |* w */
public interface Stack {
! C1 B9 V9 r* ^* x    /**
     * 入栈
     * @param object 入栈元素
1 n& Q' l7 [$ V) c/ a4 f5 O( i     */
' }: C; W5 a" L" V  Z3 L    void push(Object object);

    /**
     * 出栈
     * @return 出栈元素
9 F! C; d" [( }7 L     */
    Object pop();
' _2 p0 Z3 l6 Y# g
    /**
     *  获取元素个数
     * @return 元素个数
     */
    int getElementCount();
  \9 l  ]7 j7 ]
0 a5 p1 D4 }( Z0 u- j    /**
9 u8 m! C" y; M  N" @     * 遍历栈的元素
/ w' A4 ~, h4 V8 |     */
/ l" a( v+ Y; g3 J. v    void traverse();

}
2、栈的接口实现
/**
0 J  b/ G3 b' A$ V * 栈的接口实现
*
4 z% U) V" j" y" p: N * @author zhuhuix
* @date 2020-05-01
*/
public class StackImpl implements Stack {
3 w* ~9 P0 }4 ~8 R5 s3 N8 d3 v6 o       
    protected Object[] element;

    protected int elementCount;
3 Q" O3 ^$ k9 U% }  l
2 Y4 \" L! r: Y! o* U+ t0 x6 `    private int defaultSize = 16;

    private int maxSize;
5 g5 |: t' E6 A) M& ~/ ?" d( [& i, [
8 N& Z8 l2 S7 Y6 K5 b5 E    StackImpl() {
% a) W7 z4 I" f/ V        element = new Object[defaultSize];
6 B, z6 J7 v& \        maxSize = defaultSize;
! j+ ?, A  o" H) e# O# u7 w& B    }

, t+ M7 X) }( O* @: q0 o    StackImpl(int size) {
  ~  D2 c4 @9 U: S6 I8 g' l        element = new Object[size];
        maxSize = size;
& W5 j: j& ^4 Z. H9 l    }

$ a) w9 g% L5 O! x! n8 {    @Override
/ b3 w- V% H* P' Z8 @    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
* E6 j8 K& J1 u) E! p( ]        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
$ a; [; ]$ x# o* \3 `$ v5 J        element[elementCount++] = object;

2 \% u4 ?6 y, A  @8 C; V8 H8 S    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
, z, I( z: q" ~: ~6 X    @Override
- A$ d# _5 I$ h. Y) X  p* K  m0 n    public Object pop() {
: J( {2 H0 Q5 K+ u- e        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
5 L0 \, ^' s0 L" I6 @  e' r        }
% h+ o' ^2 h' E7 O8 n        Object object = element[--elementCount];
        element[elementCount] = null;
        return object;
+ I: K; x3 W5 V6 D3 f2 p    }
5 b0 E% {' x6 X9 {1 Q
    @Override
8 m, \# S  i7 C    public int getElementCount() {
        return elementCount;
. {1 r- ?8 Y  U( J$ O4 b    }

    @Override
4 ^7 O5 \+ b$ L/ u) ~' Z    public void traverse() {
( j; l7 l: Y; p6 g  D        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
6 f; b4 y' i$ n) j, q        }
8 t+ y: `! y% s, r        System.out.println();
1 v- L: F! M- c* }8 J/ |2 ]    }
}
2 S% f) o' G4 V7 E: l) Q3、栈的测试
public class StackTest {
    public static void main(String[] args) {
        Stack stack = new StackImpl();

        //第一次入栈:压入1-15
: }/ }8 |; h5 i        for (int i = 0; i < 16; i++) {
( H4 Y/ ?0 h, B8 g- m            stack.push(i);
        }
: w" ~) F$ B6 U) y. J& O        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();

        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
0 ~. D1 i) o6 h9 y- k            stack.push(i);
9 g* J$ h5 R4 O5 X1 K0 G        }
) U5 q' F+ D+ E$ f+ f        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
7 ^# X7 O! ?8 k& s3 ~' h        stack.traverse();
# y3 M0 u, ~0 W: A3 C+ {" M% A; u  M
; l: o* }6 {; y, z        //第一次出栈:取出31-16
) j/ [3 s( e* d/ \' W/ }2 @        for (int i = 0; i < 16; i++) {
3 W8 e/ B5 |9 I0 C. i            stack.pop();
7 H' {8 n% H% W: V* i        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
1 T8 l9 Q1 S  v
        //栈中无元素，出栈报错
9 e- m' q8 Z, ~+ X. P        stack.pop();
2 g% \! m+ c0 r, F
! G0 O9 g( Y0 }# `" c' a: _6 _    }
9 `5 [% V2 R, `' p}


; }8 [* u6 q" r- s) ~; c( ?
# `' D3 z+ U1 q* K# @; x
三、 用数组实现队列1、队列的接口定义
/**
5 S. N( H  U6 B$ P* P0 N* @& K * 定义队列的接口
*
* @author zhuhuix
% z/ a4 ?9 o, i+ X0 G' P3 j2 ?9 h * @date 2020-05-01
- S0 i( R) j: j" R/ y) f. P */
public interface Queue {
2 D/ d3 p) B) x3 I* \0 T* K, m- [
! d6 N4 k# f5 E    /**
     * 获取队列大小
     * @return 队列大小
     */
    int getMaxSize();

* l& L0 k( R9 Z. N    /**
5 Z& y9 y1 E$ M) Q" F     * 入队
     * @param object 入队元素
/ F, ^( D0 r: E1 g     */
: }2 S5 J" g+ q5 f    void push(Object object);
  t, ?. g- h  z! p" R& v
  A8 R3 u: {* i; F/ b; E9 n    /**
+ h2 ]  g) V3 o6 K4 W# Y1 ^     * 出队
0 V& z+ _7 Y" K+ p4 F- l     * @return 出栈元素
     */
/ x, A2 B& a! i8 n7 q2 r  G    Object pull();

6 {; w. s0 r1 {% |. \) I    /**
     *  获取元素个数
; L' S- }6 G4 l     * @return 元素个数
     */
' n3 V' _1 N$ ]+ @    int getElementCount();
# Z% `' u9 ]3 e. c1 W$ ~3 o
" R7 j) i/ q' q    /**
     *  获取队头元素
     * @return 队头元素
4 e4 t7 [9 q* r: L8 R- Q! a     */
    Object getFront();

/ {* g* }7 p5 T  u, d3 ?    /**
$ F  u& q6 ?& {: n1 o     *  获取队尾元素
     * @return 队尾元素
     */
    Object getRear();

7 h! I' F- [! K% @7 Y6 F. i9 ~    /**
     * 遍历队列的元素
( V# G5 o8 j, ]& b9 p: ?+ ]     */
) N! b8 ?' [( ^5 P9 ^* z8 C4 u) D    void traverse();
' L7 a3 }4 ^0 U9 m' Y- m# ]}
& u* A/ ]6 ~/ R. g! {2、队列的接口实现
3 s4 n3 D/ c5 @/ m+ }) d/**
* 队列的接口实现
8 C* Y  \# s' n- x% v) n *
7 C, }3 n3 {; B6 K7 Q. ?2 j* ^5 O" g% u * @author zhuhuix
' F& A- J) k3 Y3 y3 R. ~* W * @date 2020-05-01
4 u7 ^2 C0 l/ B */
: A- d0 q( k$ [# o( z: }public class QueueImpl implements Queue {

: o+ K, m% b4 P  G/ u/ ~, c    protected Object[] element;
& Y# Q6 l( h5 d) I3 U9 i( u/ w
    protected int elementCount;
* f7 @% Z6 c' p' ^( h
8 [& l8 \, q* g( z' E$ x    //队头
9 v! D4 _$ k8 ^. V8 _% w1 o    private int front;

    //队尾
+ S7 b, h8 M( v; X  o) G% T    private int rear;
* Y% W& j3 x& S, H
- G8 I- |9 O: Q: g    private int defaultSize = 16;

% E# d0 q8 S  |    private int maxSize;
+ c4 t) ^; \5 g# `9 k% ~# |
. I& T! O7 {  k! p, K" L) Q) I    QueueImpl() {
( }; i9 o, X& A" Q# e+ L3 M; o        element = new Object[defaultSize];
        maxSize = defaultSize;
        front = 0;
" X1 B) c( R; y" \6 a        rear = -1;
4 d& w8 U  Z3 L, u; J5 y    }

    QueueImpl(int size) {
0 p3 ^# y" v/ {# B        element = new Object[size];
        maxSize = size;
( R/ Q; G8 Z- u5 ~: t+ J& R        front = 0;
3 @8 O, Q, ~/ h4 ?" Z3 T" _        rear = -1;
    }

* V3 z* y; \! }9 z) b! M6 q9 z    @Override
    public int getMaxSize() {
$ i! c/ U# m; U  w9 J        return maxSize;
% F7 h7 B$ `% D- s6 n7 t! r7 K' m    }

) c2 t. O. V5 F2 M" E) O    @Override
    public void push(Object object) {
3 Z" ~5 ^$ k& v! |        //如果元素个数已经达到数组的最大个数，则进行扩容
1 a7 o( |$ J+ N) k# q        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
* w: t# m: U  t6 s2 _( y0 V        }
        element[++rear] = object;
4 v7 g& R" |* j* t0 _6 R        if (rear == element.length) {
4 I0 J# ]1 ~( \4 V; ^            rear = -1;
: [; ?# G4 e/ m; K        }
        elementCount++;
! ^& k/ O1 h+ J. f8 w$ u) |    }
2 }0 m/ ?% j( l  n3 Y+ ^9 l
    @Override
    public Object pull() {
* j. B% V/ j7 H' j! u( f% c        if (elementCount == 0) {
! @: ?9 p7 k  F3 b! W# r% B" k            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
1 n% y) J# ]. K0 z        Object object = element[front];
        element[front] = null;
1 K- V/ Y0 o5 B1 z        front++;
$ c# g& ?$ s. ^, G        elementCount--;
  E( x+ S, O1 i8 e- y: b4 I        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
; V' W" Y! M" {6 a, p5 @% C+ t            front = 0;
            rear = -1;
6 ]) S  {* l$ m$ P1 i/ j% N        }
        return object;
% V+ r& k3 U4 U; N& e    }

    @Override
, n+ K! w3 w& k1 ~" f; P6 b    public int getElementCount() {
7 |. V+ o9 P* d( D6 |        return elementCount;
    }

8 G3 l! q: S6 F, j. {: l    @Override
4 p$ R1 [, p: f* ?& X    public Object getFront() {
        if (elementCount == 0) {
            System.out.print("队头无元素");
            return null;
$ E, B, |- Z9 z6 o$ l5 t        }
- C' u) H0 ^; u$ B& X        return element[front];
    }
6 r9 G+ r( x  O: T0 {$ @6 g8 ^
6 S7 _) X: {5 k0 g    @Override
# Z/ M, C5 }4 A. A* f    public Object getRear() {
+ A, L$ n/ P8 V, F7 ?6 e        if (elementCount == 0) {
* v0 U% h5 i& ^8 i            System.out.print("队尾无元素");
            return null;
4 P8 Y/ ], k' p, D3 {* p        }
        return element[rear];
* x& T- Q3 S; {    }

    @Override
    public void traverse() {
        if (elementCount == 0) {
            return;
9 \) f5 L5 L! A: L" t  R        }
! v( \! u9 J( M( ^& c( w6 v1 @        for (int i = front; i <= rear; i++) {
4 x+ o5 q, _- `. u7 Z            System.out.print(element + ",");
        }
. e3 b2 U: Y4 W: x+ ?6 S        System.out.println();
    }
}


3、队列的测试
6 q; \6 I0 @8 y$ w0 epublic class QueueTest {
$ n, v# v; {& [    public static void main(String[] args) {
        Queue queue = new QueueImpl();

        //获取队列大小
( M9 f" }6 I2 }5 ~$ N/ Y        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
0 \* c9 s9 a8 ]. R' d: A
        //第一次入队列:压入1-15
' E  |' g* p$ ?        for (int i = 0; i < 16; i++) {
            queue.push(i);
        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
+ n, E( t/ g. t; h0 ^% i+ u4 O3 [        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
" m: K, h2 x$ o3 a
( N9 a/ M9 P; n; p        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
            queue.pull();
, }8 `! A" N; ~& y7 d. Q3 [; C        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
; Y1 L$ M1 d. y        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
4 I: k) N: a" z
; P2 Q3 i! M- m3 |$ c
7 J" w/ S  z, v4 R! `# b        //第二次入队列:压入16，31
$ P. n5 M. W, |8 R$ F        for (int i = 16; i < 32; i++) {
            queue.push(i);
, E6 J3 `; q3 u4 `        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
$ X" v" ?6 i4 F: g, W        queue.traverse();
- F. [/ H) A6 S+ A0 c! p" _/ F( z5 F

! p5 {& b8 e$ U) A% o+ X        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
* S/ e5 g7 L* D3 @! ?+ E7 E. z. U        queue.traverse();

! K, d# d/ G) a" n1 Q* s( p        //空队列出队报错
- R0 U/ i) o2 ~8 a        queue.pull();
9 w/ X* b6 Y. M3 E8 n& b4 E
    }
7 o2 a0 n; D, B: I" \4 b}






0 J% l% [# J3 s0 x2 c; h% u7 F


( g9 M. n+ m5 [" V


) y. w# V( Q/ E+ D6 o& l7 q
0 ~$ i# p: ^. k' R/ C  y

: m( c( o! w$ K, t3 N' @————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. K$ L+ ~3 |9 N$ S, C% k; l0 ~原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
/ ?6 o2 b& r% x1 V. J2 k; d