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

杨利霞

- J! |' h5 t3 [' j* S数据结构——栈(Stack)与队列(Queue)的手写实例
0 j& B  S& i/ ^) h, M
[color=rgba(0, 0, 0, 0.74902)]文章目录

. Z2 d+ Y7 u7 r* A. N( g8 e$ m
• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  5 I/ |+ R* p6 Y
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    ) _; D9 ?) W+ d

( f  k& }! L  j; c( ]- ^一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。

　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
. D1 T) w& Y/ J, X8 D3 j( a
2 l3 `. }$ c  ~( y* d+ N
, i$ z$ l" f8 l! A7 p( z
二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
, x- b" V% t8 n- f *
* @Author zhuhuix
2 E/ ^: X1 |% ~0 y7 a * @date 2020-05-01
' A, W- _+ x/ G7 w+ b" Q% c: f# { */
public interface Stack {
    /**
, i, E* y# h6 h( c3 N5 A  `0 h; n  i3 _     * 入栈
     * @param object 入栈元素
' w8 B1 b- e( `+ ^% t     */
    void push(Object object);

/ g4 g7 G# W. i( N) _/ H9 ?( P    /**
6 l7 c9 z# Q' s7 l" Q7 e0 Q6 }: G     * 出栈
. }: ~) I3 H& {5 `     * @return 出栈元素
     */
( }, D+ v: \; }. {- b" ]3 Q    Object pop();
/ K9 |# s5 }4 D& O! o7 j/ Z
    /**
2 v  L+ C  U1 v3 h/ v5 ]' W6 w: W     *  获取元素个数
     * @return 元素个数
     */
; m0 Q* J5 n/ T" A% H/ ?) T    int getElementCount();

    /**
     * 遍历栈的元素
0 f: e: S, v. ~2 M4 O2 |: ^# z     */
    void traverse();

( [6 F7 M2 m* K  m) J# K}
2、栈的接口实现
/**
* 栈的接口实现
# ~. @9 `+ U' P *
* @author zhuhuix
' D. @+ o# U# }. E% `5 A! o: ~* y * @date 2020-05-01
*/
public class StackImpl implements Stack {
+ ~3 d& \% C) }0 e  q9 ]. f, q9 J& w5 s       
7 v( W+ {4 \, {2 j9 ~: L; ^* F    protected Object[] element;
5 v- @+ Y; i6 k3 V$ J$ }. C, `
    protected int elementCount;

+ y+ W2 K9 A* S( W4 W& b    private int defaultSize = 16;
/ F) W/ {4 T/ k6 q
    private int maxSize;

    StackImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
9 q( L$ ^, p4 J/ ]0 U7 |! y2 G    }
6 u1 J; s5 s  i. z5 I4 v
$ w* B: c% N9 O4 w( W7 ^* Y    StackImpl(int size) {
        element = new Object[size];
; C, _% x: j  T: E        maxSize = size;
9 }- ^& _9 [: {) G% T6 o. V) @    }

    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
/ r& N6 N6 }& P" X4 T) w" O        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
  z) R: R: R/ _1 l' d! u% d* O        }
        element[elementCount++] = object;
, G5 N6 a. e; B3 Z: d
! [) n0 O! k* V. ?; o* e: J    }
, E- c6 ~3 S. I  K  ]        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
7 B+ w) P% q# J8 s    public Object pop() {
. _( _% `& o% ?* b/ R' E        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
. \9 N( M+ }. P; S4 J        }
7 v+ N; u$ ^3 x+ R# `        Object object = element[--elementCount];
        element[elementCount] = null;
2 d# n  ?4 S  @7 v# ^( j; @4 f        return object;
    }
5 x0 I' e" o  p+ p9 {
! _+ o' ?! t+ C; f    @Override
    public int getElementCount() {
( D: H( z% F' C) v+ n) b: U        return elementCount;
    }
! a7 E. O+ h- m: y) [; K
9 F: `- |4 m. l    @Override
    public void traverse() {
+ j4 q3 e: y6 X: @9 v        for (int i = 0; i < elementCount; i++) {
) _, X& \/ i6 I* S! F            System.out.print(element + ",");
  s. T3 Z# |4 B/ V* W' J3 l6 k& L        }
        System.out.println();
( c( ?5 u5 ~% k( Q# r; \4 N3 \1 @* C    }
3 E# A( w  `+ x) I+ Q}
# m! K) t- [  b9 H$ D/ P1 F3、栈的测试
* w3 @. K$ Z( `" F( Ipublic class StackTest {
( j3 _" g! y% n    public static void main(String[] args) {
+ m) m+ z" u+ u0 m) w: @3 B        Stack stack = new StackImpl();
( J3 P3 D4 U5 t6 U
        //第一次入栈:压入1-15
+ X% I+ c1 C8 }& G; }3 z0 e        for (int i = 0; i < 16; i++) {
( j. `2 y- s% Y. L: m1 u            stack.push(i);
3 y2 S: _0 J0 l, }        }
/ T' j7 s. x. P0 s9 u+ R8 u        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
' {+ ]3 [# Q8 N8 v- f+ _        stack.traverse();
! Z$ P, U* v& I% _5 {% P4 J
        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
& G$ D1 D* l. n8 y+ U            stack.push(i);
! A' Y4 o. b6 E1 |# A  t) Z7 C        }
2 w1 u9 j1 I' r- G1 q$ ^% V        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
1 d! j# x/ r0 ^& f, _) j8 g
  j8 ^2 T0 f5 S/ A& ~' F: a        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
            stack.pop();
* O  @2 f: ~: i$ p* ]7 J        }
8 A/ E# p) B0 E- A. s4 p( A( a        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
4 O3 I/ a- m' @+ G- S2 e        stack.traverse();

