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

杨利霞

. l2 t2 D6 D$ c6 P' [数据结构——栈(Stack)与队列(Queue)的手写实例

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

• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    0 H! |# J+ l, c6 c+ _3 M
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

5 ]( y* \* a2 Y* _2 p
! ?7 R2 A) u( l, I- U2 u- R一、 栈与队列的定义
( V# x9 k; P) H) a栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
9 M9 K' F: x: e( R& I4 [0 t7 U
. Q' ?% M4 y5 n# \) o　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
, }# S9 D1 S5 s( i9 h3 R

- a( T4 j3 M4 w% `( {
: R' W9 B1 A9 U二、 用数组实现栈1、栈的接口定义
# z2 i* X4 Z6 e4 j+ V/**
- J/ R% d! X: R8 u) w * 定义栈的接口
*
" ?. L5 ?- R$ m* W+ t) @ * @Author zhuhuix
) s  q' O& c" ?8 G# X( U& c * @date 2020-05-01
: W, t4 u$ @, _2 p */
public interface Stack {
$ Y/ K! b1 d$ c& `    /**
     * 入栈
' x+ y; A8 E9 h1 Y. q. S     * @param object 入栈元素
     */
    void push(Object object);

    /**
2 C" I6 Y* C- x$ }  V/ e     * 出栈
     * @return 出栈元素
     */
  O+ j7 C" x7 `. X    Object pop();

    /**
- z' }6 ~. k- N/ _' @     *  获取元素个数
     * @return 元素个数
     */
) {$ \4 o, D5 @0 D    int getElementCount();
# G6 x+ `0 B, i* j
3 @0 Y/ m- j& O+ ~. v    /**
; e' H+ V* p! b' Q7 K; b  \  Y     * 遍历栈的元素
     */
* m2 A2 M# L5 ^7 e( k9 M    void traverse();
% {/ `) g( w5 j7 G0 A
7 \9 F$ ~- p. z! O* g( K$ D- A}
" K! {9 f) f2 N4 R2、栈的接口实现
# n3 i1 R$ c9 k3 R/ z5 q/**
* 栈的接口实现
*
* @author zhuhuix
* @date 2020-05-01
*/
public class StackImpl implements Stack {
       
4 p) Y/ M- q$ i. `, E' [    protected Object[] element;
' A2 x7 W4 @- v- D0 s
' g$ ?; A0 c8 X- N9 U    protected int elementCount;
0 B" ^) D- ~+ T9 H* H
    private int defaultSize = 16;
% _1 E5 {# O% G. J
; V* s/ c; c9 G. q    private int maxSize;
8 ]2 f5 t2 L( P; B
    StackImpl() {
9 q# S0 i5 q" [        element = new Object[defaultSize];
4 D: G! Z: y7 E2 f3 I        maxSize = defaultSize;
" x8 j) I) j2 K/ U    }

: y& K4 W0 O' K: F6 O$ h    StackImpl(int size) {
        element = new Object[size];
0 x; J1 Y  B/ F* y) @7 C  s! B5 |        maxSize = size;
    }

    @Override
    public void push(Object object) {
! n9 T8 a: U8 Z6 F        //如果元素个数已经达到数组的最大个数，则进行扩容
# L# u: G5 d* `+ m% N        if (elementCount == maxSize) {
6 X4 K5 b7 M9 x) C& |6 n0 v            element = Arrays.copyOf(element, elementCount + defaultSize);
' x2 O% A, a* t% g- u' }        }
        element[elementCount++] = object;

8 U; X% F& U# k- D4 N8 u8 f    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
    public Object pop() {
        if (elementCount == 0) {
" [. T8 K! \# h! S; F7 m+ k" M            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
        element[elementCount] = null;
        return object;
    }
8 v- k9 O) e% b. A: q- x
    @Override
    public int getElementCount() {
; h% a9 z( u0 u' C, l9 V        return elementCount;
& h& w8 p  U, M* s* h' T( o    }

" Q5 s, K. ]9 Y( J8 X    @Override
' R( _+ D8 }8 j7 o+ S$ Q    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
. j2 T$ k6 \$ d            System.out.print(element + ",");
$ P9 n9 D: D8 e1 K+ H% F; \) e        }
+ {3 R& G) [1 R7 X5 v        System.out.println();
    }
; U8 k6 f. g2 K& d$ V5 J& W}
9 {1 j- P8 \3 ]1 I3、栈的测试
public class StackTest {
    public static void main(String[] args) {
        Stack stack = new StackImpl();
6 b" G1 K, n/ O8 T! U
/ B) G3 t# W3 {3 W# e; O        //第一次入栈:压入1-15
0 y- h; ~' N* B5 N# R        for (int i = 0; i < 16; i++) {
* c- U" v, C; H. ]- I            stack.push(i);
        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();
3 X! f$ {- L, v+ q, N
3 ^' t" B6 K3 V( _  w: J        //第二次入栈:压入16-31
8 c! l2 K. G+ k( P7 K" Q        for (int i = 16; i < 32; i++) {
            stack.push(i);
        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //第一次出栈:取出31-16
# [% N; V) t* F2 B        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
, G1 m# U1 c. V, Y        stack.traverse();

% x5 e: ~( d- H& n; J( U- t1 L        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
" y% e) g' A( T) h, M. _. ?6 d' a
( n8 Q, q# d4 Y2 p        //栈中无元素，出栈报错
4 `9 o% `% }) k# U1 Z2 w' O9 L        stack.pop();
" y) @+ p" T0 _1 ?6 K
/ @% I* n& d& V! T    }
5 q2 A3 ?! I  i$ Z8 l6 d}
* a! ]) W( B) n9 V: t* \+ v( K& m
2 y6 |- P# Y% |. g5 Y. N, d


) W. C9 z% H7 B三、 用数组实现队列1、队列的接口定义
/**
, [, v: C/ \7 n; ? * 定义队列的接口
*
* @author zhuhuix
* @date 2020-05-01
6 _( M- l& W4 W2 ` */
public interface Queue {

7 k! R2 Z2 R5 M8 e    /**
     * 获取队列大小
, O3 a' _# p2 l3 s5 U, w, B* v0 u     * @return 队列大小
     */
6 C: @" h) T  e' j6 A+ Y  j3 f1 |    int getMaxSize();

