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

杨利霞

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

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

& N) g6 E  b$ M4 l7 Q& }( M" Z
• 一、 栈与队列的定义
• 二、 用数组实现栈
  , q. W3 P3 ~8 q% |; ^
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

: x7 n" i# M  D) k4 M
一、 栈与队列的定义
& x4 `6 R$ R2 ~/ i4 {栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
) b/ D/ U; u% d1 A6 e) ]. a
; Q* u+ e! y/ ~, P　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
) I$ F7 G. I  G) i* x$ I! Y* P0 E5 r


; O% U6 f3 i- T1 o, e1 j$ v二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
* X' S8 T2 t% {0 g+ I *
& g, O0 @* |% g; a( W * @Author zhuhuix
# f9 W- @, H  i# y * @date 2020-05-01
*/
public interface Stack {
    /**
7 j; O% z/ ~4 a8 `; U2 ]4 s9 s2 h     * 入栈
     * @param object 入栈元素
     */
) V- g" e: ]- q& J    void push(Object object);

0 F4 @' ^/ W" x1 l: v& C    /**
1 n1 o' c' o$ f3 ]     * 出栈
6 G; U6 T$ ^( O  {# J     * @return 出栈元素
     */
    Object pop();
( a! c  U4 G# r2 _
    /**
     *  获取元素个数
6 `0 e: ]9 M: p0 p     * @return 元素个数
     */
0 N- L0 Z7 _  o4 o' X$ e    int getElementCount();

    /**
     * 遍历栈的元素
     */
+ y7 j  ^" V# v1 s6 U' ]/ T( `    void traverse();

/ C8 j; B. w: d+ f5 ^+ ]}
2、栈的接口实现
/**
! H# P% d* Y# e; M) P' x" E& w * 栈的接口实现
, w4 l6 i% T3 Z; z# j& Y *
* @author zhuhuix
4 b* ~: P+ E3 G5 T: v * @date 2020-05-01
*/
' W% I/ V7 D6 apublic class StackImpl implements Stack {
       
    protected Object[] element;

    protected int elementCount;

    private int defaultSize = 16;
" W) I" \; E% F  Q
1 `/ G2 C! l1 |# P5 G% R1 @; W  d    private int maxSize;
5 a3 f7 {2 m9 M* U7 |" M0 D
0 W. B$ u6 k6 ]* n2 Q9 f    StackImpl() {
$ {2 Y9 ?! x( f# d9 x0 i6 j# k        element = new Object[defaultSize];
        maxSize = defaultSize;
7 i" l5 l! b! o    }

% a) P  ]- z8 ?/ u* }! ~$ s    StackImpl(int size) {
; e, {+ h! q0 P. T% X$ L        element = new Object[size];
. ]  D5 x/ m/ m2 t5 ?        maxSize = size;
    }
1 f1 Q* t: O1 F( l! A. _# P
    @Override
    public void push(Object object) {
8 M! k" d0 m9 b) r5 B        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
" C0 v" g7 J  f$ o        }
        element[elementCount++] = object;
! s* J0 O& |+ Z, q& {0 {: z
    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
    public Object pop() {
" X8 M  {* k& _; f! R' N; R        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
6 {! f) d$ x1 p2 g: z: V/ W        element[elementCount] = null;
        return object;
# g" V* X6 D. Q/ Q' B- I    }
9 L$ H7 m6 _6 J: W+ C( J
    @Override
    public int getElementCount() {
9 i$ W9 p! `5 @0 l        return elementCount;
    }
" p% Z, E# Q8 j
    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
4 Z$ k) G9 o& k) Q- _        }
        System.out.println();
