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

杨利霞

( K7 z$ B* y2 l2 E1 [% y; t6 }数据结构——栈(Stack)与队列(Queue)的手写实例

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

$ j# W/ X* a9 b0 g, O* r/ Y  I! L( C
• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    ( j# h) ]7 I- `

/ C$ U5 J" N3 M9 m! E
% ~, k$ Q7 A- n: D一、 栈与队列的定义
7 E  p, X# c6 d5 c; Y) X栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
5 T6 Z* a! @; J- b7 n
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
. m7 w/ ~4 J- T& k$ j9 L) p

* o4 R) {3 `" }2 y. q
二、 用数组实现栈1、栈的接口定义
; o* X6 t* j9 f( j$ k8 ^! C% D/**
* 定义栈的接口
*
- |6 V6 V0 \' E * @Author zhuhuix
. b5 N7 G6 q; @& z * @date 2020-05-01
1 r/ H+ ?( C3 y- n* |/ p */
& {1 A* B8 i5 ^- E* `3 {public interface Stack {
    /**
1 g& a3 f& K' `7 c3 S     * 入栈
! D, x! V2 ?/ t, C     * @param object 入栈元素
; z" E, ^8 [; O2 `     */
* z+ t( R+ T9 p3 K: k% S8 |1 F( q    void push(Object object);
8 o; x; w# S) C
) P4 g% p8 ]4 q6 O: r! i8 W    /**
) }4 H: T% K  z; M2 r     * 出栈
     * @return 出栈元素
' M6 E2 L) ^. z; g3 x* G! X* Q     */
    Object pop();

  |. f- z2 F) w    /**
     *  获取元素个数
* ^: f( m  M% P& I. I4 e8 p) O, `" Q1 b     * @return 元素个数
* H2 F2 g+ v, |. i' ~% R     */
    int getElementCount();
+ \+ q0 W* O' V4 n8 _1 S& w
+ |* {* v9 t' ^' @    /**
     * 遍历栈的元素
/ |7 }; p3 y+ G/ [  Y7 B0 m  s     */
    void traverse();
( {+ G  g( J! v
}
) s' \; n; Y" t% F1 g; Y# U; y- U3 U3 p2、栈的接口实现
6 i$ r& F9 T- s# d/ `4 Z/**
* 栈的接口实现
*
7 a9 D. C4 M' a4 q * @author zhuhuix
/ @7 d0 m% G6 T. K: u: @2 u! V) e * @date 2020-05-01
*/
public class StackImpl implements Stack {
3 y/ U& W; ~5 O3 ]( X; w       
9 T) x) I/ S% o; [- G) b    protected Object[] element;
8 T) c9 ?9 _" y( X! s/ c8 J
* _/ |3 e) r) ]4 c9 m    protected int elementCount;
: h) O  Y1 |2 \
    private int defaultSize = 16;

    private int maxSize;

    StackImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
    }
  a- s0 V2 m  _- \) P' F( @" @
