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

杨利霞

  @4 v0 p- K5 x0 M; [" N  m数据结构——栈(Stack)与队列(Queue)的手写实例

" G1 C) |; ~2 W% ^* _0 g6 y7 k[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  1 c8 K6 _. U$ Q) I6 G! o; A2 d! G
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
      h4 l2 Y# ~' V2 D: m
• 三、 用数组实现队列
  ! O8 |# R& P0 J. G* f; T
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    / m6 }8 N( l: y# S. X

+ Y6 Z( o' |  M# a* m- B, e
一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
. a1 H! ~# A% ~3 ~* x' T
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。


% m9 R7 z) I  N8 H7 ?6 e+ x
二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
*
) N# p2 l( P2 l9 b: S$ R2 Y+ q * @Author zhuhuix
* @date 2020-05-01
$ H+ P% l% l4 p( u1 s */
public interface Stack {
    /**
& y; L  Q4 {9 b8 I     * 入栈
+ A- j3 Y4 V0 r, U* n     * @param object 入栈元素
     */
$ D8 d1 x) m; j; P! X$ y, m    void push(Object object);
" K# {# ]& f/ l; |5 z3 O
    /**
6 L3 ]- U- j5 L1 V     * 出栈
     * @return 出栈元素
     */
    Object pop();

    /**
     *  获取元素个数
: u& J7 P5 ]7 d& a+ g: l: `     * @return 元素个数
" d2 f* ^6 p* P7 Y- v     */
6 y1 }. {8 V% R    int getElementCount();

) r" t/ i9 j4 K4 i. x1 }    /**
     * 遍历栈的元素
     */
    void traverse();

}
2、栈的接口实现
' D) e0 v, A) _( @! e/**
* 栈的接口实现
*
) J: x' B3 Y% n1 ~/ h * @author zhuhuix
" a, u. ^0 p# J& y) Z. G * @date 2020-05-01
6 {+ q, {* f! z3 [- s */
- S6 c3 r: G  f9 H& A  M1 hpublic class StackImpl implements Stack {
% G1 K: y7 G2 L* g  V* I8 {* p8 v       
0 ^5 k) A* P0 S7 C0 |    protected Object[] element;
. c, y9 X0 {( Z7 R+ }
    protected int elementCount;
3 w, I/ u$ i! Z8 b6 H
% G8 r$ R+ A0 C    private int defaultSize = 16;
) E0 `4 v$ |7 t9 d  Y6 t
4 O2 v8 Q5 I! B1 g    private int maxSize;
. T) h3 x/ V+ @8 T+ p% I  B
    StackImpl() {
        element = new Object[defaultSize];
# o" m% J4 @2 V6 w1 G        maxSize = defaultSize;
    }

8 _5 y0 @$ M4 A& e. B2 r3 ~    StackImpl(int size) {
        element = new Object[size];
- {1 q5 G; t, J  E" |; Y        maxSize = size;
    }
9 l* T6 j0 d" G8 M, z& @
* J/ d* c4 P* P( c* V    @Override
    public void push(Object object) {
  B4 K) N( @" [% D2 t        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
2 j5 I. M+ u5 N% U$ Y) U            element = Arrays.copyOf(element, elementCount + defaultSize);
% c6 X- P) D/ ~9 X& F+ P& G        }
        element[elementCount++] = object;
4 s9 ]' s3 I- {4 w
3 [) h0 G  ^1 K; U2 ^7 U7 Q    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
    public Object pop() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
. G$ y) T+ K6 p( E& n9 {        Object object = element[--elementCount];
        element[elementCount] = null;
        return object;
    }
3 z' d1 `1 o# V, W
    @Override
* h6 P2 b- P; {/ D    public int getElementCount() {
        return elementCount;
    }
! @$ H* F& o& c
& T) ?, ?; _6 {5 E# i6 ~' q    @Override
* f  v" ~- s3 b+ ^8 O! k    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
( n8 q' i! p# W, |8 o9 r4 @: u            System.out.print(element + ",");
/ S+ J% ?* M. }2 @        }
        System.out.println();
    }
}
3、栈的测试
; o6 U) Z# e$ H  ?3 |" R- wpublic class StackTest {
    public static void main(String[] args) {
% V9 X& S5 ^& ?4 h: p& i1 p6 F8 ]        Stack stack = new StackImpl();

        //第一次入栈:压入1-15
        for (int i = 0; i < 16; i++) {
            stack.push(i);
- y1 V$ v2 q" Z: K% Q- n        }
2 s9 W" n# p! p$ R6 |        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();
2 J$ A( H2 i; K0 |
& A' R, b/ Z* r+ N4 q, U- {1 i* P        //第二次入栈:压入16-31
7 w5 |' b* e7 _: W        for (int i = 16; i < 32; i++) {
            stack.push(i);
6 @$ r# z0 y; P: O, _        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
) u( D: n' r2 a, _' ?5 O  }' H
        //第一次出栈:取出31-16
; R" C1 B* Y# Z4 ~- I9 I) `/ {        for (int i = 0; i < 16; i++) {
. b% {# \& V+ J! i- H& }, B" h0 [            stack.pop();
+ v* S: }6 Y0 ~, ?        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
5 v# c1 i% d! Q+ c" B+ F        stack.traverse();
/ O6 W/ h/ e; @) }+ `( ]7 v6 Q
0 ?3 @) R# F: E/ {/ j/ `        //第二次出栈:取出15-0
9 J) d- U1 U/ x+ ~- S7 A- E" f        for (int i = 0; i < 16; i++) {
            stack.pop();
) L# ?7 x/ G) c) @( ]0 v9 t        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
+ d& z& V3 g% \' W6 c( Y8 x8 @# ?9 Y7 a; q        stack.traverse();
& _( L4 _6 u( o2 L+ o5 X3 _/ ^
2 r, e- R! ]- A6 Z& G. T        //栈中无元素，出栈报错
  u2 E& c! Q( \, a  n8 p. q        stack.pop();

, u0 O2 B* M* P- d0 H    }
+ f! L5 ~3 R  z1 y}
6 {6 a+ m% a- B



三、 用数组实现队列1、队列的接口定义
/**
* 定义队列的接口
*
# n0 }* Z* s; K4 c  b. R * @author zhuhuix
0 K$ c* q+ ]# K3 T * @date 2020-05-01
- y) j; I0 z$ a) J6 d */
9 g5 {. S+ r/ p7 r% Dpublic interface Queue {
+ _) w6 w- K! F. [  c
    /**
     * 获取队列大小
( b0 F/ a( K! x. ^1 r     * @return 队列大小
     */
    int getMaxSize();

+ h2 ?" M* W0 H) }    /**
" Y: r, h/ f$ E' z     * 入队
     * @param object 入队元素
     */
9 B: I  [- K4 F1 _4 y. [: |    void push(Object object);

    /**
     * 出队
1 n+ [  a& q* O! Q! b3 K' A     * @return 出栈元素
     */
    Object pull();
, t3 \. C! G) K* }
1 a! Q. a5 @5 B6 z" B; g7 P. J    /**
& n' l, o( s7 a; P% I" K2 r8 J$ r     *  获取元素个数
( m  N- D) x1 E+ a+ ~5 J/ u     * @return 元素个数
7 E% `4 g6 p7 d; U     */
    int getElementCount();

    /**
- }- }# N4 Q$ Z     *  获取队头元素
- T/ B9 z2 H0 D0 Z     * @return 队头元素
" a! j% g" |: f: ~- `; _# |     */
    Object getFront();
( j6 u3 p4 }7 x/ v
    /**
     *  获取队尾元素
     * @return 队尾元素
     */
8 k6 |( l3 t$ _- M0 i: Z    Object getRear();

/ h4 `6 q$ z& v3 W$ ?3 d! ]    /**
6 D8 M( v2 _6 S  K' r     * 遍历队列的元素
  M/ b! s1 H9 h# @) ?     */
    void traverse();
}
1 x6 T$ H: L1 V4 p2、队列的接口实现
$ }, L2 m/ N9 i4 y1 ~$ [5 c" p$ [3 N/**
7 q1 n) B+ H; c3 ^7 }; J * 队列的接口实现
*
; D4 O+ H# T$ c) Z- q0 Q * @author zhuhuix
* @date 2020-05-01
*/
# X. e6 X$ v3 Qpublic class QueueImpl implements Queue {
1 T# U  \5 H/ ^+ i  b+ u8 I- r
+ [4 ~2 [- ~4 v+ i5 E    protected Object[] element;

" E8 ?" D( u/ L$ H8 s/ y& ^  ]" j    protected int elementCount;
3 T2 {9 ]3 w$ u. U! S  Y& Y1 i! N
    //队头
    private int front;

    //队尾
; B2 \/ k  i1 a; T4 N4 i7 u    private int rear;

+ _2 v9 O. X4 S1 r3 \    private int defaultSize = 16;

0 E+ k( x. ^- {, I    private int maxSize;
) C% n, T) A0 C
! j8 \+ \0 r; o' M, ^7 J    QueueImpl() {
        element = new Object[defaultSize];
: j& b4 H! y0 l; s% S        maxSize = defaultSize;
, R' {) `9 ]6 |9 a3 }( ]2 f1 j        front = 0;
; @3 p: D2 J0 @8 h  R' b9 Q. h        rear = -1;
    }

0 W2 \* W( M  a+ @6 l& O5 k- `; R    QueueImpl(int size) {
        element = new Object[size];
, n6 F9 m" x( `  x7 l8 t        maxSize = size;
        front = 0;
        rear = -1;
# \( d% E- `. q    }

# ?) f8 u, s! o5 |* l( ^' V    @Override
( I; c: T8 p: ?    public int getMaxSize() {
        return maxSize;
    }

    @Override
% T# L8 W) G9 j" [& I    public void push(Object object) {
% k9 Z1 w9 j0 p! F        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
" g4 d6 p& Y$ {( _5 G% c# ~5 N        element[++rear] = object;
        if (rear == element.length) {
6 j" q# H: o' v% ]            rear = -1;
        }
: p" q' z" o' \* H        elementCount++;
    }
: f% ~# I/ c; A8 _5 Z
    @Override
    public Object pull() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
$ R7 `# K, K* w; l; j" g1 z7 b' K7 @0 z        Object object = element[front];
        element[front] = null;
+ \' X+ ~( R$ W" g3 z& k        front++;
        elementCount--;
% \+ M- c) x3 }, }        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
            front = 0;
            rear = -1;
( z4 m# M0 @; z( g3 |' u        }
7 ?& X- Q" {, Z- B) l+ J        return object;
    }
) ]# I' G+ y0 a: n% W
    @Override
    public int getElementCount() {
1 X/ C8 @5 {! I1 B- I9 E4 C        return elementCount;
    }

$ Q, i0 I4 @+ n0 |. `  Q0 E; [# O% X0 m    @Override
5 z7 p- W& e1 r6 E2 o% d2 ~; ?9 [    public Object getFront() {
* Z4 z1 {# S9 P7 y0 ]        if (elementCount == 0) {
5 p' E0 P0 p* P            System.out.print("队头无元素");
            return null;
( Q2 I- L6 c3 w# _7 U" `7 j        }
0 [$ h+ Y% X) j  l6 \$ |! H        return element[front];
- L3 u% j4 o/ G1 ^+ V    }

, b: B7 N' w: B    @Override
1 z8 u  l! _1 ?$ R, G    public Object getRear() {
( ^7 D- c1 _1 W; h        if (elementCount == 0) {
            System.out.print("队尾无元素");
            return null;
$ C. B' l4 k2 l        }
        return element[rear];
8 l5 M% y0 G  c+ A8 V+ Y3 h( s2 s- F    }
1 B6 P: u- @! E% D- `) {; |
; n. |- w+ Y* h! K/ e    @Override
    public void traverse() {
' {* X; m$ i, x; G3 H        if (elementCount == 0) {
8 @) y! s# \. p& I            return;
, a) {7 Z$ ^1 q3 |7 B. _        }
& ?& v2 `2 D: |$ u- r( t        for (int i = front; i <= rear; i++) {
7 H  E  T4 f( ~$ C# T+ _4 r! j8 m* o            System.out.print(element + ",");
$ x9 N9 M0 \: \( {        }
        System.out.println();
. r$ }& m; c: ~( U; b# B6 E    }
: W% @) j0 W! f* u5 s( f/ ]  c}


3、队列的测试
public class QueueTest {
% K% W5 O5 X1 `8 b    public static void main(String[] args) {
9 t* G3 c9 s6 I# s& P# T4 T! M' ]" T, I$ q        Queue queue = new QueueImpl();
2 u* _! c  H! o( j6 r
* n1 V5 e. s$ M        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

. C- Z' L2 \5 c$ L7 B        //第一次入队列:压入1-15
! }2 Y1 f' ]1 N* m7 R2 |        for (int i = 0; i < 16; i++) {
* E" y4 k$ \% E& X            queue.push(i);
# r; o0 S7 H/ f& V' s8 z& h        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
+ `! u/ Q( O6 N! r        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
; X9 Y- G& z9 P# d& l* j5 |
        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
            queue.pull();
8 b3 j3 v( o4 J; G# y; `% O! N        }
: q5 c+ T- b+ f( V0 {! p/ r- M# s        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
0 r! p0 X  o+ W0 E# Y* S

( q5 A. K( J1 F/ A* z        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
, J: w0 o) O* |+ Z  T* m- {0 U            queue.push(i);
, W1 C% s; Q3 A  H) O: l        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();

/ |2 i" p' T9 K  R0 E0 Q
        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
2 S1 P+ X+ u7 ]' Y8 a+ \        queue.traverse();
* f3 _! K4 i. h/ W/ ^
        //空队列出队报错
        queue.pull();

    }
/ H& ^) M5 ?/ @}
  Q4 x. V' ]$ A& f


1 ]2 W+ T5 T7 J' V( N  \
2 B/ m/ U  J9 ~2 {3 Y
5 z% |" s  u8 B  q* k$ S8 b
' H( K8 s; d) c- V



" m" d$ X4 n' J
/ ^7 `5 T  L" L2 b



————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" n* O' |! S; |9 Q* j, p原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785

! h2 D1 n4 p) y' a3 M1 h