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

杨利霞

, b4 m2 c  y+ Y3 Q, d数据结构——栈(Stack)与队列(Queue)的手写实例

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

• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  ! e0 `" ?$ ~7 v! Q
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

一、 栈与队列的定义
( I" l0 m4 S/ L  {1 J栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
* c1 J8 c# B8 j" U! {* ]
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。



二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
*
* @Author zhuhuix
* @date 2020-05-01
2 q6 I) a' D# U7 y8 o& q */
. Y- I. t, F9 O6 U5 T" z4 Hpublic interface Stack {
    /**
     * 入栈
# T3 E" |4 W" S: k4 _     * @param object 入栈元素
     */
! A0 d  \1 y) u" D* U    void push(Object object);

    /**
     * 出栈
5 d9 ?" A8 E; l$ x- ~8 B     * @return 出栈元素
     */
    Object pop();

% [! e* N0 [, j! T6 ]: K    /**
5 ~, W) q5 b' s) W8 ?7 ]# ]     *  获取元素个数
& h* O( E# ]6 Z" A     * @return 元素个数
+ Y3 l- D9 U0 m     */
1 ^0 u2 }8 P+ K    int getElementCount();
' V4 v) r6 b9 Z/ j7 G- _5 H# r
    /**
) n+ a* r. ?, A5 g  c* d2 Y& ?     * 遍历栈的元素
     */
    void traverse();
5 Z8 J* h  ^( @+ p6 P
* g0 \. U3 e8 k: R4 Y}
2、栈的接口实现
/**
* 栈的接口实现
*
, Z- w  r! c" e. O( j7 G* S * @author zhuhuix
* @date 2020-05-01
*/
9 q3 p0 f7 d% D& P7 H( K  Spublic class StackImpl implements Stack {
       
    protected Object[] element;

$ t, d/ x* _* v* @+ F! T. F    protected int elementCount;

    private int defaultSize = 16;
; A% D) z8 e' Z2 i
    private int maxSize;

' n3 ~( W9 K5 l: W    StackImpl() {
. b  S) f, ^" G$ E        element = new Object[defaultSize];
3 N. ~( {9 `7 y: W9 G        maxSize = defaultSize;
    }

    StackImpl(int size) {
        element = new Object[size];
$ o2 P. \: C$ R1 c5 S9 ?3 f" l& k        maxSize = size;
; E) ^5 {6 Q8 x7 F7 P    }
( }7 G! g, {$ R- @( I4 M, @1 i
    @Override
    public void push(Object object) {
: {, [! O. _9 R- d1 C( M* G: e; @2 _7 U0 X/ ]        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
& v" G3 @' E( u        element[elementCount++] = object;
: n, |6 ^0 k1 R; _$ j6 y0 {
    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
) S5 B. a% [( V7 o    @Override
    public Object pop() {
) ^8 W, V) ^7 y! J' o9 D! R        if (elementCount == 0) {
4 \. i( s4 I# e# ]            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
* c1 r! W0 Q- c$ J1 |        Object object = element[--elementCount];
        element[elementCount] = null;
        return object;
    }
9 w8 D6 X* A8 `% R! p) r/ q
: q3 t( C8 D$ G6 y% T0 ?    @Override
- N- z: o; e  B  d  G    public int getElementCount() {
        return elementCount;
    }

    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
        }
        System.out.println();
    }
}
3、栈的测试
! C5 D$ X" u. ?public class StackTest {
    public static void main(String[] args) {
# X* j7 k' k% y% D# ?- I( y: ^# E5 g        Stack stack = new StackImpl();
7 M, D$ k4 v; e" t
( w" V% G- u! E+ ]        //第一次入栈:压入1-15
/ R2 u3 m" w- q  t        for (int i = 0; i < 16; i++) {
            stack.push(i);
        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
8 ]4 Z" V" g& t! Y/ N) k0 [        stack.traverse();

        //第二次入栈:压入16-31
/ A. L$ a, L3 B  C        for (int i = 16; i < 32; i++) {
            stack.push(i);
        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

% H' y* A4 q; V) i: R        //第一次出栈:取出31-16
  F2 c) |- n7 B1 O. Y; s& \) m        for (int i = 0; i < 16; i++) {
/ o6 `# I# W9 `4 f            stack.pop();
        }
! e: j$ I, e9 t" D% F+ \        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
4 b" \" S3 e" Q& Q) u: t; a$ _        stack.traverse();

        //第二次出栈:取出15-0
- A" I9 Z: d) U; _2 A        for (int i = 0; i < 16; i++) {
" y; l: O: |/ i# Z8 B0 I7 g            stack.pop();
. i, C( v# i9 R" A" F; O        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
# [( _0 [) b) c2 [" l" |: O' p9 C        stack.traverse();

0 X; Z) X1 K% C5 H: c: _        //栈中无元素，出栈报错
        stack.pop();

4 `3 A3 x7 X7 {4 U3 w    }
+ b* j1 N( G7 z4 }7 n+ l/ L}

- H; ]  b& d3 N. R8 H/ q: L4 Z


( R/ H' Y2 n- T8 ]三、 用数组实现队列1、队列的接口定义
* `" k/ E6 l5 h0 G7 m. m/**
) A- G3 i0 x1 s; s+ k& I( W * 定义队列的接口
*
, m' A1 L0 G  `% ^ * @author zhuhuix
8 R0 u8 i2 Y9 N( ?* n5 [- [: P * @date 2020-05-01
# O; ~$ g, Q. T */
( h& x8 {, s- E% w% Npublic interface Queue {

    /**
; x/ E9 J9 m$ {+ D. u1 n* J     * 获取队列大小
2 ^' R" u! l6 S  p9 a6 K     * @return 队列大小
! Z7 a1 Q1 Y5 B# t/ E- i4 E     */
    int getMaxSize();
1 p8 g2 I+ ?$ A/ O& g# @4 R
    /**
# c8 B3 p" ~! r     * 入队
     * @param object 入队元素
! Y6 q# f: i( l: B     */
+ e( T1 r$ o  n    void push(Object object);

! l" r. b: i, y2 B7 k7 ^    /**
     * 出队
, J1 k4 V5 i& ?* p     * @return 出栈元素
     */
    Object pull();

. |, b- q- x, T) q: F9 f    /**
     *  获取元素个数
     * @return 元素个数
  I4 a& C8 Z, Y     */
    int getElementCount();

6 }6 Z8 S7 N* a* ?# D, Z3 z    /**
9 @- i0 g% h8 d1 ]     *  获取队头元素
     * @return 队头元素
; U/ j  E: f2 ~     */
    Object getFront();

- a: F/ k$ A& y; k    /**
. u5 ~: k: t- n/ p) y     *  获取队尾元素
0 k* _2 i, j9 A1 k$ }     * @return 队尾元素
" H/ T5 U8 W. d& o     */
4 P% @" \3 I+ B    Object getRear();

7 k) v4 P& c+ x3 ?7 [    /**
1 {( a! J" M4 d! L3 J/ u     * 遍历队列的元素
0 X# z4 Z5 _& C8 ~6 ]- w$ {5 b7 m& D     */
3 {  R  n1 F: w9 Y+ B2 n! ^    void traverse();
}
2、队列的接口实现
/**
7 x3 _2 u1 Y8 D3 X% k * 队列的接口实现
1 `  \' l* L, n1 t  p *
* @author zhuhuix
$ H% Y4 P$ g* j  f% f * @date 2020-05-01
0 a6 C/ w9 n, [6 ~4 D */
public class QueueImpl implements Queue {
9 [/ B8 N  _9 n* d& n
    protected Object[] element;
1 U& X4 W2 U6 y6 L1 Y" g
    protected int elementCount;

    //队头
* W( {/ N( m/ Y4 e& W- w7 o' I    private int front;

/ P) O, f5 Q! O    //队尾
* L2 g* x$ {1 l  I* F7 ~    private int rear;

    private int defaultSize = 16;

' o. N8 H/ M- j! a. D9 B2 W) c' h    private int maxSize;
' p3 O7 L% K" t* l; H8 z8 V' ^1 H
' O4 Y+ z9 R. K9 c    QueueImpl() {
' d% }0 `/ O5 r  k  S- T$ p% \        element = new Object[defaultSize];
& l5 d- T) ]7 Q# T! E' C4 O        maxSize = defaultSize;
2 w- O+ W% ?9 \6 w9 T, ?        front = 0;
        rear = -1;
    }
, v: ?+ a  C5 U! {3 Z; y
    QueueImpl(int size) {
& C  u& r2 A9 a' m, }5 v3 X        element = new Object[size];
        maxSize = size;
        front = 0;
        rear = -1;
    }

$ l& g/ m- l7 w    @Override
3 n" k8 e1 w  a8 P4 ^    public int getMaxSize() {
- l' k5 D6 l. A8 n) }9 S' C        return maxSize;
3 Z8 L. r/ I4 x3 m  h1 p    }
1 E3 D! i  i5 g( ~: ?0 w
    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
7 X6 O' ]# r  ?! P4 p/ K  g* V        element[++rear] = object;
9 D. F! t* @2 I$ u+ G( u% l, w5 y        if (rear == element.length) {
            rear = -1;
4 H8 L$ v6 Q5 w        }
9 j* w" P7 p9 q6 X% S; o" }        elementCount++;
8 K# ]8 }/ i+ J3 z1 z, @1 O    }
# S# E8 ?0 @- G# U3 }, v7 Y% B
    @Override
    public Object pull() {
        if (elementCount == 0) {
- ?* Z! c2 W8 |6 ]# P+ H            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
, w2 ?# e3 `2 N2 i. E2 F: v& n' q        Object object = element[front];
& U4 q5 M2 F9 \: r# N+ ^% L        element[front] = null;
: n# h6 g" k+ s$ u$ c5 Y  s        front++;
        elementCount--;
        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
            front = 0;
            rear = -1;
: x9 G1 A( |2 Y" m$ B# G: g        }
0 k2 g7 T" g9 L3 y        return object;
    }
. ]" G. G4 x6 t$ ?5 T
: T" c2 P0 T8 F; |0 g& L. e    @Override
    public int getElementCount() {
  \, P/ }8 q+ w) S( n        return elementCount;
; ~; V* \1 k3 x5 o" C    }

6 H% B$ O) d$ b1 U& q( e6 _) F    @Override
    public Object getFront() {
0 J5 X" o+ _9 ~        if (elementCount == 0) {
2 ^7 B* m6 z" \7 o; f" s            System.out.print("队头无元素");
            return null;
        }
5 Z0 W. E) g% Y" J7 f9 _        return element[front];
; o1 ]! Z9 Y2 X( d$ X    }

    @Override
    public Object getRear() {
7 ^; W1 T% L8 @2 L        if (elementCount == 0) {
            System.out.print("队尾无元素");
            return null;
        }
        return element[rear];
    }

4 W; T- ]; n; d; C5 L5 z5 J    @Override
( R; F+ Z- v" {5 |) M. J4 M    public void traverse() {
. f' m1 k2 {  n5 x' E8 v        if (elementCount == 0) {
            return;
        }
        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
2 U; [5 n' f) r+ i        }
' l% U/ ^  K0 h. L# }* h        System.out.println();
    }
+ D& R' \* p3 ~' ~9 @- B2 \% F}
/ |5 y+ k4 c. D) u0 h) v8 o- H2 v  F
) a3 j1 ]5 {9 D/ z. g2 _9 N% x5 z
3、队列的测试
public class QueueTest {
! y. E' z4 n6 b5 j    public static void main(String[] args) {
        Queue queue = new QueueImpl();

        //获取队列大小
+ A3 V! B% A& |8 [/ R: O        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

        //第一次入队列:压入1-15
/ C! G6 a9 g/ Z: a/ B: X$ X5 g  M7 }        for (int i = 0; i < 16; i++) {
! m- r# d7 J; M7 k2 O/ B            queue.push(i);
) ^% k' Z8 k2 y        }
$ o8 D5 N2 j2 b' ?! |; |        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
9 h. m' _# _# Z; A        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
- G- h. t* t$ D- P, D" Q. M
        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
) N6 z, p# }* x. R  g& y# D        queue.traverse();
) _$ A' E, r3 H: S8 Q0 E- G: \% I        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
# ?8 @7 `0 |( {8 M0 r$ k
4 Y$ H2 |% k1 D; a. z3 |* @
/ t# h! Q# G& X" @! H        //第二次入队列:压入16，31
  r9 V9 m) \$ P6 P! h! J3 g2 o        for (int i = 16; i < 32; i++) {
3 T+ ?8 m2 ~$ R. L, S# L            queue.push(i);
        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
% J* F* N; `8 k/ A        queue.traverse();
  K9 c6 `7 J, G2 |7 z

2 q& q% H# X+ i; ?        //第二次出队:取出16-31
, D3 M! B  B0 Y" Y4 x/ q* P        for (int i = 0; i < 16; i++) {
            queue.pull();
9 o+ m2 I- t8 c        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();

        //空队列出队报错
        queue.pull();

    }
' p$ W  ?7 F8 r8 R$ R}




8 Q1 X2 W4 `0 G/ `* |' P. J5 G


! }8 F3 Y' {& ~3 U+ h9 e5 e& i
$ C: f, r# P5 s: c4 a
6 \+ K+ {2 g. x0 S
( s% e% c  Y% ]* e

- n9 C3 [: j9 _1 D" q) N! N" L+ E  p

& e5 H1 p& n- |2 |- @4 i
————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
: m) a9 y' b/ }8 N  q9 i原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
" D( D$ U  U& L- ]
4 E8 U4 {7 G: J