3 M0 o- z# W: z& G. D* n    StackImpl(int size) {
1 E/ [  u, `, V3 g% U        element = new Object[size];
        maxSize = size;
    }

    @Override
2 a! F7 k; B( O8 Y) c    public void push(Object object) {
7 h7 n3 }! V; l" U$ D6 ^+ _: s. O5 }9 P        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
+ O8 v0 Z" u+ N; Q% Y- B1 d            element = Arrays.copyOf(element, elementCount + defaultSize);
4 C3 |. L: X6 W; J* Z        }
6 @* ]( e9 j. S, I& ^0 d        element[elementCount++] = object;
  j5 Y8 z7 k1 J$ N2 z+ O% {5 o
6 Q: [# c8 e( F4 r    }
  V% }. `( |4 J( t        // 本代码未实现数组的自动缩小，具体方法可参考JDK
1 y; G+ x# E1 W" Q( I3 k6 m1 y    @Override
    public Object pop() {
6 v7 V% I2 J: O* i5 R/ d        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
. V' |: C' P1 O% F' L' F- O        }
        Object object = element[--elementCount];
: \2 ]# Z) B$ e. J0 i        element[elementCount] = null;
        return object;
    }

- C. i: Z4 t5 y+ ]    @Override
    public int getElementCount() {
) p/ o* w1 d' ^% X4 A  k        return elementCount;
0 b, p' Z/ ~/ D/ Y) C0 B; w' C4 K    }
! o. p: G; @! G% P
( [( D" Q; a. y- q    @Override
    public void traverse() {
8 a, l6 a  P3 a) s0 c; b        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
        }
5 ~& n/ S6 C- X% K6 ~$ G        System.out.println();
    }
1 {* d7 ?- }+ k- w8 t  ~6 O}
/ L6 Q, t, t, @% |9 Z3、栈的测试
- n3 Y. ~) [) G9 O$ Ipublic class StackTest {
    public static void main(String[] args) {
        Stack stack = new StackImpl();

! e7 d. X3 S' I& H/ @+ G5 e2 \% U        //第一次入栈:压入1-15
" I! A2 Z# g$ l        for (int i = 0; i < 16; i++) {
            stack.push(i);
9 ]- l& |0 K, l        }
5 C0 `2 O% t1 L. y  z        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
. H+ H5 j4 ^1 O0 T% B        stack.traverse();
8 q3 B* j0 T- `/ W
        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
