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

杨利霞

& q! V" r/ P8 ~* T+ c数据结构——栈(Stack)与队列(Queue)的手写实例

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

• 一、 栈与队列的定义
• 二、 用数组实现栈
  3 @4 X# E' Y; E' O; ]; e; C; F6 ~& a
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  9 P3 n/ ^' K) E. r2 o
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

一、 栈与队列的定义
# j. G6 C$ G% g. ~  d& A/ {* A栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。

- w6 W6 X- G& K" J7 t( e7 q' y　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
! T4 Z& n7 c( i8 K- f$ G3 s
- J. Y- d- q9 A
  @+ _, @/ W% A: ~& v
) M+ @( q9 U" e0 k4 }二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
*
* @Author zhuhuix
* @date 2020-05-01
*/
) ^1 p( H7 R7 y' vpublic interface Stack {
/ `  e' B: h3 h/ k( x$ y; [1 l4 |    /**
     * 入栈
     * @param object 入栈元素
9 N, S: O3 h# \) Y6 l, L     */
$ T* W) ?/ S% I# h  d9 l1 R    void push(Object object);

, q2 W/ b: ]3 s$ N0 V  {    /**
     * 出栈
( |( \' o3 N2 h0 i& w     * @return 出栈元素
     */
( W' @4 W* t- q; [( ]    Object pop();
  H; |4 g( G% h) x, h9 |
, t3 n6 G  }( O  x4 ^) B    /**
     *  获取元素个数
     * @return 元素个数
6 v7 D$ ]8 x! j4 k4 L     */
    int getElementCount();
' W( r2 V* q5 Q$ ^
& g$ K0 E* O0 ~+ }    /**
, u/ ?) {; ]; {; Y- k+ ~" K* r     * 遍历栈的元素
     */
2 B' ?6 N! p0 c8 u& Z/ l; T    void traverse();

}
2、栈的接口实现
/**
4 a6 [9 C0 V) p+ a * 栈的接口实现
, g7 \( C- i& q) N2 S *
0 z9 A, V! d$ D" z * @author zhuhuix
& M9 t/ F) Q  h1 ?4 `) G * @date 2020-05-01
*/
public class StackImpl implements Stack {
       
    protected Object[] element;
8 \8 J& `: E9 `+ Z' r3 p* N
+ S6 }3 o/ _  D9 a3 C    protected int elementCount;

    private int defaultSize = 16;
( h7 N0 Q# D3 P0 w0 n5 D/ G
    private int maxSize;

    StackImpl() {
        element = new Object[defaultSize];
5 ?+ O7 B: o9 u3 z$ p        maxSize = defaultSize;
: ?$ O" Q4 }  ?# X    }

    StackImpl(int size) {
        element = new Object[size];
6 }) }/ L6 B9 ]) p0 [8 i        maxSize = size;
    }

    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
2 [( t8 y; n! i( o        }
1 F: g* H2 E( Z7 c- w& U        element[elementCount++] = object;

7 z4 K) `% e, _9 e2 V  U    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
4 p6 q9 T7 I& x; L1 N) X/ {    public Object pop() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
, z, N$ _$ e1 r) ~; \        }
% D4 B6 d0 V4 ?  @        Object object = element[--elementCount];
        element[elementCount] = null;
        return object;
$ R1 Z* E3 k5 x- r" c7 w# R& M) x    }

3 _: e* e% \/ M; V; F$ |. \' Q0 a    @Override
  L" T3 a7 o/ J! T$ G& P. d7 c8 F0 g! h    public int getElementCount() {
        return elementCount;
( R' u/ m9 N4 e3 c4 v' y    }

/ u- R! h8 P% n2 _    @Override
    public void traverse() {
* [( e* |8 w* o: R5 l        for (int i = 0; i < elementCount; i++) {
9 H$ X" V) w# q0 w5 W            System.out.print(element + ",");
2 B+ g5 B9 G3 L% l! x, I* G        }
        System.out.println();
& F2 L+ L. E, n. c6 d    }
2 t7 M( L: M# Y* ?6 r" r}
( M4 I  s2 ]: {; v7 F- O3、栈的测试
7 B  ~6 }8 d) ^; `# U3 a2 i5 \public class StackTest {
    public static void main(String[] args) {
* O+ r9 R. r, T2 J/ S/ y4 H0 G        Stack stack = new StackImpl();

        //第一次入栈:压入1-15
  _. _# @2 W5 I1 U        for (int i = 0; i < 16; i++) {
            stack.push(i);
! X' A# S- M6 Q8 L: M( u+ j        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
) S! J2 X* ~1 M( v& K        stack.traverse();

7 T& \& `% }+ ?# |1 m  S        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
# U+ R: a% W9 \; ?  B            stack.push(i);
! E8 N" N- b& c1 C; l        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
% G- J0 u1 E) B' K9 c& E            stack.pop();
% E1 z% o* W. \' Y, H& [' G        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
; r' P8 w3 Q- _' Q5 z' q* F# d1 K$ c: |        stack.traverse();
+ P- h7 Z! n  l4 K3 g: K
1 Y( J5 d. x% l% u        //第二次出栈:取出15-0
( x+ U* d  h* r4 T" c: ^        for (int i = 0; i < 16; i++) {
            stack.pop();
* o6 t# ~; d& ]        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
% A# F# @" c: `: }        stack.traverse();

        //栈中无元素，出栈报错
7 u4 M6 e& l& j; Z9 F        stack.pop();
2 r& o) A( _" o) f4 J
  _% X4 y) x/ s. B    }
