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

杨利霞

$ g3 l) `' n0 @+ @2 m/ T: @& s数据结构——栈(Stack)与队列(Queue)的手写实例
4 B; c: B; p7 E- @' D0 y
* Z3 ~* c3 z, U3 {: o: E[color=rgba(0, 0, 0, 0.74902)]文章目录

  p) F0 ]8 t% j& n8 j
• 一、 栈与队列的定义
• 二、 用数组实现栈
  # P+ P. o- U& b
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  ' a* z7 d2 \2 a( R6 H' D5 H
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
% W9 \4 b: A+ G+ ?* g6 L! g
  `% ^  |, w* V. F$ _　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
2 k" i9 U1 S; a% E8 ?" o: ^


二、 用数组实现栈1、栈的接口定义
. ^- O. o2 @, D: N# h, s" _/**
* 定义栈的接口
# u+ R3 a$ R; a7 ]' j *
* @Author zhuhuix
* @date 2020-05-01
*/
5 Z. d5 E( }, I/ x2 G( O# }7 O5 [public interface Stack {
    /**
3 w9 D6 q) ^# H/ I" y     * 入栈
3 N) |4 j% i+ o7 F! U& k+ i     * @param object 入栈元素
     */
    void push(Object object);
7 {, E# e; t' [( H' ?
    /**
3 I& R5 i) ?  f     * 出栈
/ `0 }* Q' y: ]# M4 p4 k     * @return 出栈元素
; B' P8 c' o, E+ {! M     */
    Object pop();

7 S/ r+ B, o9 R/ V2 V; q. x9 I2 Y    /**
/ J3 y; B: R( q( d" D0 V! o     *  获取元素个数
     * @return 元素个数
     */
1 C" }5 P5 a5 _8 T; ]8 ]: V    int getElementCount();
% e; i8 t+ M  |7 z1 w6 [+ P
( {( E0 G7 H. ^5 c) F  D    /**
     * 遍历栈的元素
1 F" J& F  \) a3 R1 q" }     */
    void traverse();
+ w1 M8 E1 e8 a
" A& {+ F' m4 g4 P, U}
1 v# |* j4 n* ]2、栈的接口实现
/**
* 栈的接口实现
*
5 c2 c9 P4 X: Q- t * @author zhuhuix
* @date 2020-05-01
*/
public class StackImpl implements Stack {
       
$ K$ J! G% z( D    protected Object[] element;
( M; L* k# j, [! D( e3 Q9 n
    protected int elementCount;
, x5 Q7 d% X8 _: A; g2 j/ ^& b
    private int defaultSize = 16;

; Q: |. ?% h! l    private int maxSize;
2 a6 ?: Y. ^, H" ~- M. G1 X, H
    StackImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
    }

    StackImpl(int size) {
        element = new Object[size];
; i3 \5 l$ M; \. C' H- k6 x* x  N        maxSize = size;
    }

    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
. i+ E! M" X& d6 o8 Z            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
* e5 x: y& A% n) g" K' o' m+ i        element[elementCount++] = object;
! t7 Q: V: o# c/ y/ D5 s+ C, K6 L, Y
- A0 n. \7 v. Z    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
, O( Z/ r2 C" c  u' q" Y. G    public Object pop() {
* T) S" G- F. k  v4 |7 @9 {        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
' Q5 l9 x8 i* S3 a! z        }
4 u/ z( b- {; x1 v; I& X% Y3 P& C        Object object = element[--elementCount];
        element[elementCount] = null;
$ h$ J' X$ W. z        return object;
    }

    @Override
% R4 K3 k! U- R9 d# S$ ~    public int getElementCount() {
& t( B1 j9 I1 @        return elementCount;
    }

) m; ^" ~- `9 W2 m) }1 R+ J    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
        }
        System.out.println();
* f: A' H8 s. W- P- Z    }
}
3、栈的测试
public class StackTest {
* h+ ^! j# z) n5 n    public static void main(String[] args) {
        Stack stack = new StackImpl();

" {4 p4 K  r( R9 g8 d& E        //第一次入栈:压入1-15
: J4 F8 T% s2 B; b8 j3 p        for (int i = 0; i < 16; i++) {
            stack.push(i);
        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();
. k, j0 }2 V) K% z! N- Y  n
9 m6 ^  m7 Y' P% f4 C' |/ t1 _& U        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
            stack.push(i);
9 N" g3 b$ _% E. R: v# `        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
7 m/ e' O2 j. Q! \  c, d        stack.traverse();
  f6 Z9 F+ @/ [& @& Q. j( D+ K
+ w2 \% d  C- p! r        //第一次出栈:取出31-16
6 [3 w3 Z! X, _        for (int i = 0; i < 16; i++) {
  S! D! h7 Y; J2 D7 Z7 B& M& _            stack.pop();
        }
( W! I0 S' y- `- p6 D; M2 P        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
' y2 e: d' f2 @, K9 x2 L        stack.traverse();
- b$ _* |7 H6 X  d& H  b0 F
3 [3 K; f" \' B5 {        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
7 x9 ~) ]9 |$ ?) ~7 H$ [$ q% q            stack.pop();
        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
/ L# V% m$ d, {5 M3 I4 u9 c+ t
5 @2 X' I( K3 l3 `( R& f        //栈中无元素，出栈报错
; n; E  D: j3 C% ]4 y& N        stack.pop();
0 [4 U" s0 w. y4 c! D7 x6 f
    }
/ A- f% U# r, O}
$ m/ t' O' n/ [: k8 E% l


3 @, H- w7 t  h
- P$ [  p9 a, W6 b三、 用数组实现队列1、队列的接口定义
/**
* 定义队列的接口
*
* @author zhuhuix
* @date 2020-05-01
*/
public interface Queue {
. [, V( j9 M& d* m# q" W4 U) [7 z
    /**
     * 获取队列大小
9 x: F8 i/ C4 k" Y) _( Q     * @return 队列大小
  l/ w7 L7 X2 H6 J     */
$ _; T. A1 N. B& b5 c1 U    int getMaxSize();

    /**
     * 入队
4 d! {' s/ [" @3 H     * @param object 入队元素
     */
    void push(Object object);
, \" M8 }$ T# D" C& N5 Q( j" }6 c
  d9 v; g! m" v/ N    /**
- Y3 L( x! n7 F: D# S3 V% H     * 出队
0 F5 z9 U$ |$ E  _7 n' ~" C     * @return 出栈元素
6 y  Y6 p! \0 U; ]: G$ N$ f; t     */
- q7 P! |  {' G+ s& V( ]- n3 ]7 r7 p    Object pull();
5 c0 q+ y, D% r
. A% W+ V/ ]* t: I! G" r    /**
4 A9 o1 E/ \+ [     *  获取元素个数
; M0 [$ D) W5 m3 @     * @return 元素个数
) N" L: \" k- L+ o3 t+ J     */
    int getElementCount();
' t% H. y' d& H
, e' ~7 \. B/ x- @/ ?" p# Z    /**
     *  获取队头元素
     * @return 队头元素
     */
6 O/ Z& p" @4 R    Object getFront();
/ M6 V; x2 F; r3 D' W
    /**
     *  获取队尾元素
2 e) y/ f4 r" w4 N     * @return 队尾元素
     */
    Object getRear();
5 W7 O/ |# W/ W
    /**
: {/ u4 \$ @9 J8 u     * 遍历队列的元素
     */
) l$ O/ H4 b/ P1 U1 D1 }) t    void traverse();
, M# q# L% Z+ E1 u/ }0 k}
2、队列的接口实现
/**
* 队列的接口实现
! @5 E' J6 Y$ \6 A! ^8 I6 Q *
* d7 ?, m" P2 k" k: w% R: R/ h * @author zhuhuix
* @date 2020-05-01
" I9 |9 `; e( c1 q */
# j0 }" I8 W. L& t: jpublic class QueueImpl implements Queue {
7 L1 E( i; G" y+ h) x0 N; Q
    protected Object[] element;
. r/ j4 x% k5 u. P8 B' t% @
3 e% ~( H' H; e$ Z1 v  U    protected int elementCount;

, j1 W$ ~& w6 I" [" G: _    //队头
    private int front;

    //队尾
    private int rear;

    private int defaultSize = 16;
( f. O) x, G% D  u8 ~% r. `6 [
  }1 n1 l) A  H8 F3 R% T    private int maxSize;

' |5 u+ s. b* X/ l4 j! H    QueueImpl() {
        element = new Object[defaultSize];
/ o5 a0 k9 u/ M3 H. @% N5 e4 C        maxSize = defaultSize;
+ o7 t, j6 D( z        front = 0;
; w3 B4 B% y% A  U( Y+ j+ p        rear = -1;
+ Z4 I8 K4 [( w9 `' w    }
. X$ H: f/ x2 W
    QueueImpl(int size) {
4 f' H! M$ z- i1 r        element = new Object[size];
        maxSize = size;
        front = 0;
        rear = -1;
    }

! V0 Y& M5 `  c$ x& |7 ?- P0 i8 L    @Override
    public int getMaxSize() {
        return maxSize;
. P) F7 N# k: ?  [    }

    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
        element[++rear] = object;
3 ]6 M) [$ [" O$ w  P: p        if (rear == element.length) {
! ~* a& d. K! }' ?            rear = -1;
" l. _- ~# Q$ z, p- H9 H        }
        elementCount++;
+ L$ E/ ~/ X, C% k$ f- ?& U    }
" t; H$ a+ x( Y. R* a( h
  r  |3 q6 I; u8 X* [( q    @Override
    public Object pull() {
        if (elementCount == 0) {
; b4 [! x3 G& k0 r7 ]: g            throw new ArrayIndexOutOfBoundsException("队列中无元素");
% ]" g& Y7 W% X9 [5 b9 \: K        }
8 K9 y' F' M- S- w" y) `) S        Object object = element[front];
0 c+ U( [8 p% D* j, v' T( c9 Y6 \        element[front] = null;
  _; ]  {/ Z# y' h3 g4 L* Z        front++;
# W/ v3 n7 g3 K7 n' j2 P: N        elementCount--;
+ @7 G4 s, m  ~: p- b7 q% S        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
  s1 M* ?4 v3 K2 a            front = 0;
            rear = -1;
        }
$ U$ }* D  c6 i3 z3 v% d9 p        return object;
6 m% s. F$ F+ H0 ^2 Y& y) ]8 {    }

; \; b0 z( Z  O3 g3 h* S    @Override
    public int getElementCount() {
        return elementCount;
. x3 D$ o7 d: [0 K9 ?* {    }
' f1 E5 u1 Z. e; `
    @Override
    public Object getFront() {
        if (elementCount == 0) {
# a% z9 }3 R! Y7 G' c0 }# r            System.out.print("队头无元素");
            return null;
        }
  _; ~5 l9 B! k9 `  Q" {) a9 A' I$ G        return element[front];
# V7 c/ S1 C  H2 f. @; e, C    }

    @Override
    public Object getRear() {
        if (elementCount == 0) {
5 Q- O1 f0 s$ |2 H; A9 i            System.out.print("队尾无元素");
            return null;
        }
  d- U' G. k; ?9 \9 W        return element[rear];
    }

    @Override
    public void traverse() {
        if (elementCount == 0) {
            return;
        }
0 T0 K5 S, V- J" D8 W+ x        for (int i = front; i <= rear; i++) {
- V, @; S4 y  Y! ]$ e7 U            System.out.print(element + ",");
        }
        System.out.println();
7 w( Y) r" D) Y/ J- {    }
$ b! c/ |% y- }7 {6 ~}
1 l  \% v# {# c8 G: R
( z( E4 g2 |2 U1 I
3、队列的测试
& \9 i. ?! l9 x& X7 G4 Cpublic class QueueTest {
2 b) i1 X- D7 c0 |8 O8 R2 q  W    public static void main(String[] args) {
        Queue queue = new QueueImpl();

        //获取队列大小
: G' @/ j" ~/ `) g/ a        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
$ T5 i. m4 @# u( ^5 G+ B
        //第一次入队列:压入1-15
) h  y3 f. b9 _1 p# n        for (int i = 0; i < 16; i++) {
            queue.push(i);
        }
3 b2 l  G6 @2 }, ~9 o        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
+ g/ e, f( n6 K) D2 z; `7 |        queue.traverse();
  O2 g4 v; k( @, D5 U+ D% b        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
6 P; ^: V$ }" v! f# a6 q5 r
        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
8 @9 A$ n$ P8 g3 ?' a( ]* P        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
5 L: T8 e$ Z2 J% }. B' N        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
& z* Y* u6 c! q! `7 T" D! C* U
- ]5 Q- r+ K( G/ J/ T7 O7 z
        //第二次入队列:压入16，31
, j6 ?5 R4 N- G! R3 j        for (int i = 16; i < 32; i++) {
+ ]5 B+ i! I  }' c& i% ~; ]# F! K' Y( U            queue.push(i);
        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
* _( J9 s/ n% ]

        //第二次出队:取出16-31
. J+ k' Q9 u0 z) n* n8 `; r        for (int i = 0; i < 16; i++) {
            queue.pull();
# v. l! ]. F$ \        }
' e" v. b7 h. a        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
: l6 {& v( L0 W3 ?+ p        queue.traverse();
2 F4 u. L7 U1 a1 I9 Z
        //空队列出队报错
        queue.pull();
) E1 ]7 F  Y) X
5 T5 `' ^6 U3 B/ w( e& @% x( H    }
0 v  E; o1 S: a3 C( o. L}

  C* K, n( m! x+ N# u/ Y; |

& G( ]4 Q/ E: E% V, r8 i


- @+ n. S- \& P



  V) R: R+ h. s0 u% F+ I


, d! T! f$ B) K  f

# @7 @- ^- n' G+ @4 W. M( Z————————————————
2 F0 v3 Q5 ?/ ~版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! p7 v' Q8 i: B  `原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785


3 h$ I* F; t  [% U# [