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

杨利霞

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

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

• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  3 ~- Y5 m4 N' _+ m1 z. N
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

2 q9 o0 q( [5 e: X
一、 栈与队列的定义
+ y% E" h: Q' j' ^7 B5 \: ^, d: e栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
" c" V: S- _! O$ D& t2 A: Z1 _
& o% j- `3 ?, ?/ Q) j. A　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
( x, w3 a& V) r' c# U6 s& |  ~; A5 B
9 a' L5 H# k3 v0 x& \! U

- |, f0 Y. |+ b1 y, @. {/ \二、 用数组实现栈1、栈的接口定义
3 E7 i& ~# T' d5 g! e) e! r/**
7 ]% T4 Y7 O% `6 Y+ K * 定义栈的接口
*
- f- E8 r% G9 d3 K* s8 i$ I * @Author zhuhuix
2 f% w0 `( a! \) L4 w * @date 2020-05-01
*/
' F0 \& C: z2 j! @. J  i* Q2 c3 cpublic interface Stack {
    /**
$ ~; `/ y, c) j5 }+ N3 k     * 入栈
' Q2 f" ]+ e0 a7 }4 a- q     * @param object 入栈元素
# o1 [- V6 i6 U( j2 b3 q3 `     */
, \7 R7 Z7 c5 t* x6 C    void push(Object object);
" j. R, U6 f  l% P0 w
    /**
     * 出栈
     * @return 出栈元素
2 x# `" J* D0 l0 I# @     */
    Object pop();
0 K  V, K- G  T
, p% h/ r0 Q  o    /**
  s0 o" q& y/ a: H3 y     *  获取元素个数
# G7 s! n3 J4 B$ R2 T/ e. s     * @return 元素个数
     */
    int getElementCount();
- H! e% g1 a$ l$ J' d9 G. K# d3 ^
' @* y2 @% C8 ?; O' v, L    /**
, y) f( Z4 p/ t9 U) z1 O' [     * 遍历栈的元素
     */
    void traverse();

}
2、栈的接口实现
/**
  ]- t; v8 S" `$ S0 U" ] * 栈的接口实现
1 j2 Z! L  v/ C& D" ?3 M) ? *
; \+ F7 P/ Z6 I3 m. U * @author zhuhuix
/ d6 e' K$ O0 u+ d" V$ l * @date 2020-05-01
*/
( y& c8 ~9 N' ]( i: K& upublic class StackImpl implements Stack {
3 p- ^0 k+ u6 i% _+ |% m0 P       
    protected Object[] element;

    protected int elementCount;

# P" O8 [5 S7 D5 p# j% l( n    private int defaultSize = 16;

    private int maxSize;

    StackImpl() {
' B. y5 X  H$ `' S8 E        element = new Object[defaultSize];
        maxSize = defaultSize;
2 D7 p9 c' T% d+ ]& F    }
, D2 \) L% h' l6 X
( V, P+ B. A/ w    StackImpl(int size) {
        element = new Object[size];
        maxSize = size;
    }

    @Override
: z" \  R, ?! a  l8 X5 g' d    public void push(Object object) {
; ^! y# N1 g, a, z+ h  y6 o        //如果元素个数已经达到数组的最大个数，则进行扩容
3 M# S$ Z. x/ p5 l, ]- L) g& Y        if (elementCount == maxSize) {
2 x  O5 s* \% D, n1 r4 e            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
        element[elementCount++] = object;
! O2 n% d) C$ t! }& b2 W
    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
3 v* q6 o% Y% F5 t& P' \    public Object pop() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
  B, f0 r0 q4 n( K) n% N        }
        Object object = element[--elementCount];
        element[elementCount] = null;
        return object;
