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

杨利霞

% u$ {  L, \' A, O& W! \9 t/ M% y数据结构——栈(Stack)与队列(Queue)的手写实例

1 z2 T1 o) w- I, d. f[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  ' a2 J. L- x1 m0 a5 ~! U3 v4 d
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  : H3 `) {# f1 Z3 t: Q& x
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

  X1 s$ R/ u& G( v" \, x# t7 {
7 C8 D/ i! N+ o0 M一、 栈与队列的定义
+ x- C" Z8 A0 v4 Y4 ]栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。

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

2 C" j$ w- e/ N" ]! x

1 g5 b' G" n: p9 Q二、 用数组实现栈1、栈的接口定义
/**
7 g, e+ _# M- B( \5 {9 i/ G * 定义栈的接口
*
0 V2 I7 s( \# r * @Author zhuhuix
4 G* P+ U* s5 _" E * @date 2020-05-01
# [; c' K, \8 E2 D1 t9 ~ */
public interface Stack {
. B( `( z, Q1 n2 u4 Z    /**
% z+ j9 A% s# ]& h7 p% v  X& ]8 v, w     * 入栈
* _& x2 _) I8 \' C" l     * @param object 入栈元素
     */
    void push(Object object);

5 {6 ]+ S9 f6 y2 |; ^; N    /**
     * 出栈
. T8 [: u! o; W* I+ V& m9 ~" g     * @return 出栈元素
     */
    Object pop();
/ w  Z" W  g4 i* M9 o& u. G$ N4 w
    /**
     *  获取元素个数
5 D: w& y% r1 N+ Y     * @return 元素个数
     */
  w$ a& r% h6 c2 Z6 }    int getElementCount();

4 m# G' c, U( c- Q    /**
! B/ ~7 C8 \. z- U' ]     * 遍历栈的元素
     */
    void traverse();

}
! `  n( J. ]6 _, p2、栈的接口实现
/**
+ A# }& e/ J0 |$ b. s * 栈的接口实现
7 S4 t# H$ s& |! v. r *
* @author zhuhuix
* @date 2020-05-01
& X( k0 l1 j9 ]/ Y0 i */
public class StackImpl implements Stack {
: ^1 J; |/ L  ^% V5 _       
    protected Object[] element;
8 Z  e% f+ j; }# A
2 m  ^9 ~' q, K$ c0 c8 B    protected int elementCount;

9 h! i( W8 Z8 U" F5 N    private int defaultSize = 16;

    private int maxSize;
0 r1 Y. R  D' Q, \  ?* @- r
# y8 L  o. w9 v6 I: p2 E5 r    StackImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
7 U$ e/ P) W* _+ Q- \2 q' k    }

    StackImpl(int size) {
        element = new Object[size];
9 b0 [  h4 U, ]3 J; R6 i        maxSize = size;
8 M" ^" z; a! Q7 ?% ~, r+ m    }
7 z8 O% ~" i+ e- t" _  }) \* j
4 v" `2 P" x% E* v' h" u    @Override
    public void push(Object object) {
' J* x) J4 g; n        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
8 ^3 p; g: }8 ^4 x1 k        element[elementCount++] = object;
9 K- T; m' U+ L5 a) ?, I% `
# \9 R6 Z: r$ n    }
0 @* f* `, @  i6 ]) C- |        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
    public Object pop() {
        if (elementCount == 0) {
7 H& Q% w$ H* g8 j5 j            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
( F4 s% g" C: j$ H# r3 z        element[elementCount] = null;
        return object;
1 j" D. D6 Z$ D  N# t5 `    }

  g$ S- v4 i: o6 S$ \) F6 |' f    @Override
    public int getElementCount() {
        return elementCount;
    }

