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

杨利霞

数据结构——栈(Stack)与队列(Queue)的手写实例
/ X* @" D6 S( h5 j& h/ E0 o
) H! S1 N$ L. J[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  , b  U" ]  Q( F$ j% C, r* d# C, h
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
      a8 c" P1 }7 E) I5 F! d! |6 f

1 u- `+ x+ P) f
3 r* U- [" x$ R, C; J: y5 K一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
, D3 |9 Q3 ~( G' z1 k$ Y( m$ Q
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。



二、 用数组实现栈1、栈的接口定义
/**
; W7 a1 ]% m4 u/ ~- c* a! ~; _ * 定义栈的接口
1 N! {5 m! d4 H *
2 m  z$ t2 ^5 j9 ^# W. d7 k * @Author zhuhuix
2 t+ t4 N; k4 H; w5 P* G1 C3 {6 c* m2 X * @date 2020-05-01
*/
public interface Stack {
! U+ A4 {0 B6 G: q/ b/ s1 V    /**
     * 入栈
2 c7 [0 H$ t2 _( l$ B+ F! [2 a4 P     * @param object 入栈元素
$ W/ Q$ z% q6 j     */
    void push(Object object);
7 @5 b1 S3 ~9 M' O
    /**
5 h9 Y7 v' [0 ]5 c& g7 w0 |: f5 l     * 出栈
     * @return 出栈元素
9 C, d/ x" U( P9 G5 k: Y; o8 T     */
, w) U4 N. T8 ~3 ^! P    Object pop();

/ ?8 [, \( z) |. v: |  \1 C    /**
. C0 S1 T& n5 r8 K& C- W     *  获取元素个数
9 f( G0 m, B0 q7 c     * @return 元素个数
     */
5 D3 w0 C$ P* H  S- q    int getElementCount();

    /**
     * 遍历栈的元素
5 i- k8 [' Z+ w     */
1 @' _0 d" _& t    void traverse();

}
2、栈的接口实现
/**
* 栈的接口实现
: O( w% G. a& o& [# D1 ]! J *
2 l/ Q+ `7 z' p+ ?: E * @author zhuhuix
* @date 2020-05-01
*/
public class StackImpl implements Stack {
       
/ V4 H, O9 J5 O( y+ j4 `    protected Object[] element;

    protected int elementCount;

    private int defaultSize = 16;
; P1 f. M+ y! ~& t$ {1 T0 b( X* U
5 S( R2 R' L& c7 t9 i  h9 ~    private int maxSize;
! Q0 X% F4 Z3 A
( _4 d4 ?# ?6 J. f    StackImpl() {
        element = new Object[defaultSize];
' ^1 I  T' ]! V6 h1 U        maxSize = defaultSize;
2 \. d* [: [3 `    }

    StackImpl(int size) {
        element = new Object[size];
* ?& E4 C7 b: q( m- h        maxSize = size;
    }

    @Override
$ v' Z- }. R* |" E    public void push(Object object) {
4 q9 b6 }- O9 V% T+ ~1 f        //如果元素个数已经达到数组的最大个数，则进行扩容
9 W0 L% k+ v) j' ~        if (elementCount == maxSize) {
! Q1 L5 J& [) T2 ?+ E& n" E. T: R            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
2 L) v- e  b- H2 m( |; k% n& S        element[elementCount++] = object;
! U5 G+ @5 g" N. v5 o5 M6 K6 ?" F
    }
( u* y: p' D6 M        // 本代码未实现数组的自动缩小，具体方法可参考JDK
- O7 s7 M9 q/ W6 D0 `  x4 b' S+ Q    @Override
    public Object pop() {
        if (elementCount == 0) {
# h: E: n. A% d  h# H            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
% L; ]/ r5 z0 o  C2 D* p3 g9 l9 f        element[elementCount] = null;
9 v% v5 l: D1 {! `        return object;
    }
% l9 m9 ^" v: Q4 R# {* x( Z& ?
  X2 s; Q# e9 a& j8 |    @Override
