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

杨利霞

数据结构——栈(Stack)与队列(Queue)的手写实例
6 f9 p+ l7 L* M8 c# y0 v! a
[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    + Z* q- J' u# D! ?( o8 ~% P
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

! Z" x$ x! `+ p6 o% O6 m一、 栈与队列的定义
7 V3 k1 u% V  r栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
3 ]9 F+ r/ y* n1 q5 }) a
) l/ r' n+ j: y' Y. R+ K$ l　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。

% u' y% q  I) Y

二、 用数组实现栈1、栈的接口定义
# v1 O* h8 P7 O+ c% a& A: M' r) c/**
1 g( O# o8 @- G& t+ w" W% g * 定义栈的接口
# Q' Q* O5 w% v) M# |# P! L *
* @Author zhuhuix
1 x" x8 D% h8 U" M; i* p7 ~) { * @date 2020-05-01
# u% s6 T# t4 S/ @; x/ L */
public interface Stack {
* ?9 J" K# s# m# w$ C    /**
8 `2 M, S' |3 n$ I( \' k     * 入栈
2 k! y. E/ O# h8 ~$ e# H: y     * @param object 入栈元素
     */
    void push(Object object);
% I2 f% w/ D6 O; M6 Z
    /**
1 v* J% K& k3 k& L     * 出栈
& z5 I: l5 p  q  |* L- ~( m6 t     * @return 出栈元素
     */
    Object pop();
/ N9 W  p' }( c
    /**
     *  获取元素个数
( C4 W% G% H* J/ z7 U     * @return 元素个数
     */
3 l( d. m+ D$ v% X! I1 @4 |    int getElementCount();
  s% B+ o0 U8 j) i3 m4 q
    /**
. a5 ^  z" O1 E6 S( }) \# V     * 遍历栈的元素
$ E0 k( k" F3 m     */
    void traverse();
; R4 ~, H; x9 L- ]" c& s. k) D/ X
}
2、栈的接口实现
, b1 _0 u+ v! o8 A  ~/**
$ Y! Y- k3 e4 h * 栈的接口实现
*
* @author zhuhuix
* @date 2020-05-01
$ M  B# g3 C# [" X */
' ^- n9 s0 r4 Y! [3 xpublic class StackImpl implements Stack {
; z2 k3 x, K4 A7 R       
0 w' d: F9 r5 E2 d0 k: E    protected Object[] element;

    protected int elementCount;

    private int defaultSize = 16;
( ~$ x: K0 y, t* f6 V0 q. K
    private int maxSize;

    StackImpl() {
: Y8 r0 P( J0 v4 X        element = new Object[defaultSize];
$ X+ c. |# ~& N; ?! B! p& u& A        maxSize = defaultSize;
2 V$ A2 \! \- _6 s" B    }

  @% w7 t9 P4 l4 z* k/ F    StackImpl(int size) {
2 H+ w/ Z' x, y! {* ]        element = new Object[size];
7 p7 C" D  w& D; `        maxSize = size;
- s% K# G1 Z* K& c3 p4 H  Z1 T% h    }
2 A3 y6 N/ R, G! x
" Z" P. W! U1 p- g    @Override
4 d/ Q" _1 w3 t, Z" _  a    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
6 p  H7 G; I& }# J        element[elementCount++] = object;
" N4 R" W. S+ `4 ^1 \4 _/ ]9 S; c
    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
& R2 u4 r2 W, W/ y9 M) l3 b8 y    @Override
8 M6 }. I0 E7 ?$ {- [2 Y, s/ F    public Object pop() {
9 V5 }  |- ]8 k. b; n- ^        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
        element[elementCount] = null;
4 @& t9 x/ U, _        return object;
. L. C- h3 q7 F. r; e' R1 i    }
- x: S! ~2 }$ c  P) @
    @Override
4 z4 ^4 ?$ U2 e" |" I2 L    public int getElementCount() {
        return elementCount;
    }

+ ]7 y0 }2 T# V# ]+ a4 v, q    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
        }
+ V' d# P" \% Y& Q& q        System.out.println();
    }
}
3、栈的测试
public class StackTest {
    public static void main(String[] args) {
        Stack stack = new StackImpl();
8 _9 h9 q- \) i  T$ L7 G
* ^6 P; R# I9 |  l; a7 M! ~        //第一次入栈:压入1-15
2 {' i$ V! I: x, ^+ G: q        for (int i = 0; i < 16; i++) {
            stack.push(i);
5 ?' H1 Q6 p( s% O! G        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();
3 D9 C+ J; I) u- r8 K; m
        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
            stack.push(i);
; p8 j: ]1 S8 j; q- ?        }
. e! Q' O4 D# ^( h. ]" Z7 J% S        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

& L* y0 K9 o& }: I: E1 ~( Y        //第一次出栈:取出31-16
$ V' L5 {% \; t        for (int i = 0; i < 16; i++) {
            stack.pop();
$ ~2 [# E* V) F6 Z        }
  @+ C4 Y+ D! K  q0 D        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
) b! W; Z" V7 V6 p6 n& F        stack.traverse();
, D. v# O# f6 @0 ~( l
        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
  m  R$ `( \2 B! Z: y# T, c# E            stack.pop();
; ?8 a  j8 \  g        }
3 S) l5 `, f4 }) N) _, J6 a# q        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

) P/ b) `' M+ Y: I& e& I4 t. p( J        //栈中无元素，出栈报错
  g8 s; r5 j9 j) K1 N- R        stack.pop();

    }
