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

杨利霞

% b, _8 \/ [& T; F4 u数据结构——栈(Stack)与队列(Queue)的手写实例
0 N1 A9 g; j, }( m4 ~- K
& N5 W0 \4 S1 s$ T6 t+ C[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  4 ~$ Z1 v  I9 U  z& B- ?* d
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    0 a' b! k) S; w% U7 c: s: u/ j# K& _

; j& _" s9 k0 H9 O) d- V
一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。

　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。

) b7 ^, d7 Y5 k% y$ F3 T

二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
*
- e& W9 W  @, t: r  a * @Author zhuhuix
- Z# N, C/ v* W! w * @date 2020-05-01
*/
# H& C/ n2 V: V' M' t/ L3 a6 w. T, hpublic interface Stack {
    /**
     * 入栈
     * @param object 入栈元素
4 g- f& p4 N4 F& b( c* I( B     */
" z* P# U2 A1 D* ~( U4 C- D3 x    void push(Object object);
6 }' O0 y" q# E; n6 N2 i
    /**
- C' Y3 v0 j8 M3 l     * 出栈
4 {5 o+ S* N3 T7 y: J  ~) M% k     * @return 出栈元素
     */
  w+ R6 b% D2 D    Object pop();

( S0 Q! P% Y0 Q4 g' Q9 A( M    /**
     *  获取元素个数
     * @return 元素个数
     */
1 G2 j4 z$ ^, j, I/ i! T; e    int getElementCount();

' X" G) a7 r, r$ @4 F- Q$ g" u/ V    /**
     * 遍历栈的元素
     */
; f9 s" ~- h7 _& Z    void traverse();

}
2、栈的接口实现
/**
0 @- Z5 i* w/ X& G- j, Y * 栈的接口实现
# p# `5 |% a! D# b- R: [ *
* @author zhuhuix
* @date 2020-05-01
*/
& I! d! A" g+ _) j( k% _/ Vpublic class StackImpl implements Stack {
+ z2 ]7 Q6 T- m$ E+ U1 [8 |       
    protected Object[] element;
7 C9 ]9 a$ z4 a3 G% S$ ]8 `
    protected int elementCount;
8 H' s" p. Y. s, L6 a& O
6 [- E3 F2 c+ _    private int defaultSize = 16;

    private int maxSize;

( f& S8 U! Z, n) c    StackImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
1 w# J! `& A" g  j) e5 c1 ]2 ^$ e    }
& @  T8 e5 f- [9 X5 ~
: {$ m& }6 {* Q/ {5 v  ?; `    StackImpl(int size) {
& i. t% K8 k# ?. A        element = new Object[size];
        maxSize = size;
    }
( r, R0 k+ {% T9 G* v8 b1 _- u
    @Override
    public void push(Object object) {
# |5 m8 m5 K- b4 y6 A$ R. k8 g        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
3 y4 Z+ ~# }" H7 ^            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
; y2 r  D/ c3 _; V9 y8 `        element[elementCount++] = object;

    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
/ ]! m( G# l( a6 j: S% D0 W    @Override
    public Object pop() {
" T2 H8 n* R5 P7 Z/ |0 h2 g% e" A        if (elementCount == 0) {
' Q' Q" A9 U# z8 B            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
6 Y0 O3 F( U- R! n( a$ H& g        element[elementCount] = null;
( x+ t& e; W" q0 `        return object;
, g0 W, g) C4 s/ [    }
4 i) M: y+ @, A" W9 b$ g5 o
  X7 P: E+ `& H3 y    @Override
0 {+ C+ w  S  T! |$ z* O+ L; k    public int getElementCount() {
1 |4 l. L" ?/ y2 g4 `        return elementCount;
    }
% m, S* r) j* C! ^
" v7 Z: ^: e. v; ~9 Q# y0 H    @Override
+ |; ]& U! G( D4 r    public void traverse() {
2 H% I# m5 S/ {. H* ~        for (int i = 0; i < elementCount; i++) {
6 _- @% s% p  v# T1 g, U) r            System.out.print(element + ",");
        }
: U  S9 C' H2 W0 r, r        System.out.println();
6 t! d* x3 Z1 a    }
  t5 y6 g& [" A% y% |" g+ i}
( u- V" Y) a/ g9 Q+ L2 h3、栈的测试
public class StackTest {
    public static void main(String[] args) {
        Stack stack = new StackImpl();
3 Q* w6 o4 A& Y
, T7 z" i; k5 T3 n: W        //第一次入栈:压入1-15
& i, X5 U0 x; s0 `9 t2 v: ^+ j        for (int i = 0; i < 16; i++) {
            stack.push(i);
        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();

        //第二次入栈:压入16-31
1 ]# t, N3 f) W$ C        for (int i = 16; i < 32; i++) {
5 O# u) n6 G7 }) L            stack.push(i);
5 }% t9 D( E- D4 C0 F/ N2 |/ R        }
# s/ v$ x7 [/ }( s$ d        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
4 k: h, k$ e. m( c2 {$ S        stack.traverse();

7 M6 p: K# Y* {' G9 t8 Q        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
- o- K% R5 E0 G, F            stack.pop();
4 H& s/ Z; M* }! t8 i. V2 B" @/ N        }
8 w" {8 ]3 T+ y        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
  f  x- ~- o1 z        stack.traverse();
: S# p! P. @$ Y' `, Q3 m
        //第二次出栈:取出15-0
1 j) |( ~8 [0 m6 g; ~        for (int i = 0; i < 16; i++) {
            stack.pop();
" s$ x  ^. p2 @2 A: H, J        }
- C* d% p# B! k8 U        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
: a; x% ~( h; K  J2 K        stack.traverse();
& z3 G4 a. c( X' E, k8 R
; d$ _( Q$ Y7 i9 L        //栈中无元素，出栈报错
+ Z. K' T3 s1 o- t/ v        stack.pop();
% m) o/ ?( Q$ }  d; {! W# R$ y
- T1 ~" a% T+ H3 v' |5 x    }
}


8 ~2 A+ F- z+ P; V
4 ]0 q5 t6 A' J. d! z) m' F' p  D
; V- ?, D( N" l- ?6 R% y三、 用数组实现队列1、队列的接口定义
/**
* 定义队列的接口
- R$ q$ D  \, ]' Q" G6 @) w *
* @author zhuhuix
* @date 2020-05-01
. S. U; X0 |- t; h( g8 ^. w+ \ */
public interface Queue {

    /**
     * 获取队列大小
+ a- o+ o- @6 w; ~5 X, J     * @return 队列大小
     */
    int getMaxSize();

( q" X2 l: E2 |& R. u0 t# z+ }8 h$ m    /**
6 x7 Z- {2 T3 @( y* r( ]     * 入队
1 `9 H9 G! t* R4 |     * @param object 入队元素
  \# J: V$ Z5 A3 M$ u; p% Q- F     */
& B. |. O  M0 Y# i( b9 M    void push(Object object);

    /**
$ H# ~4 f4 n" \     * 出队
     * @return 出栈元素
     */
. ~% z  C* h; n* U6 D- ^3 Q    Object pull();

    /**
" ^. z+ u' E6 J, {* Z. `- @3 m     *  获取元素个数
     * @return 元素个数
     */
2 T; O7 i6 q+ Y. p    int getElementCount();
  m. {6 L) z+ R5 m
    /**
     *  获取队头元素
0 \% i4 c7 P9 S! b+ n. m; F5 F6 z     * @return 队头元素
% B# Q7 e) B3 P, N     */
    Object getFront();

, F6 W/ s( q9 b2 b    /**
  r% k# R: m+ U7 D5 W0 B/ s9 B     *  获取队尾元素
     * @return 队尾元素
     */
    Object getRear();
/ x# u9 U" Q$ k/ N
    /**
9 g/ ~$ K1 j% V8 x: o& O" a     * 遍历队列的元素
7 b7 I8 R5 B: J7 _4 @     */
    void traverse();
}
2、队列的接口实现
/**
) Y9 W0 I- l6 b: h * 队列的接口实现
*
- M* t" {( y& @+ R * @author zhuhuix
6 o) J' Y4 W5 g( F" N: d * @date 2020-05-01
*/
( M% Z( X/ Q  t9 l' `! Rpublic class QueueImpl implements Queue {

+ _- P8 K( E8 O3 y! m    protected Object[] element;

    protected int elementCount;

    //队头
, O5 {. A1 t) n/ T( c9 j    private int front;

    //队尾
8 ~* D3 N  O7 }# q$ m( G    private int rear;
) Y# K$ f2 c+ ]1 o
2 \. Z7 u( E9 e1 m1 \! i6 H: O    private int defaultSize = 16;
6 l. P4 }8 u; ^+ m. z; h# R
    private int maxSize;

9 i( ?3 R$ u* o9 l2 P, S0 Z; ?    QueueImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
% W: h% [3 O' {" {' w% |5 O* A( q        front = 0;
        rear = -1;
    }

3 i- z: p+ H3 h  ?3 W# A, s' M8 n- l    QueueImpl(int size) {
        element = new Object[size];
        maxSize = size;
        front = 0;
        rear = -1;
" Z4 s3 C$ l; l2 ^& Q& Y6 z    }

    @Override
8 R# l4 X+ B/ ?9 x5 W    public int getMaxSize() {
        return maxSize;
% Y: O  J/ g: L4 [    }
$ n! k! m, O8 M  P6 p8 _7 d
    @Override
" ~. V8 W( P/ t% l6 n# x; o( F6 n    public void push(Object object) {
9 H3 J1 ]: }( f2 b$ G, I$ O. ]& D        //如果元素个数已经达到数组的最大个数，则进行扩容
! F" E4 \6 q2 \) H. g5 r# R        if (elementCount == maxSize) {
6 H' U3 c8 t6 |8 b5 w            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
        element[++rear] = object;
4 P& r8 M9 i! K$ J; {6 S        if (rear == element.length) {
            rear = -1;
        }
        elementCount++;
& r/ N2 F/ L+ M' i# ]3 o" M    }

5 u+ ^$ a" O) i9 [9 G! U    @Override
    public Object pull() {
7 Q0 n7 i. f0 J1 x3 m        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
5 h$ y' X& X+ c9 y. ?& }$ [3 q        Object object = element[front];
1 f9 l) B1 z+ L! m6 o: @        element[front] = null;
, n! P" x% H( u8 H/ y( U% k4 h        front++;
        elementCount--;
0 G1 ~% c' E+ `1 q9 l        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
( r2 p( V$ C) o            front = 0;
            rear = -1;
! V3 q% v5 N0 v        }
. X, k5 @# `* v2 h        return object;
    }
. J- D1 Q! ~- q1 Q" u9 e
    @Override
" u9 i% s$ n( @* Z# h    public int getElementCount() {
# k8 D. I9 f5 [; X8 m  M5 C        return elementCount;
0 S& s! [. p5 u5 }    }
0 p2 L- m( h+ o' q
5 c' T7 J* a" z    @Override
    public Object getFront() {
        if (elementCount == 0) {
/ a: s% n! w7 B            System.out.print("队头无元素");
            return null;
' s* P5 t8 W$ x+ R        }
        return element[front];
    }

    @Override
& E% k# ~8 S! N    public Object getRear() {
7 p9 C+ c7 O7 y/ N9 f5 U        if (elementCount == 0) {
            System.out.print("队尾无元素");
0 w* g" ?6 d$ p1 ^( \" ]. Y            return null;
        }
6 s; {( G3 `& c1 H        return element[rear];
    }

+ F3 A, V! D2 a& \* w    @Override
) ^; J) E/ I" |9 c    public void traverse() {
        if (elementCount == 0) {
            return;
# o$ N* O4 X/ `5 @/ o% Z        }
        for (int i = front; i <= rear; i++) {
- S1 z" q5 w- S& M; N            System.out.print(element + ",");
        }
        System.out.println();
    }
  k" Z. Y8 Z, u}


3、队列的测试
public class QueueTest {
    public static void main(String[] args) {
3 A# E9 r! ^5 V- M; w        Queue queue = new QueueImpl();
( ^# x! h- Y" b! q/ P) M* u
        //获取队列大小
2 M, Q5 i, [; ~        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

        //第一次入队列:压入1-15
2 G3 e3 m; t: u$ T  ~! a& ^        for (int i = 0; i < 16; i++) {
            queue.push(i);
) @5 d" ?! D- I        }
  o# F+ X% u: j2 ~        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
! ~/ i- _4 u- w9 C
        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
* l' c, }6 w, \/ g1 M! D5 L2 W( X            queue.pull();
        }
* N( L, [9 y) }4 k1 ]        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
; h0 T+ S2 [6 I        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
0 F! }3 F4 S/ x7 R5 x

7 o: B2 i1 r, o& t0 X7 s7 z$ ]        //第二次入队列:压入16，31
* M2 x& i7 B1 {* c7 x$ b, T        for (int i = 16; i < 32; i++) {
2 j7 x( I1 c% d& {" F. e0 h            queue.push(i);
! Q, l8 Z  b- F: Q        }
1 I% t# t% z/ t        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
8 v: _# f" i* j  b% E        queue.traverse();
# ]" f( e' }' o: T! D

        //第二次出队:取出16-31
6 g4 T# O( C' |! g" l        for (int i = 0; i < 16; i++) {
            queue.pull();
& Z6 Z9 q1 v' M# l        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
: D! i  [- N# w1 i        queue.traverse();
$ Q7 S, z" M7 e# o  G! D4 x
        //空队列出队报错
& N3 I5 m  v: Z; @$ k7 \        queue.pull();

6 M$ Q7 _3 O# R# l, ?8 F9 s    }
9 p, F4 k' E- T1 D8 \9 l/ {9 u}

1 d8 S/ ~. _& |) ]6 v/ S
: q) }+ g! b7 ]
) n2 P- r7 i" P

1 j2 ^4 V" t0 d$ y& [

! t: V# t2 k. ]; f) U% ^



' u, m- f& U9 H/ d% [1 j/ u2 @
- C  {0 p  J2 i5 ]

" X  L/ _: F% P6 g7 O$ K
————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* L! u) Y$ v/ E原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
5 W1 u) H5 l. u
: U1 l& @& U, u8 _" v3 `0 P