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

杨利霞

数据结构——栈(Stack)与队列(Queue)的手写实例
; l3 z& C% N* g
[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  6 b8 e' h# W; a) @( |
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
    H8 I5 v" W* b0 e" I! O! L  }% i' d; H* h
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

1 C2 A% y/ A. A3 n9 I一、 栈与队列的定义
' c* `8 z7 }/ h/ W# V1 g# Y' W. B栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
5 R% ^0 e3 b+ R3 k$ y
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
- u- v3 d& j+ j# X4 i# R4 s: u
$ p4 J5 n9 m! L9 k

- M+ T5 m/ t! M4 _$ K二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
*
* ?. W, K  x0 K2 I2 }3 } * @Author zhuhuix
7 d# t2 @8 ?% A% K6 ~3 K. ~, r * @date 2020-05-01
  ^) m+ B% y5 {1 b */
public interface Stack {
+ G& c* p0 I# z* f, G7 p9 [! I! m    /**
     * 入栈
     * @param object 入栈元素
7 t/ I8 K7 [5 @1 t5 ^: N     */
% E) q: A$ h1 h/ V9 J    void push(Object object);

    /**
     * 出栈
4 M1 v+ o2 E' {  p( y3 v     * @return 出栈元素
     */
' g8 T, S* b5 }5 Z    Object pop();
- b& p0 \/ i0 V/ B
    /**
4 i% A& l" j/ N     *  获取元素个数
& e" ?% w: x0 f     * @return 元素个数
     */
3 h; P9 d* @9 w& E) S    int getElementCount();

    /**
     * 遍历栈的元素
  J' _6 i, ]* H' w0 e5 O& F     */
3 w' y+ }, w/ r! L3 \$ m    void traverse();
4 e% s; b& b8 h  c9 E! H# y
}
2、栈的接口实现
/**
* 栈的接口实现
*
; l8 O' q9 [5 K9 v. ~ * @author zhuhuix
* @date 2020-05-01
$ I9 D+ U+ L1 e) |$ m7 G! x1 \ */
public class StackImpl implements Stack {
. t3 D5 |8 t. b3 N* k0 P" V       
    protected Object[] element;
# {% P3 U) G9 G
    protected int elementCount;
+ A6 X8 s$ X1 t
    private int defaultSize = 16;
5 |- X8 J7 |& F5 s: S
4 F! D6 N. y/ {! `6 @: S# h    private int maxSize;
8 [$ |# U0 x0 ]! A8 Y9 w3 G
    StackImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
    }
6 N8 i/ |  \- o) d/ k# A& g
# K& |5 T1 q( u1 }8 H0 v    StackImpl(int size) {
        element = new Object[size];
        maxSize = size;
, ?$ z; Z- x+ O0 p, e# ?$ y! h    }

    @Override
    public void push(Object object) {
4 z6 x5 \0 P: b, j9 B6 m' y        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
8 l5 R( k* V; j0 G            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
        element[elementCount++] = object;
" ]4 m9 G" s& O% `
    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
: H$ }+ j: ]! W0 H1 O9 B/ m( @8 y    @Override
    public Object pop() {
. w/ c5 t8 O7 Z; E        if (elementCount == 0) {
' i2 f/ H) X5 t# |: t9 I4 [            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
- I' [/ P) G2 j9 \        element[elementCount] = null;
3 ^, f) o% P" Y, s' `3 a4 \        return object;
    }
& p8 ~. |4 C; L* M7 o! X6 J, \
    @Override
    public int getElementCount() {
        return elementCount;
' a8 p. P. H6 F7 N  G( e" O    }

" g$ S  b, A$ o2 }+ o    @Override
1 D% h6 d, Q. D. m# C    public void traverse() {
3 T4 T! l, M4 K5 p: [( h        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
        }
        System.out.println();
    }
}
3、栈的测试
public class StackTest {
    public static void main(String[] args) {
        Stack stack = new StackImpl();
& s8 c8 H  o# _% r
        //第一次入栈:压入1-15
; y+ M9 D& W3 o$ N& w7 O# G4 u        for (int i = 0; i < 16; i++) {
            stack.push(i);
        }
/ o  e# F# y( ]5 \  i0 t6 F1 Q        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
; |% i) h# I6 f( k5 v: Q. ?        stack.traverse();

        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
            stack.push(i);
        }
