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

杨利霞

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

( R, Z. e. N# R[color=rgba(0, 0, 0, 0.74902)]文章目录

1 k6 Z# H1 X  n& ^% |* z
• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  / [- [, s' G% ]: U0 U% L
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

1 R% I% S4 R' A; X# D- w* Q1 t
一、 栈与队列的定义
( l) L( C& N6 Y7 \5 ^栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。

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



" T# G: n4 Y- s: K6 l1 E二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
2 B& t9 b% }8 K *
* @Author zhuhuix
* @date 2020-05-01
*/
public interface Stack {
- x* W. y' o: G; y    /**
     * 入栈
     * @param object 入栈元素
( k9 k2 z1 h1 r     */
    void push(Object object);
; _8 ^6 p! k, T5 u0 o% u' N
8 S* N* h! n. ~0 p: q% |: J: s    /**
: W$ X& i) i6 e3 _; B: L     * 出栈
" a0 _3 H* q* U/ M     * @return 出栈元素
, M/ [5 p8 |! Y; {     */
    Object pop();
, N6 [; b7 `) _
( s" R/ a" X9 X& H) w    /**
     *  获取元素个数
/ ~( w6 ]; K7 V4 O8 ?0 h8 X     * @return 元素个数
     */
    int getElementCount();

1 M( N) g4 @4 L    /**
/ D/ R0 X& Z# H     * 遍历栈的元素
     */
    void traverse();

2 t9 Z8 j8 _, m9 s  {* `- V7 R}
2、栈的接口实现
/**
0 {% }& o( B' Z& _0 m$ h * 栈的接口实现
/ {1 B5 l. M1 k  R; V *
5 R/ Y' ~6 q7 v8 n8 q * @author zhuhuix
* @date 2020-05-01
*/
' W2 O" q+ i7 ^; j# w9 S6 F: fpublic class StackImpl implements Stack {
       
) I9 J& }" @- {$ @. r6 ^2 Q; `    protected Object[] element;

    protected int elementCount;
2 I- H/ V: ]& }, I* j3 \
- p% b* s3 I% a$ X1 \    private int defaultSize = 16;
; [7 ~3 T' t5 s1 |3 o/ b, e* c; [9 `
    private int maxSize;

    StackImpl() {
        element = new Object[defaultSize];
) u2 X0 p: ~( l        maxSize = defaultSize;
8 v% S7 |1 N, ]& \$ n: D, ~( R4 s1 X    }

- j" s4 O! o0 c9 B* Q" V    StackImpl(int size) {
        element = new Object[size];
. k: R: |& S* \9 S5 d        maxSize = size;
* K- e- c; {3 F  O8 \: H- d' l    }

  f3 G" ^# G7 A$ x; o( R, p    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
( z6 b9 C% i$ m3 H        if (elementCount == maxSize) {
: s& f; d0 N3 a" I! p            element = Arrays.copyOf(element, elementCount + defaultSize);
5 ?0 y% q; n. D8 P* y        }
        element[elementCount++] = object;

2 P! L$ Y# L. v3 u% w* F    }
1 T" Z# v* A/ F4 T        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
    public Object pop() {
1 B+ @# F) f) ^1 Z8 q7 F        if (elementCount == 0) {
% }% ^* o2 q# t% ]4 w/ _9 f; @            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
        element[elementCount] = null;
: Q- ^3 _! m1 P" s        return object;
    }
! m3 F! a; T& n! v7 w3 p
    @Override
    public int getElementCount() {
) Y: @. e: b' B2 x: F$ S        return elementCount;
# T. ~4 _( `' Y9 a    }
% h) G  f6 C) ~9 V2 ~
7 ^5 C9 x* c; L) s, m    @Override
7 R$ _% m9 K9 l    public void traverse() {
' D7 x, z- p" [5 x        for (int i = 0; i < elementCount; i++) {
6 ?0 C8 r5 k; t% i            System.out.print(element + ",");
        }
( n6 Q2 v. H4 x: y! M. O& `0 w3 i, C8 s        System.out.println();
    }
}
* W' \0 t, W' s& l: F) b, s" y3、栈的测试
0 J3 @+ W% k% S) A- i1 npublic class StackTest {
7 B( V5 s1 L: v3 K' W% t' I    public static void main(String[] args) {
        Stack stack = new StackImpl();
; ^* U6 r* ]0 t2 ~
        //第一次入栈:压入1-15
7 Y- z% H5 X; N5 \1 C( i) T        for (int i = 0; i < 16; i++) {
0 T5 w; s# i2 ?: S            stack.push(i);
        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();

        //第二次入栈:压入16-31
  {5 f' a' O2 z0 @9 @& I# @2 c        for (int i = 16; i < 32; i++) {
$ o" p6 r. k) w  }$ ?8 I' i            stack.push(i);
        }
2 n' _6 c3 e0 ~- Y6 P. e% V        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //第一次出栈:取出31-16
! j0 \9 U$ Q: ~! `6 i8 y9 `' P        for (int i = 0; i < 16; i++) {
            stack.pop();
! {& ~% m( Y6 Q0 y2 A        }
7 A) i, J$ _8 q        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
& H: W! A5 n, e' b        stack.traverse();
+ ?2 Q2 h7 q7 e1 k& r$ F1 s* t
        //第二次出栈:取出15-0
& p1 Z1 z" U- J! Q* F        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
5 D7 V( g0 K+ F2 z& S        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
7 X" @8 P) R# ~" W5 @4 X        stack.traverse();
, [: h" P  Z( B4 K
        //栈中无元素，出栈报错
1 b5 U* I8 B& |        stack.pop();

% ]) R) d! [* b8 F, {7 E4 `% O5 w    }
( e. W0 ]2 d1 \4 A! N1 t}