" s" p: `; d' V& D( @        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
, ^6 J" \! @( y& k0 J            stack.pop();
        }
' {9 D, F" t2 }, x( L$ ]8 e7 U        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
0 l" U$ D5 K9 N4 v) k+ K5 Q        stack.traverse();

0 C- a1 x$ A% G% `2 R        //栈中无元素，出栈报错
        stack.pop();
/ n$ E) F5 G+ Y# a5 N$ h4 D# Z
    }
}




三、 用数组实现队列1、队列的接口定义
/**
) M8 {) I- Q& H, L * 定义队列的接口
) L# @% w# U% z: @# Y *
* @author zhuhuix
8 {0 m4 Y% u* _, x  C * @date 2020-05-01
) H+ ?  b; `/ {! o */
# v" c! W- D% H: A. h# B# _public interface Queue {

- b5 s  i. P. t/ R1 M    /**
     * 获取队列大小
     * @return 队列大小
     */
    int getMaxSize();
! }: F; m3 E. @
    /**
     * 入队
4 t1 h" v+ |- b& U4 u# @     * @param object 入队元素
     */
, H, L3 G  }9 n" O5 ?    void push(Object object);

2 T7 e& f. n! G5 D) X    /**
% o: |4 F% k4 L8 ]/ @     * 出队
     * @return 出栈元素
     */
    Object pull();

$ ^6 ]* k' _: }3 q3 I8 K    /**
     *  获取元素个数
     * @return 元素个数
     */
' I8 L2 ~! D1 ^+ W& ^+ U    int getElementCount();
! }' E" {  E" b* e8 W! z9 Q
) p' I1 K/ T( _    /**
2 ]  c" R. U& Z6 X7 t% D     *  获取队头元素
     * @return 队头元素
# M5 U1 U. v) \0 W$ K5 q# \1 [     */
- P$ ^* s) U8 _& p    Object getFront();
* ^4 c. z1 }( ?6 ?# J8 \  \
2 a8 s9 a: i3 e( U& |0 |    /**
: \! a. V( X' l; |, F: c1 H     *  获取队尾元素
6 l, ^3 \* ]; L4 f& i  b& f1 V9 T     * @return 队尾元素
. A9 }3 ~% \4 x* Z$ m) Y. |     */
    Object getRear();

) q9 K5 f7 M7 j    /**
4 N! I8 S( p5 n& M     * 遍历队列的元素
     */
    void traverse();
! G' g( O% @  t}
2、队列的接口实现
/**
. {/ {: |  @% d& S * 队列的接口实现
8 h% r4 }9 X# {0 |) y, c) C7 R *
  o" t8 S/ L* e1 O * @author zhuhuix
* @date 2020-05-01
*/
public class QueueImpl implements Queue {

% w% J2 i" E8 D5 g; [0 t    protected Object[] element;

    protected int elementCount;
. l- q) |1 o. J+ D) p
    //队头
    private int front;

