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

杨利霞

数据结构——栈(Stack)与队列(Queue)的手写实例
; b; \+ I" r  h, b# k
. Y1 Q, y3 g1 S- S[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    ; H  V8 Y9 D& W( T& z* K# w
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

9 A" Y# u1 \' d
一、 栈与队列的定义
& v8 R& n* w! n. `# {  `* Y栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。

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

! q( k+ {1 k  p/ H& f
- {" u* ?7 w: P+ X" u! n1 T2 W
二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
*
8 G6 O* h& D! \- [- p * @Author zhuhuix
* @date 2020-05-01
*/
public interface Stack {
" [! _, D1 x& i% I1 O1 l% k0 O/ _, `    /**
) J! M2 x' F0 m: F6 Z2 x# U     * 入栈
     * @param object 入栈元素
$ U5 `) z: E, O% |# o     */
8 a  G: m  J' B, ?9 z    void push(Object object);

    /**
# q5 A/ v0 Y/ D' R  q' {1 P     * 出栈
# |- K/ O5 P- j4 Z     * @return 出栈元素
     */
: a6 K! t5 ]2 D# c2 o    Object pop();
( L3 Z' ^. j8 S( W
    /**
     *  获取元素个数
( |' F3 l5 o' t& [! z$ Z" p     * @return 元素个数
     */
    int getElementCount();

! \* E; T( G( x    /**
. v3 b# K4 Y- l) O) c     * 遍历栈的元素
1 V- q5 V5 L; i4 Q+ r% a7 N( I     */
2 R& R, j2 k; ?# ?    void traverse();
) e/ H8 m# n/ x! t' W8 E" d
}
2、栈的接口实现
/**
/ |7 O/ H8 I* i; b( e& b$ J; { * 栈的接口实现
*
! ^9 P8 f3 h+ U+ ?  G * @author zhuhuix
7 W0 _( z* z& @; d' }5 k: A * @date 2020-05-01
/ I% r' Y& |6 l( H9 ]1 X */
8 S  F9 u) X1 l5 [public class StackImpl implements Stack {
0 J9 k! U6 W6 Y1 n& b% \- E8 z       
; `' o+ F  Q- @( _9 N" ]    protected Object[] element;
. X6 h+ B+ i: v; H
    protected int elementCount;
: @5 H$ i0 c9 o; N9 Y' d7 i
    private int defaultSize = 16;
% _& i( j4 M5 P/ n" E7 w4 b2 n
    private int maxSize;
6 e) k; O3 E/ p$ u" z
; w/ L9 M6 i- O9 T    StackImpl() {
. S7 A9 Z( c# H; I2 q7 X        element = new Object[defaultSize];
        maxSize = defaultSize;
$ u0 i$ {  l9 C; W+ S- G    }
# ]' s$ n- g8 _9 i8 l' \6 f3 @
    StackImpl(int size) {
/ E, Z& q, ^5 ~$ n1 n- \3 D        element = new Object[size];
        maxSize = size;
    }

9 B8 f6 o) n2 n' A% s: X    @Override
    public void push(Object object) {
: R8 a2 G! e1 N: e        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
7 \7 x. t% P, Q$ o1 f( r9 o/ W  C            element = Arrays.copyOf(element, elementCount + defaultSize);
6 r" W8 n( b# A4 h) W        }
& Y3 ?( W. I9 q/ t3 S0 C6 p, ?6 K        element[elementCount++] = object;

0 ^: n. u/ d( ]: M1 s3 d    }
0 F0 F& C$ ]" L" {" ^7 d4 T* e# z        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
3 U6 }4 N( d& b2 q    public Object pop() {
/ X; M3 u: Y: x+ H& D  |        if (elementCount == 0) {
8 T/ ]1 G9 v, }' n* ^# G            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
$ B- y+ @) e5 f  [1 J        Object object = element[--elementCount];
        element[elementCount] = null;
        return object;
/ _8 d( N+ ~  d1 k& z' M    }
- }5 Z" |& ]3 k$ l& U/ y' S
  @0 w& H; x4 [- T4 w8 Y4 Q' J/ v: V    @Override
    public int getElementCount() {
        return elementCount;
    }
! P: B/ }3 j& z8 V( J/ F  c
    @Override
    public void traverse() {
  N/ I4 c4 a( e# F2 P% j' D        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
. }6 O/ g; V# t# R. D. ^        }
        System.out.println();
) j: Z( t3 O" f- Q! X# D    }
9 j# U- L% `6 k$ X2 \- E}
$ v. L  `+ y: V- ^% ?3、栈的测试
  ?$ j2 J6 @6 @# F& cpublic class StackTest {
    public static void main(String[] args) {
  k" T, \" P( c, w8 t1 L$ s        Stack stack = new StackImpl();
7 V: ?+ ^& Z  u( K/ A
( u0 ~5 z% @: c/ J2 l        //第一次入栈:压入1-15
        for (int i = 0; i < 16; i++) {
            stack.push(i);
        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
% d' L) a1 r9 F1 [1 M. G. u        stack.traverse();

        //第二次入栈:压入16-31
9 a8 j2 }5 r9 b/ Z6 p1 R2 R- O        for (int i = 16; i < 32; i++) {
            stack.push(i);
+ g! V) w  z  Q) j5 ]7 ~        }
4 L& D) w" x" d5 E, z4 g/ \        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
) c1 V2 q* I* y
        //第一次出栈:取出31-16
) x, L3 [3 u" s* Y* C        for (int i = 0; i < 16; i++) {
( b1 H) C8 O4 [$ o% O4 `* V3 w            stack.pop();
        }
; `# E: v2 y, i% \% i7 g8 P        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
* R! r. S; j  f8 G1 A6 G        stack.traverse();

        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
            stack.pop();
9 t' m. m- i$ V" C: V' u        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //栈中无元素，出栈报错
! W$ G8 P9 Q) L        stack.pop();

    }
}

0 O" }8 K' U' E+ K* {& r0 e
1 D' y" g5 Z- o/ _9 c
3 B1 s$ }5 `: c) N$ k
- E9 U% D; }" c% v6 L5 @三、 用数组实现队列1、队列的接口定义
3 z3 K* t. \7 F  X* _# O/ }/**
* 定义队列的接口
*
# ]4 `" d/ r+ ~- L9 O * @author zhuhuix
" W( o# I) P3 E( B8 ]2 F9 } * @date 2020-05-01
4 u. a; N) o* v, X( N3 H */
public interface Queue {

    /**
! Q1 M& @+ E# _9 \/ X! T/ H, d     * 获取队列大小
     * @return 队列大小
     */
/ m7 ^6 _2 V, m; j    int getMaxSize();

6 k4 K' u6 w: {( B7 m" Z    /**
. X# T/ x7 u" u8 I5 S$ K! d     * 入队
     * @param object 入队元素
7 r9 r: }& t# W  G     */
    void push(Object object);

    /**
( d) @- M  W0 a- \     * 出队
     * @return 出栈元素
$ D2 \, a; T9 {# z! F2 }, h     */
    Object pull();

    /**
0 _8 U' k! J" I" n7 o$ ^* Q     *  获取元素个数
4 H6 o* i  i* m5 i     * @return 元素个数
# Q2 u  i1 N6 l) j# a. U0 w     */
    int getElementCount();
  l8 Z* ~' J7 B9 C( A) p# q
) F4 @' a! G) u- V4 t) _$ S    /**
     *  获取队头元素
     * @return 队头元素
     */
    Object getFront();

: B3 l" u9 B0 V4 I    /**
6 h+ _% h& I! b% S6 \5 X: ]3 X     *  获取队尾元素
     * @return 队尾元素
     */
    Object getRear();
1 [, h" ?- C; W/ u
8 ?4 d/ Y/ |0 g: @6 \    /**
' }! A  _. Q2 p' _6 ?. T8 G     * 遍历队列的元素
! y) F5 i9 s* o$ w7 V" n     */
- F2 z+ R& y5 {1 G, @. {: W    void traverse();
}
5 M5 p: @# y4 \$ e$ w1 H2、队列的接口实现
3 ^9 \- [9 A$ I/**
* 队列的接口实现
0 f5 d. T$ U9 o1 q *
0 }, a7 n/ N6 g& I7 Q& _ * @author zhuhuix
* @date 2020-05-01
, I3 i3 [9 X  f$ ^ */
4 C! [8 b0 ]( h/ B, `7 j$ x! Qpublic class QueueImpl implements Queue {

' q" z/ Y: Q7 o5 N    protected Object[] element;

' ?( U: ~4 E  u! X. c- [1 E    protected int elementCount;

    //队头
. I8 d$ E6 P' m- J% A    private int front;

    //队尾
    private int rear;

6 P" T6 v8 r/ x$ [    private int defaultSize = 16;

    private int maxSize;

    QueueImpl() {
        element = new Object[defaultSize];
5 X  n5 Q6 P2 q# ?) m' u5 j        maxSize = defaultSize;
( N0 {  {  b6 p, N1 y        front = 0;
4 U3 L+ L" l( U$ h* ]: @        rear = -1;
: o/ u# k. T" m/ D& S5 x  c4 J& }' u    }

    QueueImpl(int size) {
        element = new Object[size];
        maxSize = size;
        front = 0;
        rear = -1;
6 |% W% u: A0 Q6 Z6 e/ i    }
' l6 E3 F) X% p1 b, {& n
    @Override
' \4 f5 t! ?6 h- p    public int getMaxSize() {
- V& P9 n+ h( T/ x5 T8 \        return maxSize;
* \. t8 Q0 h- x- w3 O0 V. X' \    }
4 f, z9 {4 L' X9 W5 t
    @Override
5 Z3 z7 |* d- z: X    public void push(Object object) {
0 `( a$ N: o6 Y$ w2 r; u# Y( M        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
  d: N5 b' z" Y  l9 b            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
' U7 F' N4 d; X7 F* F6 U        }
" H0 b. o7 ?. H' B2 \        element[++rear] = object;
        if (rear == element.length) {
+ B4 f& {/ N# {9 x+ r. A            rear = -1;
        }
        elementCount++;
    }

3 ~" v% P& ~- K/ }    @Override
    public Object pull() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
        Object object = element[front];
        element[front] = null;
        front++;
        elementCount--;
; \- I! P# G6 a6 p, L6 e        //队列清空，队头队尾恢复初始值
" p+ ?" g" H# r% I% U$ h8 G4 b        if (elementCount == 0) {
6 z7 K+ U. G$ J! k% Q            front = 0;
# n: S; {5 }9 q" }3 H            rear = -1;
4 [" S: f( o7 O% q! _% ?        }
! c. Z0 T3 K0 R$ [* q% t3 ~" r        return object;
$ o7 @4 q0 [' \, o" W& b, S  y! t    }
# Q! ^) g3 A# Y
. j$ @' A& U' j3 g% Z- {/ B    @Override
' g( D% ^* }8 g4 O# s  K    public int getElementCount() {
( _* E7 u& x2 w: T) t        return elementCount;
# ^* E2 W: y4 N4 a    }
4 M/ K3 }/ _) U+ k% r
  y+ Y% ?" n' q# e    @Override
: ?: U( e; I3 y8 `1 G  W    public Object getFront() {
9 L9 ^) X4 m* u- \        if (elementCount == 0) {
            System.out.print("队头无元素");
            return null;
0 j- K/ Z3 I% t. _1 H        }
        return element[front];
* @. I) p+ j+ G+ s1 |    }
9 \3 z1 O& m" X1 A! i7 |
0 g' N& X# d$ K( B2 {: q9 X6 E# Q! M6 S    @Override
    public Object getRear() {
/ b1 ?5 W' t! f, X6 M' i. M        if (elementCount == 0) {
            System.out.print("队尾无元素");
; h+ t: F. P4 Y& k+ O% m: S# T            return null;
4 E* v6 {+ r5 ]; U9 o5 C* @/ S        }
        return element[rear];
$ q$ q7 F7 b* V: O" t% D    }
" ~  o4 ?/ R" V+ \5 [! a
8 D( L# s" ]2 O$ H& a0 p    @Override
    public void traverse() {
        if (elementCount == 0) {
            return;
        }
        for (int i = front; i <= rear; i++) {
8 ~( @5 u9 Q' J, i0 a$ ]            System.out.print(element + ",");
        }
        System.out.println();
    }
" u! }1 o, Y8 P2 R) w+ |}

! r0 g1 F3 p0 `' R# k# f3 e
3、队列的测试
public class QueueTest {
    public static void main(String[] args) {
# i& |7 [" `6 E, ~8 _# K6 W7 y$ K        Queue queue = new QueueImpl();

# X4 D$ ^" n( D5 y, h- ^        //获取队列大小
) L0 _4 h3 V1 I$ n0 S. F        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
2 n1 G' C( ]) u' y, d9 F# y
, U+ N5 s7 n- a        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
& b: e% j- t+ |6 K& S3 U5 E9 p            queue.push(i);
        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
( o! S% v. E9 }' @- F8 j  y4 P& B        queue.traverse();
5 J2 w6 ^# m/ X/ k        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
4 W* e8 P; g$ W/ N
        //第一次出队:取出0-15
5 Q0 T1 w9 s1 |+ |        for (int i = 0; i < 16; i++) {
            queue.pull();
% c$ l& D0 V3 R" F; e) ?7 c        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
# A  g" |0 U- _  C2 u% p" L. ^        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
$ N  u: ^, H$ m9 D/ @  M, P

        //第二次入队列:压入16，31
1 C2 x8 a) ]' @& u: J        for (int i = 16; i < 32; i++) {
' j/ l  F6 N7 b# u6 K% e1 L' A* B            queue.push(i);
        }
7 |" X4 m9 D8 P5 _/ [/ t) a! V$ J# h9 c        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();


  O: i" _- I" {8 A, z        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
9 I2 }& b" K& @+ x! o' B            queue.pull();
- z* J8 c# w9 f% u        }
* c$ Z, |) w. f) \( Y& d( w        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
$ s1 C( Y6 ^. R+ ]& g% J7 w
        //空队列出队报错
        queue.pull();

/ R$ q+ i2 R( k3 ]    }
}
, g9 `, c' O. @& N5 ]) e5 }( ?4 f


% k9 ?. {. J: E. Z


3 M5 Z$ N$ \" z+ U( Z1 b

4 {& L5 z6 M/ n) F! U4 o9 J; |1 n, {
; r- R  Z& G! U$ F& d& E& H
/ o5 U! ^# m' o
" `' w, A# r' D$ h3 @/ k

$ c4 ]: [( C2 e" M+ r
  o! F4 L+ ?6 d
7 E! E" o+ A/ \( h+ e$ U5 g' ?————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
; y8 w* F" j  l2 Y