$ x, U6 l4 l2 u! e    public int getElementCount() {
, r/ {& Z" \1 b+ G        return elementCount;
    }

    @Override
) ]/ M; i- _, d7 U; P( r    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
        }
0 u3 F$ o) P1 E- K/ q* s        System.out.println();
0 `0 K' F' N- w' z- W7 O    }
4 ]/ e) {9 E* l) ]}
) H1 }( H/ O, n3、栈的测试
public class StackTest {
0 r/ p2 q/ q; y9 a; x8 X  N  e    public static void main(String[] args) {
        Stack stack = new StackImpl();

" ?% i( t2 w, p* Y        //第一次入栈:压入1-15
3 H( D% K* s" p" F  v5 b* R        for (int i = 0; i < 16; i++) {
            stack.push(i);
; j( Z9 d/ z% ~8 [9 \7 |0 t        }
3 G) ^8 ?! \, P  v        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();
) v8 K5 \7 d, K$ }* a4 z
        //第二次入栈:压入16-31
& ~( Z3 I  n, ]& j; M! {        for (int i = 16; i < 32; i++) {
9 w' m  j5 G0 X. q: [) j/ @            stack.push(i);
        }
. \+ m! m) \$ ~* F+ [        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
( F4 ?, ?# [4 N. O3 a! E        stack.traverse();

3 ?/ |3 d- s, Q0 T8 L0 i        //第一次出栈:取出31-16
/ j+ H/ @* Q1 a        for (int i = 0; i < 16; i++) {
- q9 E8 {0 e: U9 `' y) A$ K" u            stack.pop();
        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
) v/ b! P  F/ T: p( F# ~        stack.traverse();
4 I6 ^, K+ T+ z: ~, `. W9 t
7 s( O4 f& C2 b  S! _" z        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
4 ]: D: k' i4 f. i            stack.pop();
8 {: x- ^& z* L4 b; ~( q. L        }
! L- P4 R# }( J* G" P        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
9 I$ z1 F% D4 \) u7 D' o        stack.traverse();
/ O* W0 d0 \2 C& M( v! d5 a
5 G: ]' e8 Q8 y1 O        //栈中无元素，出栈报错
4 B7 L; k, |% U2 K9 |; S( \        stack.pop();
. e. O1 X& B5 m6 }
8 H7 g! f# e" C1 `( g: J7 A    }
}
# {$ s: [6 P& w0 C

4 A+ Q# ]: `% H7 x
  c& f% [4 H$ `: z
9 Q6 c' K  @( b; Q9 A; P三、 用数组实现队列1、队列的接口定义
/**
* 定义队列的接口
*
* @author zhuhuix
( i. P& O5 q$ `2 r * @date 2020-05-01
: F8 q) B2 `/ E+ s8 N( a2 h3 ~ */
public interface Queue {

    /**
0 }; M6 K$ K: r" ~     * 获取队列大小
: X8 I- e, k' Y9 \' v" b: \; {     * @return 队列大小
     */
    int getMaxSize();

    /**
     * 入队
     * @param object 入队元素
3 R8 d8 i) X2 i  j1 \     */
  E# x1 E* h. e/ M, h3 v+ x8 T! R; b. M    void push(Object object);
- ]" ]8 x# F" v! e3 U
    /**
     * 出队
     * @return 出栈元素
     */
    Object pull();
8 N7 {1 S2 h/ [* V. `
    /**
     *  获取元素个数
( g8 i8 N' F% G  `0 r     * @return 元素个数
4 J' s+ O# _$ K5 W  m( D     */
  l& d" r; }, u    int getElementCount();