3 l5 w  G  i/ S8 {! j

  `) T; s5 i5 [! ]
三、 用数组实现队列1、队列的接口定义
/**
* 定义队列的接口
*
' J$ c" `( }0 u0 z9 e- T* U0 c * @author zhuhuix
* @date 2020-05-01
*/
9 t3 q' w4 y( M+ l! P: cpublic interface Queue {

  s+ }" ^! j2 h9 M7 ]    /**
     * 获取队列大小
     * @return 队列大小
     */
, r4 k2 U9 y) }. @    int getMaxSize();

    /**
- ?" {3 I1 n* B  c' I! Q2 A     * 入队
" @0 U$ L  R& t+ K6 M/ r# a     * @param object 入队元素
0 P+ L: H+ ?- U# r! N' D3 v     */
    void push(Object object);
* [7 `% S3 v# F5 |
* r  g$ P, @- t: t0 H# ?0 T  H) Q# G    /**
" X! K) u7 x7 w$ \/ a6 |+ C     * 出队
     * @return 出栈元素
8 s& R; \$ u* w" \' W: d* _+ f$ J     */
) Q+ _9 {6 a5 I  H% `, e    Object pull();

    /**
: a5 r9 c6 z" X     *  获取元素个数
     * @return 元素个数
     */
( B2 f9 |8 Q- S% u. C    int getElementCount();

    /**
6 ~( u* d9 F1 H) K3 O     *  获取队头元素
     * @return 队头元素
     */
# m0 F1 F" {3 `8 l    Object getFront();
1 j5 O! [- E7 r8 W) I5 P$ _+ X
7 b& L0 P0 W. ^; Y& d$ @, h9 R. E    /**
     *  获取队尾元素
( D7 Q) J  d7 T     * @return 队尾元素
     */
# L4 S2 r# j) W) ?1 O. f    Object getRear();
" ~( P$ O, }+ K  Q) ^
4 V* T7 i6 \& W    /**
     * 遍历队列的元素
  I0 y  j5 x8 d# N     */
    void traverse();
" M6 ]) f- u$ S( z9 t+ |" g0 q% ^) z0 u}
2、队列的接口实现
8 B2 q* [( K' p3 _0 Y6 [/**
* 队列的接口实现
*
* @author zhuhuix
; b0 n0 e4 s0 N* p5 _  N7 Y * @date 2020-05-01
*/
. S1 ?) X* q9 Apublic class QueueImpl implements Queue {
) W# _/ T! B6 V8 f( f6 R9 W
" m& N% r: t7 Q    protected Object[] element;

% X7 }5 _7 ^2 D    protected int elementCount;

    //队头
    private int front;

/ Q; N% v' G% d    //队尾
    private int rear;
& q# ]4 b; A5 ~- m
2 G: S9 t4 m: @) R    private int defaultSize = 16;