1 \- j7 T. r% {, {, ~7 t+ _6 z! i}

1 B) m# c! l0 H8 u; }/ |


三、 用数组实现队列1、队列的接口定义
# U/ d+ j. T6 k" I* @/**
* 定义队列的接口
*
* @author zhuhuix
* @date 2020-05-01
) a6 j3 u+ v9 ^5 a0 Z/ Z */
public interface Queue {

    /**
     * 获取队列大小
     * @return 队列大小
# ~( A+ x: H6 M1 [/ |     */
1 b2 s9 a2 T( ?5 A* o& V) Q( y    int getMaxSize();

    /**
     * 入队
; R- U8 ?- X  B+ C: _' L1 ]     * @param object 入队元素
     */
8 X, T, a8 j8 I% A+ U    void push(Object object);
- J) d. [; a2 R- G# v
    /**
     * 出队
     * @return 出栈元素
# h& ~  d. E; n; g% Q     */
    Object pull();
7 }9 V5 N; e, I" Y
2 t6 w, f& g7 h- t# ?    /**
. X' I6 b- s" a3 V6 k     *  获取元素个数
5 ]# S4 j+ R8 t4 p     * @return 元素个数
     */
    int getElementCount();
: t) L# D3 \* y' s; t: X9 t
    /**
     *  获取队头元素
     * @return 队头元素
     */
" J- {; [) v1 z  j0 @3 q) z3 b    Object getFront();

    /**
     *  获取队尾元素
     * @return 队尾元素
     */