* c" Q: s3 i- o' K0 k- S            stack.push(i);
( {9 S: T5 B( E+ d8 x" A. @        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
: @. w2 X  c% k& l2 O+ ?- D" I        stack.traverse();
* T( o2 ]( [* V/ s
0 N" w+ n! Z2 z8 p& j. `        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
            stack.pop();
8 p# y5 K3 d4 v- M, l/ C        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
8 C! F* U/ U4 o! g        stack.traverse();

        //第二次出栈:取出15-0
5 P! |7 L' C1 ?4 M1 \2 r/ b# A/ {, N        for (int i = 0; i < 16; i++) {
            stack.pop();
3 T& ]9 L! l# ]# y6 t" V        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
* l7 O9 U4 z! t1 x( A1 m. b
/ m/ ^1 @# N" P& W! _; u        //栈中无元素，出栈报错
        stack.pop();

    }
1 G2 Z! w! {& z5 F}

6 M0 U3 m: D, @; r$ g9 j
; E4 M* p9 c; C( `- K( G3 E
; R) H+ |; c4 t% q. v5 S$ |
三、 用数组实现队列1、队列的接口定义
% D3 r, w- u& M7 `1 o/**
* 定义队列的接口
, m3 P9 y+ K7 _. m5 h *
* @author zhuhuix
* @date 2020-05-01
, L7 S7 x1 ?" x0 x */
0 u* `' L! C5 \0 ]( ~) ~* |0 upublic interface Queue {

    /**
     * 获取队列大小
! x0 |' \. e+ k% D6 H1 m     * @return 队列大小
     */
    int getMaxSize();

' s5 V8 |* [. `# A4 I    /**
, `- K. \' A# W+ h     * 入队
/ j5 E0 E: u2 R     * @param object 入队元素
     */
5 W8 N$ w9 r+ q    void push(Object object);

4 k; \4 J# _8 |1 q' Y) n( _    /**
# ?  x* F- p7 l: i) L$ Z# [     * 出队
     * @return 出栈元素
7 w1 L6 C* A$ B, }4 P" B     */
    Object pull();

    /**
3 }& a1 |  c; ~5 u& `     *  获取元素个数
     * @return 元素个数
     */
* |4 M# H$ W5 l6 ]    int getElementCount();
8 P/ m# ^, V- C1 c9 ]% n
    /**
- x6 ^" c! M$ c# \8 o+ B     *  获取队头元素
3 J) Y" s7 j9 {- O7 H& T! t     * @return 队头元素
. Y4 h% }6 {; F5 b5 Q3 _0 L8 e$ O     */
4 {" [& E+ g! ]/ J    Object getFront();

    /**
: u2 C3 D) q  S     *  获取队尾元素
     * @return 队尾元素
     */
  R$ F0 s( U/ L# g' H    Object getRear();
' I: X8 N3 c. H8 P" d- h
5 o+ B) R; t5 \: y) P% }  ]: H    /**
     * 遍历队列的元素
; e! N- |. ~$ H8 @/ O" i7 ~     */
    void traverse();
}
& a0 |9 ^  P6 k+ B, c1 F! g2、队列的接口实现
/**
+ A9 x0 b  q& A6 p0 v* u6 S5 O * 队列的接口实现
1 @# D' C1 M" L& z! |4 y *
; }% k* B( p6 a* b4 p * @author zhuhuix
* @date 2020-05-01
/ |, R* ~) W, U$ \ */
public class QueueImpl implements Queue {

" N  }2 I% v+ X    protected Object[] element;
. S; u; m' \( |5 I7 M
1 J* t, x* X( }7 j$ N$ a    protected int elementCount;
6 L' B: W/ g0 O9 W5 e
    //队头
9 h6 H! N3 I( E2 L    private int front;

, O9 b/ v& b/ J, o    //队尾
  X4 }- Z. Q6 J) m, f    private int rear;
7 @5 a( _3 k0 |6 \* ~6 n7 s
" o9 d4 I, v% }! ]4 Y+ o    private int defaultSize = 16;
7 R! V0 o( y. y3 p
3 @& z* R& i+ O6 Q    private int maxSize;
5 M4 h$ y: P' v! f0 w- v4 h
  L4 g. l: E3 q- B# H    QueueImpl() {
        element = new Object[defaultSize];
. H, V. t8 {/ S' A0 G        maxSize = defaultSize;
        front = 0;
: f0 c; z/ ^- y, K5 C        rear = -1;
    }
1 K" K5 t# W) d9 Z2 n2 Y( d
    QueueImpl(int size) {
        element = new Object[size];
  v7 M- z# d) ^) U$ }7 w# ~        maxSize = size;
        front = 0;
, ^; Z4 ^& H8 M, R1 [3 g& W" i+ k        rear = -1;
8 v4 j5 M! d/ `+ B0 k& ^/ F    }
7 f  h3 A. @' K! x
! I5 y) p# N0 Z+ \& n5 m! Z2 W    @Override
! c5 R& h( \$ Y: [  x    public int getMaxSize() {
        return maxSize;
* ^- J3 L8 I( R+ D+ G) E    }

, X1 @* d8 }2 N$ T0 ?4 @7 J    @Override
    public void push(Object object) {
; l6 C6 u: s6 j9 q/ @        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
7 H) ^9 o* U4 n8 l4 H. z( w; G2 q            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
        element[++rear] = object;
8 n" w: ]9 ?) T4 l1 N# B        if (rear == element.length) {
+ O  B6 t3 T) _% |+ S            rear = -1;
        }
        elementCount++;
. H" n) K/ m# Q) J    }
2 K' L; i: y# \* Z2 f) u
    @Override
7 w) v( f& U  w    public Object pull() {
        if (elementCount == 0) {
4 B, j0 Q4 k( H. R            throw new ArrayIndexOutOfBoundsException("队列中无元素");
" J& X5 O4 o% Y7 U9 I0 M        }
& h- f9 b6 ~1 m8 G3 Q' F0 x        Object object = element[front];
7 l5 x) S1 G' q0 k        element[front] = null;
        front++;
" M  y  g( E6 w$ G9 p, C! L3 M        elementCount--;
        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
            front = 0;
- J) n. A7 ?% t" _3 ~. K  G            rear = -1;
. P  a8 q& i9 q* t# b. c        }
+ R( j& R# [+ L# S# k4 E0 E5 e# o        return object;
/ r; q4 j$ o* Q( b, {$ \6 ?    }
2 d# F# Q( O7 _$ {
& u9 l9 X* j2 _. i0 F9 l* s8 U8 T    @Override
    public int getElementCount() {
* M! s# A7 q3 ?- W6 p- d$ r+ E        return elementCount;
    }
! _, {# o+ J1 h+ u4 m5 G! o
    @Override
    public Object getFront() {
        if (elementCount == 0) {
$ A. I% ^* K5 l9 j9 F            System.out.print("队头无元素");
            return null;
2 X9 V0 a, C9 e8 p        }
        return element[front];
# K+ \! ^! C9 ^9 n; O    }

    @Override
    public Object getRear() {
        if (elementCount == 0) {
: X! T: ?  {# {- r" ~            System.out.print("队尾无元素");
3 e! ?/ l/ ^2 d            return null;
- O- S2 n8 z$ \8 x! i: y1 M        }
9 V" A% o9 u9 ^9 R/ Z% o        return element[rear];
    }

- |1 `4 a( F0 M0 M+ }, E1 u    @Override
2 W" L' [+ H; d7 `* G    public void traverse() {
        if (elementCount == 0) {
; c. M9 c: E/ D7 J, s            return;
. d+ k8 r" ~" T% M, W! w- ~        }
0 H* M0 U" H, C5 u# E3 U4 `        for (int i = front; i <= rear; i++) {
8 X0 z# y' B) p6 O3 e            System.out.print(element + ",");
        }
        System.out.println();
    }
( L& o3 j' c! ?8 z7 Q9 R/ E}


3、队列的测试
public class QueueTest {
    public static void main(String[] args) {
4 S; c( ?- j3 P6 N, n$ @3 \- M        Queue queue = new QueueImpl();

* V2 g) z7 D* y; f2 M, G        //获取队列大小
; K8 ], Q* K: w2 {6 x* k$ k4 \$ n        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
            queue.push(i);
! ^- a3 R) n7 S2 y. D, c. |+ G$ }+ o        }
0 i+ B4 ?3 s) H. W' b$ q8 ?% b        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
, Z6 \6 J. i9 f* c
        //第一次出队:取出0-15
# \& O  M& w1 ?0 g1 v/ z        for (int i = 0; i < 16; i++) {
2 I  K+ w( {: }3 s2 _$ ]            queue.pull();
. d3 J4 m, `* f% e1 ~5 b        }
' u/ A0 ~. g/ w        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
1 [1 M+ O0 F5 k* W5 z( T8 Q% P# {        queue.traverse();
9 V9 L" i4 V3 M+ Y        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
+ A1 \  H, A$ E" N, l+ q6 r4 ^

        //第二次入队列:压入16，31
: A+ |+ @" j. x0 D        for (int i = 16; i < 32; i++) {
. L" y: N7 R$ O$ \7 s            queue.push(i);
5 k( Q/ \7 C" f4 H! Q! b% F        }
! a+ ~# \# q( w) \6 D        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
  k' t( V% [4 Y0 ]8 i        queue.traverse();

2 N0 l- q* Y2 O  X
        //第二次出队:取出16-31
: w% [. u6 s' H% }$ {! {$ ]        for (int i = 0; i < 16; i++) {
            queue.pull();
3 p! H% t% [& [4 [        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();

! h8 p$ T& D( ?        //空队列出队报错
        queue.pull();

; M4 b; Z+ _1 u; R1 E    }
}
) m+ K$ A' a  u( m

. {1 C1 y6 p, g$ J3 W3 b7 e9 X

/ s- u; B8 ?' P$ u  e

/ Q7 x( V& Q, I6 _# J


& b, m+ F+ \+ ^, d4 X! S5 M
' o: h9 i" a3 K$ [




# O" A; |5 V7 `* z8 q————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785