9 S! G; W, e0 b    /**
     *  获取队头元素
     * @return 队头元素
) [. ^5 N- R+ K8 ]3 h+ x/ t- l     */
% w$ S* E/ M( L0 G( o5 o    Object getFront();
) D  y1 A1 D$ z7 ^9 K0 p
    /**
     *  获取队尾元素
4 Z* x8 `) M4 P: ^     * @return 队尾元素
+ p" ]- l, C6 M8 v     */
    Object getRear();
9 Z3 n6 I6 A3 [' e
    /**
     * 遍历队列的元素
     */
    void traverse();
, F* N' U" x* b8 L}
2、队列的接口实现
/**
2 z) ^# O. W8 }5 D: D0 m" q' E% s * 队列的接口实现
* b# R" ?/ T+ B2 H$ C7 @ *
( D9 e: P- t! v0 V7 z0 `% J6 F% n * @author zhuhuix
" z7 a" y, H) k. e5 Q * @date 2020-05-01
*/
$ j5 h7 |) P' O3 E* d7 Gpublic class QueueImpl implements Queue {
3 Z' f2 c6 F$ [5 }
# t  T# b6 E, g0 R    protected Object[] element;
8 B! @/ N( @5 `$ b0 p' X& l
  P; b6 w  \9 M6 d    protected int elementCount;

2 J$ ]* ~- y. C) w    //队头
4 b& z) B. [) l: p& S5 v( Q    private int front;

+ z  o; c1 d* L( k: ~, S* Z    //队尾
: R$ D! t9 k3 e% S4 ?    private int rear;

/ S+ ^+ ~# I. N& ~    private int defaultSize = 16;

    private int maxSize;

0 ?" O: @' S, q2 x$ v    QueueImpl() {
" `: U8 j: J% d. I* r( @9 n        element = new Object[defaultSize];
        maxSize = defaultSize;
$ }- L9 O% `' N        front = 0;
        rear = -1;
; Y4 v/ W' v& S1 S& h1 W& s    }

( W6 |- b+ J% G6 x2 c    QueueImpl(int size) {
        element = new Object[size];
1 d! {  h: u3 _7 G+ `8 r3 |        maxSize = size;
+ O2 c/ y2 n! N4 {! d        front = 0;
        rear = -1;
    }
, ?! {6 T1 G  z7 A5 {
    @Override
* ^4 R% P9 q3 T+ C" Q: q    public int getMaxSize() {
3 Q! Y/ u: l* }        return maxSize;
    }

8 [5 M. \4 Q7 k* k    @Override
. [8 g2 U& W1 x% @6 A/ G    public void push(Object object) {
8 I" \! s" G( {+ }        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
- I$ R; m5 D4 e; W9 B            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
8 M  n: }1 J. Y        }
: H, }0 M' |) t' d: a/ D        element[++rear] = object;
        if (rear == element.length) {
            rear = -1;
' v) h+ |1 e+ U% f8 o; s        }
        elementCount++;
9 B  i5 B. A1 m7 v: z    }

8 Y6 D( V4 l( s& A& h    @Override
- f& p# B* j5 K& J: |3 w    public Object pull() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
, T. V, h0 |! ]( F        }
        Object object = element[front];
; |0 n  @7 \9 |3 a0 C        element[front] = null;
  b' h" X! W" }7 {+ R! g( U% I( t6 U        front++;
        elementCount--;
/ D" W! t) R8 P# a( v: j/ Q  l        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
' B. W3 _. C' b. g. ~            front = 0;
- `- H2 P. m, z            rear = -1;
+ b; N* n: Y  u( b1 F( l% Z        }
        return object;
    }

$ c2 Z2 Z* K$ H( m9 |  u    @Override
    public int getElementCount() {
7 d- ^9 K7 ?0 V8 m3 J! x9 U7 j7 ?        return elementCount;
7 C7 K3 A5 C# C) Z) m) K2 W) J    }
( a4 |  C0 P7 p0 ~* b. E. O, X' [
    @Override
* R6 f7 [  y+ \. F$ ~    public Object getFront() {
        if (elementCount == 0) {
2 t9 k, S1 ^* T" {9 ~# O6 P5 N            System.out.print("队头无元素");
            return null;
        }
        return element[front];
    }
7 p$ k- ]" r5 b0 j; y4 V8 ?  Q
    @Override
    public Object getRear() {
        if (elementCount == 0) {
( C- C6 u, g  `6 w0 Y2 k$ d$ y            System.out.print("队尾无元素");
* `: j1 ]4 @* v& O+ L: t            return null;
        }
        return element[rear];
1 U) ?  q" S+ R/ k" V; K/ i. r    }
" `. H* n5 K9 O5 h
  O- O" M3 w4 P% R2 y1 ~1 e    @Override
    public void traverse() {
- ?2 x  Q% V0 D1 m6 D        if (elementCount == 0) {
! ?' R" n# v1 v2 P/ l            return;
        }
        for (int i = front; i <= rear; i++) {
  A3 G5 N! T/ q4 U            System.out.print(element + ",");
        }
, R( t0 _  l% B0 }6 Y( E        System.out.println();
    }
8 E0 Z5 A  }8 A9 Y( U}

8 X- \3 k5 P3 n0 ?- E4 d/ c3 ~
3、队列的测试
public class QueueTest {
    public static void main(String[] args) {
6 o. b. \. j2 K$ Y( _, C: \        Queue queue = new QueueImpl();
0 h( W5 R( }. c( H
        //获取队列大小
& ^; n1 w& e4 q        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

: J2 E, A9 c$ W  w. J& r1 w        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
            queue.push(i);
        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
( E% ~$ e! ^. o1 v+ C9 {        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
7 \+ F% G$ @  c: v' R9 _$ Z& j8 @% U% x
        //第一次出队:取出0-15
( j4 _7 v! _" h0 u$ e- G1 \4 C        for (int i = 0; i < 16; i++) {
/ v  ^0 U9 w$ B6 d% a            queue.pull();
* o0 K" W; t8 Q" J        }
/ z; ^: |& W( {6 q; [4 i        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
5 \: u3 B" z; [2 z6 w$ }. Z) u        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

% v7 g& |1 c( ^" T' ]+ _% g# o0 H& k
        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
            queue.push(i);
0 p0 A8 H4 t4 S" K        }
3 L' h7 `8 B1 y1 `        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();

: y. m# P; V& W: ]8 g0 G
/ v& W) {- W- Y0 f  h, a5 b4 z        //第二次出队:取出16-31
+ s/ t. ^5 h3 j% f7 J  p        for (int i = 0; i < 16; i++) {
            queue.pull();
$ A+ f4 M9 X1 [3 s4 ?9 C- p        }
$ L6 W+ ~7 T- S- s2 N3 Z0 ~        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
: L) u) v1 [7 c. l. s/ k" W        queue.traverse();
, S9 p7 Q1 b9 y0 T! O
& B1 A0 t2 f% d" @1 T1 R5 M5 [        //空队列出队报错
$ ~- T$ E1 o5 ^7 y$ l; p  d        queue.pull();
, \5 `4 c# T1 \% @) H9 u) H
    }
! K! S* j# `6 D}
5 w) j9 O9 ~1 L% n0 I0 Z
  t8 l) G/ M5 ]6 C3 S, P( U, D
. _1 [4 K7 \6 D; I/ k


+ `: A- F( @4 j* r- V' z4 @
8 n1 s( Y# P. u. ?  s0 D9 [0 K
9 T# Y2 k# b9 g- k: W! L1 W

, N& S5 v" O# F4 L' j
! F1 N! A! s) ^; B: F! h$ c
4 M1 {) E2 \! E6 K9 l. [2 P$ `+ o
0 U& [( W$ w) B( F5 k! F  T
* i7 i2 @' x: u* y* \# r+ f; `
1 H& e; M7 Y% d6 z3 \
————————————————
2 f2 r% ]! a8 m( d0 B4 ^版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
4 A$ l! }8 T5 W% q6 B原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785


6 f& u# q9 [, r8 j/ t' r* ?3 ~9 m: T