( R: ^+ q& s$ n    private int maxSize;

& s! E/ Q% Q9 C    QueueImpl() {
; r1 l  _( a. b$ l/ u* {  m7 h* t        element = new Object[defaultSize];
7 i+ j/ m  e# D" T. w. Q/ e) @        maxSize = defaultSize;
        front = 0;
        rear = -1;
8 {8 z  w* }/ s6 y4 F    }

    QueueImpl(int size) {
, v, J; F% S9 T4 j* ?        element = new Object[size];
        maxSize = size;
* x4 \$ x! o& ]# ^$ |3 C        front = 0;
" x# m+ R1 s3 S& Z% m8 a        rear = -1;
( A1 J' V  `1 j. O7 j3 `( d" |/ W7 u( q    }
. U9 w% j# }- E2 x+ C' y5 j
    @Override
3 X8 G+ u; l7 f+ S0 x    public int getMaxSize() {
        return maxSize;
" X  j8 r5 i3 C5 I# H4 D* P2 t    }

    @Override
" o8 f/ P. g( h) t* j, J0 ^7 ^    public void push(Object object) {
3 S4 ~& o; B$ ^* T7 k        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
        element[++rear] = object;
        if (rear == element.length) {
            rear = -1;
; ~& G) B& F! |9 L        }
6 e% Q5 }* J8 O6 {% f) a. R' [* s        elementCount++;
+ S; d; ~$ E& r# I* J8 G7 ^: ?    }

! T- j) P7 x" F8 _4 b- {    @Override
    public Object pull() {
        if (elementCount == 0) {
# O5 `) g4 Z: c9 P6 _# ]1 }% E            throw new ArrayIndexOutOfBoundsException("队列中无元素");
8 i+ n( \5 I. e' k: @. P. c        }
) N& E7 i+ i. I' X7 E) p4 s        Object object = element[front];
, x# L, M( j1 t. R; W8 H' E' n: d        element[front] = null;
        front++;
- {( C2 J/ f9 T        elementCount--;
4 f4 ]5 o" N4 K8 B" M, [        //队列清空，队头队尾恢复初始值
* k& k& g: D5 l- R% C2 C, C        if (elementCount == 0) {
            front = 0;
' z) `4 x8 x: n            rear = -1;
! a$ H; c5 I% C        }
        return object;
    }
6 c, \' q* q( u* [6 |( a
    @Override
7 k& p0 K( k6 }" w. o; A    public int getElementCount() {
. u/ g$ A0 v  v5 @- z' g4 d: p        return elementCount;
) {" r. W2 o2 E3 i" h7 a    }

    @Override
  ?2 Y% k8 }9 }: h7 |6 m    public Object getFront() {
        if (elementCount == 0) {
* E& m6 k6 i% c2 g            System.out.print("队头无元素");
            return null;
        }
+ u5 T! e0 n2 ?: o! R8 d        return element[front];
    }
; Y7 d6 O& F6 [1 L% B7 Q
0 @$ p, P+ N0 `$ m6 L, Z    @Override
  {8 y. i! u% H7 U, W, I. [    public Object getRear() {
% c+ Y4 M" ?1 [4 R3 O        if (elementCount == 0) {
! i! O1 ?9 _" w  Q. Z            System.out.print("队尾无元素");
            return null;
, V. c6 R1 m/ d+ [% _% M+ h" j& N        }
        return element[rear];
5 ~/ q) Y8 d  j6 L    }
8 Q/ x9 A. U8 `5 ]3 l4 M
    @Override
$ ]- B( k$ E$ b# p( h0 u    public void traverse() {
        if (elementCount == 0) {
            return;
        }
8 s3 O/ a, p! F        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
- ~# H8 n1 U; M: J        }
        System.out.println();
' V2 q  a0 r' B- F& y    }
}
/ x. [! B' l% R2 b, U+ |

3、队列的测试
public class QueueTest {
/ M7 M9 b# G& ~/ V7 I" H' [- ^    public static void main(String[] args) {
( z4 P6 d; D: ?% _" A  z2 ^8 A% E        Queue queue = new QueueImpl();
' a" a) i+ v" W
        //获取队列大小
6 x) n4 T/ P/ A, H! F" L3 ~$ ~        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

/ ]' X% U: S7 @+ a4 X8 N9 }        //第一次入队列:压入1-15
7 P, d& n! o: V, Z- W        for (int i = 0; i < 16; i++) {
            queue.push(i);
        }
) y) f5 `! j( i; w0 t% x* K# k        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
+ s" l" t$ f( Z8 ]# U# [( v% Q        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

        //第一次出队:取出0-15
' X: F7 s. N8 V        for (int i = 0; i < 16; i++) {
            queue.pull();
  f* G  |2 z4 E# I$ w7 h& Y- o        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
% C1 P$ O$ `8 h- X" e2 a# Z6 `        queue.traverse();
3 \  S4 p0 [& q( f3 S8 O  G7 o  ]        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
  _& G$ E. l/ Q. ~( i

. {7 \- \% d5 a1 v( V: q        //第二次入队列:压入16，31
6 p4 o  i1 c. y$ K* c; x8 i% M        for (int i = 16; i < 32; i++) {
            queue.push(i);
$ A) \( j  W; R1 Y) D        }
% P( F) I' _/ w8 e6 ^- z9 Q        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
' K! i4 j8 b+ P( B; F# V4 H9 L5 {) f

        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
! Q8 W8 U8 w) x8 t6 ~            queue.pull();
9 w' x7 J5 @1 ~8 ^: n        }
# w* ^; D' b7 n: Q) d. ~        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();

! o! p8 k' U0 U- E# R& [        //空队列出队报错
3 L( Y2 r- r/ x1 j        queue.pull();

6 |( \1 q' x! T/ P    }
}



0 ]% g% O/ a/ p4 K
4 i% B( A3 }  _" _5 b' j" S

8 F% j& ]% y+ s  T' r: I, W
+ c2 [. [" Y2 a% G$ J
" e2 q' o4 H, A1 i% o


0 N9 ?3 w$ g8 s5 G* H
  U* h7 K$ T* |" I


3 o% X  d/ n& q; ~  l' k9 `————————————————
3 I! r; U9 `7 |- ?: D! a- C8 c3 M版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
8 ^7 E: L- e  o. ?4 K) Q原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785