, v' d2 X6 `& @* g5 B( ]        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
  E5 j+ L2 O* {: y7 Z        stack.traverse();

        //第一次出栈:取出31-16
7 Q+ q; ^- X, D/ G1 Z$ N- N- ~        for (int i = 0; i < 16; i++) {
            stack.pop();
' n3 @( S: U2 j  a        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
8 k! d9 ~5 c0 g" K* [0 _" j        stack.traverse();

        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
6 C5 N5 v. {  T            stack.pop();
        }
& E$ P! O, W$ ~        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //栈中无元素，出栈报错
9 r$ v9 y- T, Y7 H+ P( K+ A6 E( G        stack.pop();

    }
}


( X, U4 I- W+ I, J3 v6 w
# n9 m* k1 w5 t( |
* ~9 x  ~% Y! {0 P; e0 U2 {三、 用数组实现队列1、队列的接口定义
/**
* 定义队列的接口
/ c7 o6 ]! c( @; s$ \% W *
* @author zhuhuix
* @date 2020-05-01
  j3 B+ S; q+ V' n0 N1 t5 T! X */
0 D* V; q6 n+ n  C: x8 M- m. M$ ppublic interface Queue {

! F: Q. G3 W$ m2 \! X    /**
     * 获取队列大小
     * @return 队列大小
     */
7 L- [6 ?( L. ?8 J1 `+ A    int getMaxSize();
/ \5 N. E. p. i$ O, S9 ^: _
    /**
     * 入队
     * @param object 入队元素
& S/ L( i0 z/ v8 y     */
; s6 }& X! f" W' s8 A0 k    void push(Object object);
1 ?% i, [3 p! y% M7 y3 s9 M  V
    /**
( Q' J5 C6 B+ B4 @+ b! d6 a     * 出队
& g$ C& \% P0 H: q) e) M) \     * @return 出栈元素
& M/ z! l3 e+ C$ Y  E+ {4 n% x' _     */
    Object pull();

    /**
     *  获取元素个数
3 i: s5 E' ^2 Z9 ?     * @return 元素个数
( \: V$ `) b! V2 S     */
1 t" I2 R6 M: K4 ]    int getElementCount();

    /**
     *  获取队头元素
. y& T5 X1 e9 r7 q* _1 \     * @return 队头元素
6 C3 x; U- D" Z9 x8 [  r% f     */
    Object getFront();

4 d* {0 t  o) V) i7 P/ y    /**
     *  获取队尾元素
! q- Z: S! B8 N+ i& W6 j. {5 U) U     * @return 队尾元素
     */
    Object getRear();
  Y) k* T6 t; \8 }$ r
    /**
     * 遍历队列的元素
/ D4 o* |7 ?! u* q     */
    void traverse();
7 B3 h  Y9 K0 g3 ]  F$ e! g7 b}
/ ~$ i% y+ |! U* Z! {- N) W+ M4 ]2、队列的接口实现
" r8 ^7 E" ~" Z2 I8 H/**
* 队列的接口实现
*
% f/ g( b6 ?3 [7 u( \ * @author zhuhuix
* @date 2020-05-01
) m$ [# w* }" P# |; ?4 z5 s0 w3 a; h */
- ~( U' J( K- ^" I: h; apublic class QueueImpl implements Queue {

/ W) Q* }. Q* d- J2 D    protected Object[] element;

) `, z2 ~6 g& ~# s2 G( ^% q9 C3 q, ^    protected int elementCount;

' h1 m% h( r1 p6 G  Y7 V    //队头
+ @3 R' ^# z  d1 X" x& B7 Y+ h    private int front;

  {# ]2 B% o+ }+ W1 f    //队尾
4 Q& Q$ b! o6 [+ g    private int rear;

    private int defaultSize = 16;
# r$ a4 x8 J" R$ N8 Z
    private int maxSize;

1 j) @( u+ u( j4 \- a    QueueImpl() {
1 j7 g/ M7 E/ n: H8 D9 }) u  D* [        element = new Object[defaultSize];
        maxSize = defaultSize;
7 J1 ~( h3 Q$ J        front = 0;
. }/ U4 l8 U3 X5 R7 t  q* F! n        rear = -1;
$ ^7 D3 o: I! ]7 d6 i7 X+ D( A    }
9 p, Y, W% R$ J4 A8 c/ R
  u1 M3 W; N$ H  ?1 q    QueueImpl(int size) {
        element = new Object[size];
; x# p( I' D$ Z        maxSize = size;
        front = 0;
        rear = -1;
    }
2 l' z0 C% r, U  U, |7 N4 |7 Z7 s
* J2 r) B! [6 q4 L. k    @Override
2 v* W0 n) S/ I    public int getMaxSize() {
        return maxSize;
    }

    @Override
    public void push(Object object) {
, O  S: s2 ~6 z' L0 V        //如果元素个数已经达到数组的最大个数，则进行扩容
" O; a1 R% V! Y/ R        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
% N1 ?* T3 Y% Q  v9 r5 N- M        }
% C2 n- M8 B$ K        element[++rear] = object;
        if (rear == element.length) {
            rear = -1;
! w! Z: v3 N: b8 w2 h        }
        elementCount++;
, s& Q5 J* N6 O3 t    }
! K% F; b& x% k
/ w& O+ ?; [1 C$ y, K    @Override
    public Object pull() {
        if (elementCount == 0) {
) t- u9 I6 Y& S7 g1 \9 ?* y            throw new ArrayIndexOutOfBoundsException("队列中无元素");
" m: @$ E( Z& Z' V        }
) U0 @8 R- s7 A7 b" t        Object object = element[front];
) X7 L1 z) _1 s; U5 v4 Y        element[front] = null;
        front++;
, K. \2 z* g9 z. u4 V9 ?; ~5 X        elementCount--;
        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
            front = 0;
            rear = -1;
        }
        return object;
- G, l) S0 |% W- D& P    }
$ E5 P2 D. p5 H# W, B' U% _! F
: D5 [# z' A# @0 Q+ r    @Override
- x* B" v+ D$ u  m9 L* @    public int getElementCount() {
- _- b: V  f) |% V        return elementCount;
    }

8 X0 s! {' S* [, S9 G8 b% L. ~4 M    @Override
    public Object getFront() {
. p  Y: M( R7 m8 u7 p0 C$ N        if (elementCount == 0) {
            System.out.print("队头无元素");
: {- ^+ @" }* s: r            return null;
        }
- z1 C( H7 Q# L3 n+ f  t# [2 H0 C        return element[front];
# K; D! R; _- \; _% h: w( c    }
; a, Z  U9 r! l  s. d+ v! t
' i& b" p. i( g3 }5 E0 f) A    @Override
    public Object getRear() {
        if (elementCount == 0) {
3 ?4 E" m6 ~6 l+ b$ B2 W% N! m            System.out.print("队尾无元素");
            return null;
) g9 V# g& ?, c* K% D        }
0 K2 e1 I8 a9 w* F* M2 _        return element[rear];
1 @: O$ I# U. m- l6 R$ f    }
. f: m  @( s# T+ ?7 q/ o4 M
    @Override
    public void traverse() {
# Y* x1 ]! V# _! V4 T3 E        if (elementCount == 0) {
            return;
1 n, ~; p. n, l& ?8 T        }
        for (int i = front; i <= rear; i++) {
0 k9 I9 E2 @: D3 j            System.out.print(element + ",");
+ t5 G) t2 T9 F) T* P: t6 X$ l4 X        }
$ y8 j: M% e! Y5 z2 b        System.out.println();
3 L) |" D% `. }5 x  f9 H. c    }
}