4 v1 }$ U: J9 d; ^4 X' A0 V; g) k! f    @Override
2 |: f+ }$ [/ E9 H" ?    public void traverse() {
* e; i! ~4 x. P4 [        for (int i = 0; i < elementCount; i++) {
7 u+ {+ [( I' U            System.out.print(element + ",");
        }
        System.out.println();
    }
}
* `6 t7 G# k; I1 u3、栈的测试
public class StackTest {
    public static void main(String[] args) {
! w2 R$ d; J2 B: h7 g        Stack stack = new StackImpl();

% \2 e% `- w9 i6 a        //第一次入栈:压入1-15
        for (int i = 0; i < 16; i++) {
            stack.push(i);
: t! @4 N6 O/ h" `0 b/ F5 x0 q+ L( k        }
, J, L; {  _% x4 Y. L) @        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();

+ f2 n, H7 l# V) @) U- Q        //第二次入栈:压入16-31
, v# D2 n% z9 M' ~- e& _        for (int i = 16; i < 32; i++) {
4 C. o8 m  e( E7 u; A$ Z* Q" X) \; b            stack.push(i);
        }
3 Y* K9 [2 p, W4 I        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

1 g/ v, ?; O7 T        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
            stack.pop();
! Y) V% R* T# S  f% W) x8 g. {        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

( D& G2 v+ |. _: p        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
& A2 g% y7 A# f            stack.pop();
        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
) O' _7 `+ e+ P3 k7 I4 p6 o        stack.traverse();
; }$ R% \) a' M# |6 y7 c
! Y5 D' O+ y% D$ Y        //栈中无元素，出栈报错
        stack.pop();
0 P- \% V/ T; m
6 v. p* t# |0 g6 m0 X    }
8 S* w0 i' e. B% [  ~* {: }4 g1 e}
* ^7 {  s0 d0 H* q



三、 用数组实现队列1、队列的接口定义
" J" e8 l' _' m' E$ J+ s/**
* 定义队列的接口
1 d! v3 C/ K) \9 A* k6 b3 g9 I *
6 X5 o, a3 u( q8 o * @author zhuhuix
6 g& T2 B+ L' V7 |. \# b9 }0 K3 X * @date 2020-05-01
*/
public interface Queue {
9 j; p+ l4 l6 `3 h5 ~
& e2 k( P9 y$ A! x! n  R    /**
     * 获取队列大小
" d+ m  i0 U: z- q; h     * @return 队列大小
     */
) l4 j5 Q! `5 Q7 d9 ^, c    int getMaxSize();
# |, R  X1 X8 Z( ^- j$ M. O, t- F
    /**
0 @- k5 }' A: o# S8 j     * 入队
) A: S7 h, n) c7 S( Y. m     * @param object 入队元素
2 @; g7 n) Y( l+ m0 T* k     */
    void push(Object object);

$ y; H" I: T: J5 Y7 J% P* V    /**
# b1 B% \# x& A2 h+ u. o     * 出队
     * @return 出栈元素
     */
7 b# V; T9 Q  \1 R. w! U    Object pull();

    /**
7 O' |' y# @1 N2 E% Y2 w     *  获取元素个数
) s& s; B% w2 T" a/ U1 j     * @return 元素个数
6 h, g+ O* p5 `4 `" \6 K9 t. G     */
    int getElementCount();
. g# t* `+ y$ L
  Z& W5 B$ K  n0 G% ~1 `0 r8 s. Z! c    /**
5 ?2 m; d4 }. O% J9 J     *  获取队头元素
     * @return 队头元素
1 E$ L) E4 M9 a     */
2 Y! b/ |0 w, Z  X    Object getFront();
  |4 Y' U  Q8 ^: h
, [9 C3 l- T8 B3 p( `    /**
: l9 H9 u. b3 A5 K+ s     *  获取队尾元素
     * @return 队尾元素
$ O  u1 \4 j  ~     */
4 t6 ?$ Y$ j( K+ c3 z    Object getRear();
  W4 K9 _" I- m
    /**
     * 遍历队列的元素
     */
3 X) w- }- V/ m    void traverse();
7 E: m6 f/ V0 i. y! C- [}
2、队列的接口实现
/**
7 b& X; d. H$ J: V& O  _! V+ X * 队列的接口实现
  J+ w$ z; }8 o; k) Q$ ^6 ` *
: l8 A# O" F$ [1 G. F; R * @author zhuhuix
* @date 2020-05-01
*/
public class QueueImpl implements Queue {
& }0 M4 s2 ]0 ~8 c) c" H% I
    protected Object[] element;
% X5 k% t* P8 u+ _$ \
    protected int elementCount;
! [" M5 B! J  s; t7 r
+ f7 y/ q: H0 E# V. P    //队头
    private int front;

& I  L4 ?$ f( T+ e    //队尾
    private int rear;

    private int defaultSize = 16;

8 U0 \% e$ s' [$ M8 ~* G    private int maxSize;

& p" U1 x! j- j" C9 g9 E2 B  l% e    QueueImpl() {
, @& }/ m% _  e% e+ [/ U  h7 t        element = new Object[defaultSize];
        maxSize = defaultSize;
        front = 0;
6 `! o& [$ I- K3 m        rear = -1;
& Y# y( X( [5 g/ }' R    }

2 q" ~. i4 {5 L5 A) ~; V    QueueImpl(int size) {
2 y7 }( y- x2 q        element = new Object[size];
        maxSize = size;
        front = 0;
, Q( H0 Q, @" O! Q" T+ T( Z) m        rear = -1;
    }

    @Override
2 \9 C( O  y/ C9 P8 O    public int getMaxSize() {
0 h; r) Q& p, F' P7 q0 R        return maxSize;
. A1 m! \4 n/ s( N/ P: @    }

7 z# S* A7 s) A- i! e    @Override
" G, o' `: a/ G! Q7 G    public void push(Object object) {
6 V# d$ b  o5 \0 t        //如果元素个数已经达到数组的最大个数，则进行扩容
5 a" G" E- w3 z6 \        if (elementCount == maxSize) {
3 k* y8 J9 p8 D            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
        element[++rear] = object;
/ M, A3 m/ z6 ]        if (rear == element.length) {
            rear = -1;
+ Q9 U- i9 [4 G/ u* y" C        }
        elementCount++;
    }
8 k/ B2 [1 t/ F
1 t% y$ n# y  J3 s8 q" B    @Override
' A; B& b* ^: I    public Object pull() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
# w! \# E5 u7 T% e$ i        }
( `3 K8 U  R. p2 ~        Object object = element[front];
        element[front] = null;
        front++;
+ u8 h/ ?3 |6 d3 d0 ?1 R2 [        elementCount--;
        //队列清空，队头队尾恢复初始值
) \9 [, K7 _2 j. }( B        if (elementCount == 0) {
( F7 n) }8 Z1 Z# L            front = 0;
- d4 ?5 R9 q+ Q4 i            rear = -1;
" F) P# T. ^2 u3 p/ |* q        }
" F; B7 {1 T" m8 W; E6 \/ G8 S5 B        return object;
    }

    @Override
% k  L# V) x: j1 \& \' {    public int getElementCount() {
        return elementCount;
    }

    @Override
1 L" ?. F: J7 g, L3 X; D    public Object getFront() {
' ?+ k/ _9 i2 ?        if (elementCount == 0) {
+ ~4 t. R/ g# b2 p3 o: r3 J            System.out.print("队头无元素");
/ \& c3 v( z2 n6 y  @, w            return null;
        }
        return element[front];
# o2 r  w1 N+ w    }

    @Override
    public Object getRear() {
        if (elementCount == 0) {
            System.out.print("队尾无元素");
            return null;
        }
        return element[rear];
    }

! b  q( D7 b" |; n: G5 B! j! E    @Override
( C& F( L0 E/ A    public void traverse() {
        if (elementCount == 0) {
2 q9 w2 ^. X5 d9 J/ H1 b- [            return;
; W$ ~; |0 S. K4 `        }
        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
        }
        System.out.println();
# l) k8 G8 V0 C* e" k8 S/ I, ~    }
}
9 a8 z% _. n, R( U$ O: R

& W2 O& r6 u# G, R. Z8 _- m3、队列的测试
' x4 C4 T$ U( `" Tpublic class QueueTest {
& h( n$ U: s- t    public static void main(String[] args) {
        Queue queue = new QueueImpl();

        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
) \* ]& K4 b" t1 R0 x: e4 N( g7 g
' Y5 d, f6 u  V        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
- \2 R) B0 ?3 U: ]0 p            queue.push(i);
: a/ o0 R6 m: m: H1 Q$ _! |        }
2 ?( A6 ]5 ]" S* C9 m6 D+ _3 Y        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
5 n# |4 S; I* X3 K
        //第一次出队:取出0-15
. W: @/ N" K% b7 U        for (int i = 0; i < 16; i++) {
( P0 w6 _! s; q* J0 x# \" [            queue.pull();
" d" _8 i) K9 V. f) V3 B        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
: K. A& V; M- X  B% t# B/ X        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());


. H. Q, r; Y8 m! n& Q3 P        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
            queue.push(i);
        }
, W& h: W0 B# \        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
& {: d6 m# ?' S4 |- l: s        queue.traverse();
/ J1 ~, Q3 ]% r$ a  u# S, G; \# x

        //第二次出队:取出16-31
* }! |0 ~3 G& ?9 `9 n% V        for (int i = 0; i < 16; i++) {
9 @  W: c- j* j) G$ F            queue.pull();
        }
' L7 K7 Y' w+ m" K8 K        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
. |8 w/ t9 [" G6 C( U$ `
0 `1 F. K2 b; Q- v* g8 a        //空队列出队报错
        queue.pull();

    }
0 ~! ~5 C- O2 O! m7 }}
, g3 V3 P% A* t9 Y6 U- k) H& l/ v
* W2 f, |# k, ]8 k
: n7 x% X0 Y5 u) s0 T  l9 p  E. R


4 g3 }' g4 s6 }& B6 H. C3 ~
) Z, d$ X% l* Y  E8 f
* s6 F6 V$ f2 T  v3 r
5 u3 u9 l+ u* m


3 i2 P: R4 Y$ ]1 k! @+ U- g8 [% g



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


* w& r# B. T7 e/ q3 ?, v