; Q) w% k3 S; L- F% U    Object getRear();
( ^( s3 d% j5 z2 _! N4 N
    /**
     * 遍历队列的元素
     */
    void traverse();
}
- C: B) T2 p( `4 t: ?; ^0 f2、队列的接口实现
/**
* 队列的接口实现
*
* @author zhuhuix
* @date 2020-05-01
*/
) G0 X  V8 x, e# l/ F& _5 Q, Epublic class QueueImpl implements Queue {

    protected Object[] element;

' l# p- h+ f4 O! B' `, w    protected int elementCount;
% n! j  F4 H2 z# e" L
6 p0 p: N* k7 F3 m  v$ V    //队头
, ~$ D. u' p6 e& b    private int front;
. Z; P. R# d" u  E0 F
6 ^5 p, Y+ ^* i2 O    //队尾
    private int rear;
9 L! l, K% J4 R5 _; |! s
    private int defaultSize = 16;

! Z7 x/ c' j7 x. N7 ~    private int maxSize;

. \& ~9 E$ z* g5 g8 d    QueueImpl() {
        element = new Object[defaultSize];
. ?1 z7 D, r" H        maxSize = defaultSize;
. Y& }4 N! ]& _/ x7 k% Y( o        front = 0;
% j. u2 W+ l7 H. V        rear = -1;
/ t" {$ T) s+ H/ _- N    }
; F, ?" k5 K! j. Z& J
    QueueImpl(int size) {
        element = new Object[size];
        maxSize = size;
1 c! g$ Q( r# {" Y        front = 0;
        rear = -1;
    }

    @Override
    public int getMaxSize() {
3 b* @; d0 ?2 ]7 y' M6 Q        return maxSize;
    }

    @Override
2 F: D2 |# N, I/ y) T0 `" S  ~    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
6 _9 }- {! x/ ~" |            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
        element[++rear] = object;
        if (rear == element.length) {
' [1 j" D* L: k( Y, k% k. C3 ]            rear = -1;
. k' l2 E( |9 A/ n        }
# F4 ^6 g' z$ Z        elementCount++;
    }

    @Override
    public Object pull() {
6 H/ W8 @2 h3 b5 P6 ?6 v7 E        if (elementCount == 0) {
: I1 P9 o3 r7 v; x7 u2 `/ ^            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
        Object object = element[front];
% ^0 h, ~; Z7 `# L+ C- D& g        element[front] = null;
* e. b# j9 f2 n1 L) n' j& D$ Y6 ~        front++;
0 c" c* g/ H) f/ T% c( U4 E        elementCount--;
        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
; y/ d) Q: f1 Z            front = 0;
            rear = -1;
        }
        return object;
- o" a  O: T( n    }

    @Override
    public int getElementCount() {
        return elementCount;
: O, C( X: `/ a1 ^+ |3 o    }

/ r, P# O: L! z: V  H" i6 V    @Override
! V; n. U( F; f/ }) Y" J, c    public Object getFront() {
        if (elementCount == 0) {
            System.out.print("队头无元素");
  b  V) z% T: d' K8 s# A            return null;
        }
        return element[front];
    }
) h4 E/ S5 t4 z  E" n
    @Override
    public Object getRear() {
        if (elementCount == 0) {
5 T% L: L, f$ S' z            System.out.print("队尾无元素");
: _7 _" z- C2 A9 J( d0 L# k            return null;
& j: E) O, ]; W% H) S* m# y        }
7 i8 j7 T: l" T& i        return element[rear];
1 |& \/ ?4 P& R* l, y: z    }
4 p# n6 Q" u, j" _9 j) v) f
  n2 x) X+ q! b6 V    @Override
    public void traverse() {
( T( e* ^9 d4 `9 O, E0 W        if (elementCount == 0) {
            return;
        }
9 F2 s1 k# G& D' j% v- E        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
1 z, F: i( D, m% e0 b, F- R8 Q) j+ \0 F, }        }
: Q4 W1 u, _9 Z$ d/ z# x6 b        System.out.println();
    }
}
3 V0 l. n- r( L  M( @: }
5 y/ }' |3 o* M2 k7 t. U! }
+ G5 K4 B5 j+ U+ {; K2 E3、队列的测试
6 q& A1 V0 }, O' a8 T, lpublic class QueueTest {
    public static void main(String[] args) {
* T( L7 r+ D# q, h% ]        Queue queue = new QueueImpl();
2 A' u0 ~3 J+ g6 ~2 I( ]4 o
        //获取队列大小
9 A" l7 u4 k$ Q3 {        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
: ^" D# B- K/ H8 @
2 U* {; W, u" Y        //第一次入队列:压入1-15
! \) H* Z; i# y" h        for (int i = 0; i < 16; i++) {
            queue.push(i);
        }
3 x4 h8 K2 {3 ^! c# f7 h1 q  O        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
5 P9 Q, G( j! J0 F        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
0 b8 H5 J3 S2 p1 n6 u& J            queue.pull();
        }
& ~( I: P" t2 y$ u/ g) C. I        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
6 s$ ^) q- ?) x' j        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
! h7 E, v% ^1 v, Z

7 g* p0 L" O/ t. }% C" o        //第二次入队列:压入16，31
1 `0 f- ~5 r8 R  \  @        for (int i = 16; i < 32; i++) {
            queue.push(i);
        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
: J" P' l9 o/ b# f; k* {1 E/ q$ ]
' l! _, s6 C* Y( q* e- W* n4 h$ s
; T% d: y/ Q" G. `        //第二次出队:取出16-31
" Z* O9 d3 S6 a: y0 Q: M1 n2 Q/ X7 @3 L        for (int i = 0; i < 16; i++) {
            queue.pull();
' q3 M$ |6 {9 C        }
  q! h+ V/ M2 }% O6 A        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
- |7 w/ Y. Q( H7 h3 h8 E        queue.traverse();

2 s# C  d; J' Z7 A+ C( Y& w9 \        //空队列出队报错
3 p$ W, J/ |: ^& \        queue.pull();

    }
}
# T! G8 M/ Y& _) |) a0 {
" d2 D- J1 z6 [: x( P

# u& j( ~' `" ~' r. \! ~
- V/ {& c" z5 Y  F/ s
. @+ e8 m! O' r0 q2 g" {3 z




+ E7 i: ^: J% J* M

. c4 Q  j8 f+ W1 q" g8 s. C
" `) i0 V0 l2 i3 S: d  x

( @1 k4 y) x! ?! E+ [' g" }4 {————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
1 m  {( v* ^  A* U# N+ e7 X3 F原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
+ K( ^3 r  {8 j8 x& k$ b

# A. |0 }5 F# Y; e  H4 e: w5 ^/ ]