! _. P( q2 @( x8 ^3 t1 t" E% f    }
! E$ q& H+ _' Y( E* v
    @Override
5 _" y7 P7 D- K6 K6 Y    public int getElementCount() {
        return elementCount;
    }
/ X4 u8 _* [4 I: `0 k" @
$ \) E$ _) U7 O* G  n    @Override
' u# z& V3 W. @; g8 f    public void traverse() {
0 P# o0 ]; ]4 G" r( X; n# o        for (int i = 0; i < elementCount; i++) {
2 s9 Y+ X: V1 c/ H: h            System.out.print(element + ",");
8 F( |6 R- i$ o4 s2 T        }
. P" n2 ?" X1 K+ w        System.out.println();
  H& H5 y& O0 E/ \+ p2 V% E! F    }
! ?2 W% m6 g$ T; u. S: _}
3、栈的测试
public class StackTest {
    public static void main(String[] args) {
        Stack stack = new StackImpl();
; }; h. r) L5 n* I9 y
; H( l5 b# q) p5 G8 P        //第一次入栈:压入1-15
* N" T' h, G  V5 b9 q8 O* D  j        for (int i = 0; i < 16; i++) {
: C" @! r! d1 }! C            stack.push(i);
        }
1 @. G; }& @7 \5 v        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();

3 p2 X: T9 Y6 z2 w        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
* N. _6 O# W* |            stack.push(i);
        }
, B* d5 ^; E+ v& v/ n% C4 j# C. `; ]        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

3 W3 T. x# x8 {2 s        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
. H: P8 T' Y' x7 v2 P* s            stack.pop();
4 M; H& A" O4 }        }
) L6 F3 d: Q  t) ?) H3 Q        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
$ x+ y4 q2 B* {& A, r# W5 @6 j        stack.traverse();

: m0 l/ q3 @& w( ~( y5 Q& e        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
" P% g( Z: e+ m# U            stack.pop();
        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
0 T0 T! t% U4 Q% }% a- f- w, C0 v6 Y, d        stack.traverse();
3 ]( X8 p  a9 d# O+ y: \- E/ D
        //栈中无元素，出栈报错
0 P# O5 c6 F( p6 ?; O        stack.pop();

    }
}
7 d6 i0 b+ V8 h( n& N& a% @
7 n" X; M$ ^8 {. w! `9 W* i+ _


三、 用数组实现队列1、队列的接口定义
1 P0 P# T) _- F% @/**
* 定义队列的接口
*
* @author zhuhuix
1 t* K. Z  w) D" G * @date 2020-05-01
, C& l) o& n8 D# N3 s  O- G */
8 V2 X6 Y+ J4 d$ q5 f% r# s! mpublic interface Queue {

    /**
     * 获取队列大小
8 b* Q9 i$ H4 L" s% u, ~. O  g     * @return 队列大小
1 l+ N) n- b+ j% G0 e4 z* \! }8 q" I9 ?     */
; [. U1 ~9 u  `9 q7 n7 G3 H    int getMaxSize();

% _5 _3 w9 `# X- h    /**
% l+ k' V- ]8 f2 ~: R8 G     * 入队
5 l8 U' ~) Y- \2 E1 w# T     * @param object 入队元素
     */
3 w' e7 n+ x( S* E    void push(Object object);
4 C" |5 j$ e' [6 N$ V, d
    /**
     * 出队
     * @return 出栈元素
     */
3 J. ^% W, C5 W! e' j$ a* ^    Object pull();
/ h! l* v$ z( T5 k
% c4 _0 d$ n0 H6 Q* B7 W2 _2 ~$ K$ N( Z    /**
; k, h, }' T9 Q' e0 N$ `5 t$ F/ X: x     *  获取元素个数
1 v3 I* G% |. o' V     * @return 元素个数
     */
0 r' _' e3 U; K5 g0 G    int getElementCount();
, l( U0 T( m- H: k5 W
  ^& a; `! U* s+ u" X7 t    /**
+ [! L2 c6 n4 x     *  获取队头元素
( O* R5 m% e% ]2 {5 G3 z     * @return 队头元素
     */
/ c' v- G0 |1 |    Object getFront();
. ?, L  |$ W; P  Q" v* O. S
    /**
     *  获取队尾元素
     * @return 队尾元素
8 ]9 p* x) P! l4 t  x/ T; a     */
5 O& a8 O$ M5 c    Object getRear();
# P2 ]; @8 {8 M6 K3 H9 T  j$ w% [
* ~# d+ \+ M2 M; L% i; v- Z* s    /**
     * 遍历队列的元素
  }- V7 M) W4 y4 y. c" P     */
    void traverse();
}
$ p: W0 [" G6 q* u3 G7 t  n% O2、队列的接口实现
; j3 ]  Z. ^. H! }8 P& _8 A/**
4 V6 w5 B, B* c * 队列的接口实现
- B3 M' Y. |  d# Y1 W *
! z4 Z8 L# s" P7 N( o1 I  o * @author zhuhuix
. Y3 }  z* w3 N1 J6 T * @date 2020-05-01
*/
public class QueueImpl implements Queue {

' j) T3 O' J# A8 {    protected Object[] element;
5 f% {5 H" H! M1 n6 w" k
    protected int elementCount;
4 L2 H3 f+ |: r% I$ P5 d0 m
    //队头
    private int front;

    //队尾
3 N* J& Z8 X- G' _& [    private int rear;
, b2 ^3 h( \3 X  x! I6 e% S
# o+ ]+ D& k9 ]0 s) B+ Y" ?    private int defaultSize = 16;

, b' q2 f, n' V) [: I    private int maxSize;

    QueueImpl() {
  E: S. j) t" s) f6 ^        element = new Object[defaultSize];
        maxSize = defaultSize;
# Y' B5 z! n( I' z        front = 0;
        rear = -1;
    }

    QueueImpl(int size) {
        element = new Object[size];
        maxSize = size;
0 l8 z5 R7 G/ `+ n* `        front = 0;
0 L5 [7 l* d" |" ~' X; I        rear = -1;
4 [7 h6 \. F3 o4 n: \    }
% e* V' G) q1 |- @. m
/ \( K) d* C" ^    @Override
    public int getMaxSize() {
9 K- n& L: W* o7 o" g4 G* Y        return maxSize;
    }

: Z5 g+ u" m2 N    @Override
% X7 n9 g: }: Q* R    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
& ^, W) L  B2 t" o6 Z# x        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
; V" o* M" O5 D6 B0 l) [        element[++rear] = object;
! \, j% t* e  W7 Q' |) X        if (rear == element.length) {
            rear = -1;
        }
        elementCount++;
* U( J, Y! j0 \1 c+ j  x    }

    @Override
; D4 p. z. R- ^  w/ U    public Object pull() {
9 f( F6 p3 n: E+ ?  q* Q7 p        if (elementCount == 0) {
$ q+ e8 X! E3 l9 O8 E# o4 ?            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
3 o- U. _+ D  i/ B, E$ A3 L        Object object = element[front];
0 D; O  v- b2 k        element[front] = null;
% f4 i4 }( I! U- P6 U; X% Y        front++;
        elementCount--;
        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
, j/ I6 {0 H# e7 e0 V- D            front = 0;
            rear = -1;
1 x% z3 U2 Q# X+ X% U9 W9 b        }
        return object;
) x/ C& r8 o+ R0 r! r    }
8 v+ i; P3 `5 F0 f/ P/ [1 A
    @Override
    public int getElementCount() {
9 p- x8 q2 [+ `' d0 W6 R# ~        return elementCount;
    }

    @Override
    public Object getFront() {
        if (elementCount == 0) {
            System.out.print("队头无元素");
6 r: i& \/ u% A) n# o; C! r            return null;
        }
        return element[front];
5 u& z. U( C' j4 t8 }    }

# X% T+ ~) J; F% p- o    @Override
    public Object getRear() {
! Y+ d/ q6 o  I# H6 T        if (elementCount == 0) {
            System.out.print("队尾无元素");
            return null;
  l4 W' x1 d/ h3 j        }
! K: V& J5 k, Q  L3 W* m* H. @7 S        return element[rear];
+ B/ A! J6 y/ n- j0 S5 u    }

% L* z7 s7 P, A9 d    @Override
$ R3 E- C! ?* W    public void traverse() {
        if (elementCount == 0) {
            return;
3 Q" d+ J2 @) ^4 }/ F        }
( p) A' Q1 E5 g+ G( l9 v7 [        for (int i = front; i <= rear; i++) {
. Q6 A; W. {# H) j' j- ]' s            System.out.print(element + ",");
! O0 G7 e; R) y- m        }
        System.out.println();
    }
}
5 o: V4 s1 k$ q2 ~

7 L6 m& y8 @; O) s$ e/ n4 g3、队列的测试
; ^7 X- @0 ^! L7 Y5 V- [# ipublic class QueueTest {
* O3 Z0 t' F3 ~5 P1 N7 m- W" |    public static void main(String[] args) {
1 ?# C3 k$ L, X3 g        Queue queue = new QueueImpl();
$ a4 E9 B2 B# ?' R
6 l/ V" _( c9 R' L& R        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
  a; \' ?! `( ~. G
        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
- Y1 J3 M! U& ~5 T( G- |+ S            queue.push(i);
" h  A! T( _5 W        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
; f; c$ c6 N0 a, [! P4 N4 M
        //第一次出队:取出0-15
$ N1 J& O& x& F! U! V% J- {, c        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
# Y0 ^& R& z" I& Q8 x( w        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
0 X/ ^1 f7 U8 `/ [+ V; ^
. e! E3 y% [! ?- C9 ?8 D" w" c  g
        //第二次入队列:压入16，31
, ?- k% V5 D+ X2 e1 D3 r1 Q6 L        for (int i = 16; i < 32; i++) {
            queue.push(i);
0 |2 j. c: U* c- e2 B        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();


* S3 u& c% F$ A# E% d        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
            queue.pull();
  ^8 v6 ]* R8 t7 L        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
, a3 d( y' Z& H( d3 t
        //空队列出队报错
        queue.pull();

    }
/ o7 p! \& H: h}



6 U8 D: _8 l. h0 Q  e4 t$ X

- ?; \" m; e& x! _/ g( q, e7 E




9 J+ J* Y% [) N) Q$ B5 B4 g

7 O  W1 X+ M4 i4 J# m
. t/ t: P: e) G

————————————————
3 Y8 t. {" w$ \, E版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
+ j) r: z) u1 P0 ~2 r* M. C原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785