( a  K- c$ c1 E; `2 L1 S  {& L) g8 }    //队尾
; k) U5 h; v1 N; p0 U! E2 `    private int rear;

: M1 \, q( e' r# F$ p* q( C9 b    private int defaultSize = 16;

8 g) r# ?7 y# C. c* ^$ s# q    private int maxSize;

    QueueImpl() {
  i! S: A5 `1 D        element = new Object[defaultSize];
4 F5 E/ }9 d% R8 {5 {: Z$ O        maxSize = defaultSize;
        front = 0;
        rear = -1;
    }
1 e+ G2 n/ s: U) {
  z* a3 T7 ~$ R  s! @3 Q/ A    QueueImpl(int size) {
        element = new Object[size];
2 C& w" F4 ]  m        maxSize = size;
        front = 0;
4 a9 y. X' ]+ |2 j, B        rear = -1;
    }

! @9 h- G1 B4 x! N    @Override
( l+ I. L- [! f; V    public int getMaxSize() {
- E; |) n  F5 F, _. i0 |! e$ u: g        return maxSize;
2 m/ m4 W: A0 u' B# X) H7 k$ B+ P( }7 P    }

9 m5 ~+ D- T( p5 ~* P7 n  t    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
; {$ e; J9 u  k1 H& R$ e1 T- N        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
- \' b! h7 ^* Q, N# K+ d        }
- M& T1 e, {1 H; R, J        element[++rear] = object;
/ T# x8 O- e: [+ P        if (rear == element.length) {
            rear = -1;
        }
  n( w9 c0 {. v        elementCount++;
    }

    @Override
' c2 ~1 M, ?# d* s    public Object pull() {
4 [: |2 y1 H1 T3 L0 H        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
; c; g7 p; T0 h  Z0 {# P        }
        Object object = element[front];
        element[front] = null;
        front++;
2 _& W  M' ]2 e        elementCount--;
$ E6 P% {! G6 p# d: m! `" ?        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
" K8 k* i% x0 ~            front = 0;
* D) d( u. a$ S! _9 H/ M* ^, f            rear = -1;
        }
  V5 _: J/ i1 b% o' |8 t        return object;
    }
; _, V; G; E; D, D. A5 L4 q# @2 \# E
/ v/ Y2 O3 @, w    @Override
    public int getElementCount() {
        return elementCount;
    }

    @Override
    public Object getFront() {
        if (elementCount == 0) {
            System.out.print("队头无元素");
            return null;
& e7 |! D3 S9 R( x. Y3 T        }
# U( I( x" G3 d, p        return element[front];
: U& i6 y) @! J$ }9 e5 \8 e" f3 ~) A    }
& m! K; z# T0 b6 O
# D2 X7 Z! o5 K/ ~$ o7 l; Y  L, I    @Override
    public Object getRear() {
+ d6 y. {* Q: N) G# {% f# o        if (elementCount == 0) {
+ f% _2 _2 y: r5 \5 y- p            System.out.print("队尾无元素");
, C) i+ W# [- ^# B/ N( E& U1 l            return null;
        }
        return element[rear];
    }
; w+ U& ^1 g: z, V4 A
    @Override
    public void traverse() {
        if (elementCount == 0) {
            return;
& {* F& v5 _0 R3 u        }
9 _: C& M& p: }3 x. L( A* P        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
        }
        System.out.println();
& u* G! X8 I8 }) Q9 y2 F4 O! w0 P( @    }
}
; F( [5 J+ a) J+ w! R5 B7 w

3、队列的测试
" n) J/ k( J; k; i' `) j: k& tpublic class QueueTest {
7 E9 ~2 P3 z' D; b; r& Y    public static void main(String[] args) {
. r! ~) J0 u; ^# D        Queue queue = new QueueImpl();
( q4 P8 E7 Q8 {6 z
* O# |# B& t7 T; \7 c        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

- z& U. [% a* W2 n3 R. U        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
            queue.push(i);
        }
+ \+ F, y" C' g: W1 n        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
6 Z, ~- A2 w# I: o& H$ @8 v        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
$ |# \5 V( i# p) d2 Z# h
' K. ~7 n, ^6 W/ m) l; y        //第一次出队:取出0-15
- Z* W8 q; M2 L7 o        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
$ Y' U/ o) L& l5 b) G        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
  ], \  |( u* p. o6 _
- w# o  d% y" j6 d* T) X
7 `! n3 K6 }5 J! Q' ?9 ?( i        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
            queue.push(i);
        }
1 b" m4 n- x- i* ^4 `0 @        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
0 x' j+ v- b9 S4 T+ P& }. B        queue.traverse();
& h$ `8 s; g+ k# _: p6 [
5 L" J( ?1 A  W. `% |* _) Z8 J
5 t) }( B5 o% L# u+ t: B, M2 R        //第二次出队:取出16-31
( Z8 v$ }' M) \$ e8 o( Y- d2 G        for (int i = 0; i < 16; i++) {
            queue.pull();
5 U% b6 t6 [/ l1 P3 ?' x        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
/ t9 J5 A- W# ^' Y; d  d        queue.traverse();

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

# t' w( Q* C. n) J, \7 @( D$ z    }
" q: }8 \) l' [) z+ R) a}
  f. c# z7 f0 y/ s8 T: q8 K" E


% X2 A5 v0 R. M, k1 D9 x* @
. f, t2 J' y  Z! ~+ {


9 w; ]; D( s& J- k# q( I* b, H
4 N1 Y2 y9 j/ u/ c$ S
! _0 g7 |0 C( j3 v* H" G5 f6 b: o
& M% i7 G5 ]+ m3 E3 J
" n6 Y& s0 Z: o) h/ P3 ?


( v: B7 ]  G  y4 ?2 p% n: e
# K2 m9 o& s- o! o: P; U————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
( `$ K/ F9 {9 Q

1 W8 Q$ A" @$ u" d2 W' h* t* e, x