    /**
     * 入队
, E+ @/ ^: _( _" `" [0 y     * @param object 入队元素
     */
    void push(Object object);

    /**
5 T7 m* O2 U& S3 t     * 出队
     * @return 出栈元素
     */
    Object pull();
' O6 E* V& D9 [/ T
    /**
     *  获取元素个数
     * @return 元素个数
     */
    int getElementCount();
& Q, g, j# y' C
    /**
; n1 N+ x4 v0 T) [% m; k     *  获取队头元素
     * @return 队头元素
     */
    Object getFront();

8 `* ?& s$ P+ f; @+ S, D    /**
     *  获取队尾元素
     * @return 队尾元素
     */
    Object getRear();
$ _: H9 {) S; M6 \
    /**
     * 遍历队列的元素
7 H0 @) X  C! G9 s     */
* L) V; n9 [/ k* l8 d' m5 W1 k    void traverse();
0 L1 T# i1 M* Q1 M9 m; _}
2、队列的接口实现
/**
* 队列的接口实现
/ q; V; e( ^9 H& k+ X; V *
1 K) p1 }4 K7 ]( p' b. c+ x' ] * @author zhuhuix
0 X3 s% \" d% `5 ]1 |% \) d" e * @date 2020-05-01
" F3 l5 z  ^& d9 Y$ Z1 C */
. c! x& L/ t" Ppublic class QueueImpl implements Queue {