3、队列的测试
) @3 {7 s8 ~8 L' Mpublic class QueueTest {
7 D& B, k' {. B: g: C    public static void main(String[] args) {
        Queue queue = new QueueImpl();
, O0 U0 s) o! t3 s% x) x
1 k4 r, R4 t) [; I        //获取队列大小
! r" j- E  `2 K% i8 Y        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
5 m: K- C" j) }% x2 w- R7 X
        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
            queue.push(i);
+ o0 F5 C" L6 [* ~% j; J8 Y        }
9 B/ Z, n- w9 t7 R1 Q        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
4 h) z) d9 i6 L; Q        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
* L( v/ M$ B! J" b7 }0 I2 R
        //第一次出队:取出0-15
, h. N8 N7 z0 H        for (int i = 0; i < 16; i++) {
* W) C" F2 y- b. g1 o; G            queue.pull();
        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
5 A1 N  Q- U2 F2 M) K$ |, C        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

! L1 V# I+ E7 o2 [$ R9 i2 b
        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
            queue.push(i);
        }
) [4 K! _- F. Y' C        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
  v, h5 Z8 X% \, Y        queue.traverse();


        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
0 M: o- V+ e& K- f! c8 k  _        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();

        //空队列出队报错
& Y+ F4 p+ z4 Q6 k- g0 l; ^        queue.pull();
: P% p: P% s( V" |% ]6 H+ x) n- Q* F) Y+ Z$ b
( k1 a4 h8 v- _5 S. @/ J& N4 L    }
" s8 w& `% M4 C& c( s4 e}

" E* _, E  o) t; j% A6 j# Y

% r1 y% O6 k! U% U7 n/ e8 I9 `
( g0 b( `* o0 J, u" g, ?2 y$ y
: z/ S! {- h) T! w0 l. V/ d* h
& E0 I7 l8 K5 m
3 W- R" m7 }  z* T/ h0 A$ [" i& G
: J* w& J0 A% R

$ \3 p+ x8 K: Q. C; C2 {
- t+ }% C6 D3 S1 Q" y* b# w
/ ?4 i4 H1 C. y5 f; t9 F, E


  z7 N4 m5 O, x6 z; L( S————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 a% c" u: n  }9 b. n) R; f  h原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
8 \8 U6 s5 c( J* |

$ I9 a" Y% U8 p/ C  v9 D% I8 g