# O( I) d- a* p( f8 a}

' |( E6 C3 s6 v2 r( H3 M+ E9 }( q

. i0 f+ C- v& S0 }4 W9 M* }
三、 用数组实现队列1、队列的接口定义
& n$ z8 |& D/ c6 c8 o. `/**
! N7 d! J; {' T * 定义队列的接口
) F  l$ X  Q4 v  y% {7 O) e" h$ k *
! }! s; i- k: C  l9 P. e * @author zhuhuix
* @date 2020-05-01
*/
public interface Queue {
- n! p% B8 F. P+ \
  e4 C3 K* i5 I( S( Q3 W    /**
" h0 m( B; P1 i     * 获取队列大小
  ^. y% ^- x- _& Z     * @return 队列大小
     */
3 b3 W  m9 C5 g0 \    int getMaxSize();
0 [% E+ ]6 P/ T9 y' ]
% k, E3 U9 `) i) h5 R; t    /**
6 [9 G  T2 _- D  a* V     * 入队
     * @param object 入队元素
     */
2 Q% @4 X5 O9 c0 h- _6 L. V    void push(Object object);
2 c: T/ h  E6 w, G
, Z" x& R. G2 K, t$ J2 t( `4 j    /**
     * 出队
     * @return 出栈元素
     */
/ ~2 `1 C- Y0 h: V3 Z    Object pull();

& v5 Z& t" p% \9 A8 ~( O7 U    /**
     *  获取元素个数
     * @return 元素个数
- a8 K9 D* U0 }     */
8 N/ M! x6 f( M/ }. D8 u, F7 m7 |    int getElementCount();
( \* W' x/ y7 D
    /**
) I/ ]' C/ z1 b* T9 `1 U$ A  e/ N     *  获取队头元素
) D5 z" T- q  z. g" O- i9 }     * @return 队头元素
     */
    Object getFront();
& f, P1 q! X) R" k) ?
    /**
! U: ?  }  A) _     *  获取队尾元素
' o: r0 N$ u/ z9 X     * @return 队尾元素
     */
    Object getRear();
6 V% f* b# H8 F7 C4 [$ t
+ ]% ?* s$ U, ?/ v- T    /**
     * 遍历队列的元素
! T7 j- m  r- ^1 o     */
    void traverse();
}
2、队列的接口实现
/**
* 队列的接口实现
: _; b9 i8 x7 a4 A2 | *
* @author zhuhuix
- e# y+ H+ M+ P$ e * @date 2020-05-01
*/
! W! }" H  |" j1 A: ?) y/ `" |, }public class QueueImpl implements Queue {
/ p/ t( a" n1 d# y- p9 |
    protected Object[] element;

8 J4 Y. q8 H$ s3 o' m, W$ V    protected int elementCount;
3 `8 s7 p. b3 ~+ d% K7 U7 J
/ W( @; M: @6 o2 N4 z' Z    //队头
: J' c; N" t2 W3 E! i    private int front;
6 y; X& A4 G# W' M: c6 |8 q7 R
5 a0 ^& L# ]; u- [" x% }; G& {    //队尾
    private int rear;

    private int defaultSize = 16;
: [4 H; N3 a% f3 O8 d% i: P6 m
- F+ E/ Q  a9 q! ?# Q: ^    private int maxSize;
1 y* N4 e% `* `' t) c; b
4 G' ?1 P1 N; m# Z% V  Z- s    QueueImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
        front = 0;
" A* X, T* i7 O; b4 B  z        rear = -1;
    }

4 O9 C$ n3 z$ @7 e; K    QueueImpl(int size) {
        element = new Object[size];
+ u& _- A: F3 d* x# e0 [        maxSize = size;
( W' V  H( w8 c$ u; s5 S        front = 0;
        rear = -1;
9 Q, ^8 q2 |& J( V    }
) y7 z! ?0 o1 q
5 w. X' V6 `- ]- R- g; ?+ ?    @Override
3 W! v2 @; v6 z    public int getMaxSize() {
        return maxSize;
2 f4 x* Y% N- p8 v/ E    }
, D4 y+ j7 h5 x9 \6 N, ~8 u" I
8 l, J* e3 o9 I9 F! L- I    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
% k# \3 |2 y& t5 h6 E            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
        element[++rear] = object;
        if (rear == element.length) {
            rear = -1;
        }
        elementCount++;
    }

    @Override
    public Object pull() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
0 M8 w" I$ _6 [$ F5 M4 F        }
" s7 D0 T# d$ y! |9 o+ S        Object object = element[front];
        element[front] = null;
9 C& `' [/ w7 X+ T        front++;
% D7 ?/ ~& W. T) U        elementCount--;
        //队列清空，队头队尾恢复初始值
! r: q! x# V, ]$ a0 d        if (elementCount == 0) {
            front = 0;
            rear = -1;
0 e& p' f+ _2 Y  M3 Q. p' }        }
4 {& v( ]4 v) S% u1 u3 R( I        return object;
    }

    @Override
    public int getElementCount() {
" j1 B2 a' k: x2 r        return elementCount;
    }

8 \* c& y) [" C/ m  S/ Z    @Override
* P9 q1 k7 E2 E: _    public Object getFront() {
        if (elementCount == 0) {
$ E% E. Z+ \( i. F5 d* V& E            System.out.print("队头无元素");
9 Z0 Z& |( h1 `+ u) G' ~            return null;
        }
) h4 M9 q- o$ s! N4 F' U, k& B3 f+ h        return element[front];
6 |1 p6 T: ]- [$ v    }
; G, P$ E( `2 ?5 i6 J" L
    @Override
  x; o1 R$ F( e# X, z. J    public Object getRear() {
        if (elementCount == 0) {
# r, p6 h2 p; b! e            System.out.print("队尾无元素");
            return null;
        }
$ l" ~1 @( e, l' i9 D8 n) C* R        return element[rear];
4 A0 r0 S5 A0 n5 p    }

4 q5 A8 _- a) U/ u9 Q    @Override
    public void traverse() {
        if (elementCount == 0) {
5 y3 L. Z1 x) u7 `            return;
4 e* |# M2 T+ c7 }8 }5 W! m        }
( u; e: s$ `* ]5 ^$ y: F7 q        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
, f6 |8 u3 t$ u& V! U: f- c" @  j4 S* `4 R        }
9 U' y2 p0 ^& X# h# V  ?, }4 ]        System.out.println();
    }