! @9 B: O* Q9 P+ x5 V' s4 e- A    }
0 c1 F4 Z4 q7 W% L1 c}
3、栈的测试
public class StackTest {
    public static void main(String[] args) {
        Stack stack = new StackImpl();

4 x: }6 r& C/ ^3 h' e        //第一次入栈:压入1-15
        for (int i = 0; i < 16; i++) {
            stack.push(i);
) {# C. t4 x, \* i$ Q1 @: z- Q        }
9 S( F. J/ M6 C' D8 ?        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
; L" P( ^# M1 W- R# B# p        stack.traverse();

7 M8 _& R( z  \3 R; l6 ?  o( \6 H        //第二次入栈:压入16-31
1 p' D+ D5 j% Q% G3 B" `8 {- Z6 A        for (int i = 16; i < 32; i++) {
( ^7 q; X. w, l0 P; J& O2 }( R            stack.push(i);
; b( n& d& t/ Z/ e        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
5 c/ g/ l" `3 j6 a" E+ v4 g        stack.traverse();

3 _4 u3 C* D0 n5 Y. Z/ I        //第一次出栈:取出31-16
  y' f4 a, U0 M: i( P2 @8 v        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
" [$ W$ b$ N* t* D  o3 C
4 A0 T9 Q9 s/ C% Z0 E        //第二次出栈:取出15-0
/ \$ S* B4 {8 e; w+ i4 u        for (int i = 0; i < 16; i++) {
# U8 q7 E7 S; R; h- {- x# @            stack.pop();
        }
: e: n7 Q$ P9 r  @        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
5 Z, `) H$ I7 h0 l% u4 R
! J6 V: p, W0 M5 R) S, t$ L. J        //栈中无元素，出栈报错
2 b( d: ^; V* u        stack.pop();
( G) J$ B& J# ^& [
  z+ H1 I9 f4 {1 z: S* C    }
}


, m8 z' N  m, [: J
0 x6 Y8 p- S; M1 e9 J, m! e7 Z
三、 用数组实现队列1、队列的接口定义
/**
/ E6 `8 C5 p! s, A2 E$ | * 定义队列的接口
" }' w8 }) a; t0 w( B *
% M/ R3 F5 r0 n# v0 D! _ * @author zhuhuix
* @date 2020-05-01
*/
public interface Queue {

7 Q# u7 W; A9 l% e6 E/ S& `2 E    /**
     * 获取队列大小
     * @return 队列大小
     */
5 I2 n2 |. K' v% I5 G* |0 K    int getMaxSize();
, ]) l; Q' }& B9 A* c
: i5 v- r- G$ O, |; D  E* G0 `    /**
     * 入队
2 n, g+ a7 q8 i     * @param object 入队元素
, V4 y& M& [* N7 u     */
    void push(Object object);

5 K: G0 w' J, K1 x$ [0 n6 w, }, q" F% G: |    /**
& W8 b" v5 `! _' ^     * 出队
     * @return 出栈元素
+ C6 B: N/ S( {/ d1 g     */
    Object pull();

8 ^/ m! ~5 ^# {  o- d/ x6 G1 t+ U! \    /**
     *  获取元素个数
     * @return 元素个数
! I2 W* i# r/ y7 w# _     */
    int getElementCount();
: f3 ?3 ?2 W5 h; x1 ^: g
    /**
- F/ T+ D# n+ ]! @0 l6 \! _: r1 f     *  获取队头元素
     * @return 队头元素
- p3 Q( j: O; O0 h     */
    Object getFront();
3 a8 a5 H3 @% \# o
    /**
     *  获取队尾元素
     * @return 队尾元素
     */
# X& s4 ]9 X1 e$ w    Object getRear();
( g) O0 |; K; j6 D
    /**
3 J) @) d* I: _/ a     * 遍历队列的元素
     */
    void traverse();
6 X0 d4 ~8 R* L4 T7 e}
$ {2 x/ f3 p# z4 Q7 [& C0 [/ }2、队列的接口实现
( K" d  R& N/ z4 n6 q. D; ?/**
* 队列的接口实现
*
* @author zhuhuix
* @date 2020-05-01
*/
public class QueueImpl implements Queue {
3 H, n7 ~" E+ W% k% o1 X" Q
    protected Object[] element;

/ ?* n  ?. a, V9 W  m4 C% G    protected int elementCount;

0 [" D  L3 c: y: |1 _  r/ A    //队头
0 f* V4 l" O# y9 K) a& G    private int front;
/ M( }2 _( E7 o& t+ }/ x
/ ?7 A; s( |1 `0 U. y    //队尾
+ `; k. ~# B0 F- f/ L, m% |    private int rear;

    private int defaultSize = 16;
8 ]7 @3 S: a8 |! b* H4 B
1 U: A2 v3 K* P    private int maxSize;
. I& W; N# o* d' h# K5 ?
7 D- ?  e- d% W+ Y' F; C    QueueImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
        front = 0;
+ s7 ]& T' \# {0 ^        rear = -1;
    }

    QueueImpl(int size) {
% a5 \4 M  ~, ~; [9 D# O        element = new Object[size];
        maxSize = size;
        front = 0;
2 f" U" O0 ]3 ]0 a( [( ?; q        rear = -1;
8 m* O( s* E5 _7 O9 g( M+ z    }
! T* C, C* E: Y( O1 `/ H
+ U3 k: E8 L  C' |    @Override
0 _" y0 W0 J! A' [    public int getMaxSize() {
        return maxSize;
    }
/ A" F  e0 |3 a$ k( G  ~' ?( Z
+ h- _4 w, @* V8 `8 k! h    @Override
+ U9 a* ]4 e9 I    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
, ?  V/ R3 u' s+ L& b        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
, O- J9 _5 H; I# w2 x/ B        }
        element[++rear] = object;
+ G& T/ i7 U- t4 Q# I        if (rear == element.length) {
            rear = -1;
+ d  B7 b* ^6 p( g/ b        }
        elementCount++;
9 _* x. k" x; ^0 ?/ @0 E0 \. [    }
# b/ O- y+ t, e
    @Override
0 \9 u! k& `7 y- E* e$ ]; U    public Object pull() {
        if (elementCount == 0) {
7 y$ V) x8 Q5 d) d. s# h            throw new ArrayIndexOutOfBoundsException("队列中无元素");
7 Q7 k! \% O) o3 O( q1 v        }
) F. Q& i5 r0 \4 h2 w& w        Object object = element[front];
        element[front] = null;
        front++;
  A2 |, D, ]0 @; L. U        elementCount--;
& }6 |4 ~. I2 A6 `% ^: G# J+ i4 T        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
            front = 0;
            rear = -1;
& y* w6 K5 C( p8 t& t. n7 I        }
        return object;
    }

3 Y8 q* L/ w2 A3 ^    @Override
    public int getElementCount() {
        return elementCount;
    }
& A1 P- V2 y/ l8 k8 Y  M0 s
! b: F: T3 u( v+ H8 n, j    @Override
" ]& K( x' Z) S4 b+ p    public Object getFront() {
        if (elementCount == 0) {
            System.out.print("队头无元素");
8 ]) Y# c) n) o( ~9 @! D            return null;
# o& o5 s( z! c        }
* s* d( y8 ]% |% i3 E9 F0 k- f        return element[front];
    }
( t$ v) B- f6 C$ s4 D
    @Override
0 x- _9 T7 w. v/ c  S5 i* e    public Object getRear() {
6 O) S8 C# h0 z5 |; l        if (elementCount == 0) {
            System.out.print("队尾无元素");
            return null;
* N6 L9 k3 v) j$ W1 a        }
0 [$ @& s" w) ]  j6 e* X  g        return element[rear];
    }

    @Override
% N# t+ Y) C* T  t! E    public void traverse() {
7 N1 r4 L" H, _. u* B        if (elementCount == 0) {
            return;
        }
        for (int i = front; i <= rear; i++) {
; W' A- m: |5 _& {8 u            System.out.print(element + ",");
( Y) a* ]$ r$ ?+ R8 S( o* P0 P        }
" ]* O1 b+ \3 q6 g/ J9 I  }" @        System.out.println();
    }
}
7 u; A: f0 J! ?5 `

, X$ G* N. ~1 r6 [& T+ E" L3、队列的测试
public class QueueTest {
& ~6 V! m. H  R, G: ]' J9 v% g    public static void main(String[] args) {
% }" R: T9 h# E2 S' H        Queue queue = new QueueImpl();

        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
5 s! `/ p2 B& I1 f/ m0 F
& V* O5 |' }+ b) {        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
  a# ^6 H. i2 `6 f5 {            queue.push(i);
, ^" [+ S% C# v        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
0 f8 P! k+ e1 {/ |$ f6 s& }$ t, g/ f        queue.traverse();
/ O* ~8 \# }( T) H3 A        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
            queue.pull();
7 v- u  y+ e3 t' \1 E        }
6 ?- u% A3 `- U# \( ?        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
1 Y$ w$ d; C0 x7 r        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

. z3 g: p; j0 t* [6 i
8 u7 U6 S7 R' E; v( A, F" H$ `        //第二次入队列:压入16，31
+ @5 x. Z. D( V1 Y        for (int i = 16; i < 32; i++) {
            queue.push(i);
        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
! V+ V* D0 s9 z# J        queue.traverse();
, ?, ?4 K& W' y

( W, o3 s: G8 d& A* e- ^/ Y        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
4 q* x; Q9 Q: |7 G3 n            queue.pull();
( _& G5 W! f: S6 {        }
% z2 H' a! q. h- G        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
! u* W9 _6 ~; h) l
        //空队列出队报错
; N; ?3 Y0 D9 n        queue.pull();
9 x3 h8 z) P# ^5 P6 j* Z. `
    }
}
1 r% F. r7 L4 P, _0 P" |1 J- |* z4 z


, `" X) {! C) @0 \6 v9 E: _. U
; l" Q' j5 L% N' @) z% C8 e2 x4 g


( K$ M5 K" ], W" t6 ~  S% s! A( u, n



2 H* p6 Z3 j' d) I4 i9 E2 Z

3 o  T1 W' k0 Y/ ^, M. e4 K, a
; L! {! p! U+ i2 j
- i! q% I8 r3 n3 R————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
0 _1 X4 n# B. |/ V! `1 W: w, {
1 J$ d; Q; l( U% v5 ^
& h. ~" D/ N) {$ X+ H/ _