2 U5 X4 P% _/ x2 e    protected Object[] element;
0 _, z6 k7 c9 m9 X* [7 y
, B( h' j" u" H8 K: t0 _    protected int elementCount;
; Q& N/ S: W6 N& u1 H
    //队头
( }. l( d: o* C    private int front;

    //队尾
    private int rear;

" _4 @. j8 f* c    private int defaultSize = 16;

  z4 S/ W# Q  [5 p* o    private int maxSize;
3 A( L" E( h4 I
    QueueImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
        front = 0;
        rear = -1;
    }
8 E6 v% V1 }$ ^7 G
    QueueImpl(int size) {
( ]. C) s/ W9 }8 u        element = new Object[size];
. A2 ?% J: C/ u9 R; Z" O- o# V        maxSize = size;
4 w$ s* X* O# ~# X        front = 0;
9 `9 b) h" Y  W: z; W        rear = -1;
2 ?5 M  P" _# {& b2 s! m    }

! n3 o1 u+ _- f, h" C  v& M    @Override
" u9 D# J/ Y, ~; u& ?5 Q$ b    public int getMaxSize() {
        return maxSize;
    }

    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
  T& H( v" ]1 X, r6 G        if (elementCount == maxSize) {
5 {+ k% \: A' G            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
        element[++rear] = object;
        if (rear == element.length) {
            rear = -1;
        }
; C3 k# q7 j# v( f/ M3 ~) y        elementCount++;
    }
  Z; H) q* Q8 k- q$ P7 _" |5 Y
: Y: \: Q) z% t6 `5 l/ M6 f* @6 W    @Override
9 e. k8 j- S) h% d; V' D6 v    public Object pull() {
        if (elementCount == 0) {
. u9 e# K# Y# K            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
        Object object = element[front];
8 s* c! U5 s& B& @6 {8 ~1 W2 h        element[front] = null;
        front++;
8 O( w" H/ |: H, S7 ^8 \/ D* k2 j        elementCount--;
$ \. W8 G$ \+ S8 r        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
1 b7 u7 h5 V8 ?3 a) d            front = 0;
7 g) P0 Q4 _6 y% n7 u# J5 f" i            rear = -1;
- ]. w+ G. J$ z, w% o4 a' e, h4 F8 H        }
        return object;
    }

    @Override
    public int getElementCount() {
        return elementCount;
% ?0 a+ T" n7 B3 I    }

5 F5 t) o; `( F) r4 J    @Override
    public Object getFront() {
3 J( N+ t$ N+ ]! q/ x3 r        if (elementCount == 0) {
% j* M, a* A; E0 q" B            System.out.print("队头无元素");
) d2 [. j' ~0 L' }0 q! ]) s            return null;
        }
        return element[front];
6 W# M/ w/ C. P    }

    @Override
! O- @- X+ g( `* m$ M2 q2 s    public Object getRear() {
        if (elementCount == 0) {
            System.out.print("队尾无元素");
            return null;
        }
        return element[rear];
9 h/ y! Z6 [- f$ S  `7 A) H    }
3 G3 [# E; c) ]# U. h
    @Override
$ k1 L) T/ f, E& W5 n% q    public void traverse() {
5 a. I1 s6 |( `1 |, e/ I        if (elementCount == 0) {
2 U7 f: t, {& T, _$ O5 G6 J) z            return;
        }
        for (int i = front; i <= rear; i++) {
# V; h/ M6 F6 w; F  O3 d! m            System.out.print(element + ",");
; e7 v# H3 ]3 X3 ?        }
+ [# {* M2 e8 J" u* h0 a) \2 y, i        System.out.println();
/ Q! r" W( R  H# B- s, g2 v    }
}


0 {" c% p7 t0 R, p; \5 L$ T' ?3、队列的测试
5 M7 T  q% C: {public class QueueTest {
' S5 B8 l) g' ?    public static void main(String[] args) {
        Queue queue = new QueueImpl();

        //获取队列大小
, d2 Q* T% H* w6 ~+ q        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

        //第一次入队列:压入1-15
8 S* g" u9 r0 G$ m        for (int i = 0; i < 16; i++) {
            queue.push(i);
/ [  D3 @2 `" K9 |" o        }
. _7 m0 J9 E! R9 _# b& w        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
0 N7 `: H, z" t' W        queue.traverse();
7 ]* @' u9 N  [& H" t" @        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
+ Y0 h9 Z* v7 i) E5 Q
* \6 d. |- j( }5 m! u! I        //第一次出队:取出0-15
: O9 g9 v. ?3 h" @& P        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
. s2 p6 b( v0 m. l# y( E        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

% B7 {1 k8 f  e/ ]: G
2 L7 |3 h- m% u2 i  ]        //第二次入队列:压入16，31
+ @# Z, A6 Y8 V: o9 |  O" {        for (int i = 16; i < 32; i++) {
            queue.push(i);
7 a/ X4 V! I# |  T) T        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
& }$ n. r( I- T# \
" F& h$ v0 p# m1 `3 b. n" ]; K
        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
            queue.pull();
; t, @' A% d2 a/ x2 U  u6 E        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
3 K3 j- Z4 c+ H! I/ i        queue.traverse();

7 n, ~6 z7 _! Z( p, Y        //空队列出队报错
        queue.pull();
3 P! p  n1 F. |& N* W
, P5 g/ i) q' h4 ?" q. \9 n) F    }
}
/ G" P: v: x, Z  J! N



  W  B. v, \1 U( Q

: e; ~$ S+ {/ c& r/ P8 q3 I, x# K

2 h1 |/ J  o/ s$ B8 m- e1 \




9 e) H/ P; P, ~# R) d+ W
6 o  b( r" z1 E  `
8 d9 e/ E/ w0 B! C————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 r# g; o% Z4 V2 g. v5 u, a原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785


) n+ @- a" A0 J" \& E: b