! u8 j5 z8 t! r8 z" m& L}
3 X3 l- u  ~3 ?" u

3、队列的测试
public class QueueTest {
) P8 V; ?: J. m6 W    public static void main(String[] args) {
5 u6 L5 I; H+ X# z        Queue queue = new QueueImpl();

        //获取队列大小
" @7 l: j& e7 ~        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
, N6 s; u7 Y  f$ A
  Y0 V$ S; M( u& }- l- C        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
' p3 N* S; X- M) S0 o1 t            queue.push(i);
- f0 ?1 B) H' M' c( r" g        }
9 \7 z$ c  r1 Q& E) U, t        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
; C; V3 I5 ^3 [- s) j: e        queue.traverse();
8 C4 z! Q* j! \4 E1 z6 f$ L9 R$ k2 L        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
8 C. s3 R+ M5 [2 u- R5 C( d5 U# X' D
        //第一次出队:取出0-15
7 A: C0 |1 q4 J6 s. n        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
5 _" p% Y% S  N+ D2 ^        queue.traverse();
; K/ g  N& z; ?4 \* v& s2 N        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
8 f7 r- O  I1 X! r, K
/ F: _! S4 [# h( L& N& [% E; c/ L% ?
        //第二次入队列:压入16，31
' g4 L$ k( c6 F' y* b- m        for (int i = 16; i < 32; i++) {
            queue.push(i);
$ \$ Q  B7 h% D  n5 K# c  p+ ], N        }
) o" ~& |" A6 A( i        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();


) ?2 ~) a: C& P+ R. q& Q        //第二次出队:取出16-31
4 q; I4 o# J7 G. z        for (int i = 0; i < 16; i++) {
6 r8 ?3 k, K" p            queue.pull();
$ K# G$ _3 `* K, m4 p9 |6 j        }
8 s; d+ t7 a" T        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
) t7 {) z2 W5 G
        //空队列出队报错
        queue.pull();
. E. z' e( [; U1 y; i2 Z: D% [
& n; b" z/ i& F3 J$ O+ H7 i. j  g    }
7 S0 m" n) Z" a. g! u" J. T}
9 O$ N$ o( g  ?( ?) n8 K

+ q! p) h- L8 h% \" ]' S
: I- t/ D3 r5 G0 B
; |, w9 m$ c+ A& t; S
+ D4 g, {( c+ ~0 {* {
* |* `8 E9 H$ ], N
* a9 Y% T+ ^5 ^5 g  Z, n
9 }- ?! H/ O! [: \) q. j5 w+ X
, C9 D2 A& M  x' [& A  q4 d2 E


& z9 M! \1 ?& E+ w1 h
! q' N8 _9 Z, z" |' `1 u

————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
7 M+ k! @. s8 {& O5 E. q7 n
9 B" w, ]. S: U  S8 [: m