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

杨利霞

8 ~' K9 {) J# B9 L) e8 e+ u% |数据结构——栈(Stack)与队列(Queue)的手写实例

: ?- S/ a" l: G/ N% Z8 K# R8 P[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    $ V( s. g. Z1 r4 B5 G5 Y  I) ?: f

0 F4 U6 T& ~: {  L" F" O1 U
一、 栈与队列的定义
$ f- T. c- _' e8 x# p. ]栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
" m% h; h0 U) q- L1 s; Q; L. y
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。

! h( W: F& W) G  ?$ n
+ f' g0 Z4 H8 \4 V3 k, N% W+ @8 D( \% u
0 z" ?/ Q) c1 K- ]6 {+ k二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
*
" T' G4 A' }; ~# O * @Author zhuhuix
  b2 @+ p8 Z# @- z1 Q* k * @date 2020-05-01
# E  I& R" K5 R; { */
public interface Stack {
    /**
$ {: x5 w- C, z: L3 `- R' r* T     * 入栈
     * @param object 入栈元素
; {: [2 }' V2 C) E; F+ m! T     */
* g: d, M8 X$ ?9 M* |( a' w    void push(Object object);

    /**
+ o1 I* ~. b* @; _" O0 X0 F$ b     * 出栈
     * @return 出栈元素
% y* `6 d  R  ]9 d8 I, \3 h; x     */
# j% H9 [: x* H6 z) p! o    Object pop();

) j9 ]5 k# Y5 T  b; _( w, c    /**
" o1 I8 |+ n% E0 r' `     *  获取元素个数
; u! d: m. G9 _( n     * @return 元素个数
     */
    int getElementCount();

    /**
/ f8 T( Z, H2 Z& u2 S     * 遍历栈的元素
     */
    void traverse();

0 m+ A: J; g6 A9 x- G' B9 }}
2、栈的接口实现
. f. R5 _: {* H" z: Q' I! C5 O' }/**
! G. ]# F3 c, [' E* m4 E8 |7 _ * 栈的接口实现
* H3 g$ K8 q" L  k. G, L* W *
* @author zhuhuix
* @date 2020-05-01
( x, v$ o1 M0 Y9 r7 U */
public class StackImpl implements Stack {
       
    protected Object[] element;

  _! ?; I/ x$ y- A! u7 E    protected int elementCount;

    private int defaultSize = 16;

* l# \" F% r" c' P9 @* j2 o    private int maxSize;

    StackImpl() {
4 S6 u3 p' h' y        element = new Object[defaultSize];
        maxSize = defaultSize;
    }
6 w8 P3 d+ V: o: C. s: @" J* R5 n
$ i0 C8 A# U: h2 q$ b: T0 X    StackImpl(int size) {
        element = new Object[size];
) P" W% f) s- {0 K$ K9 B9 s& |: b        maxSize = size;
    }
4 z$ o( J! h+ c3 }+ |
    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
, f6 b7 ]: T0 O# r        }
        element[elementCount++] = object;
0 `: T- H4 v" K- z
    }
% G  S; O* a) V/ t        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
    public Object pop() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
% r; `, j2 j; \; S. G        }
4 F/ g! {6 _! d  B4 \, ^        Object object = element[--elementCount];
7 L' `' R  e* _# x1 l2 t        element[elementCount] = null;
; m$ X/ O/ `; V( E7 |        return object;
, T4 w/ N8 P1 [% @- q* Q    }

0 N- p! o) j* Y. U# i- l, C3 u    @Override
    public int getElementCount() {
        return elementCount;
    }
, h" W; d) |/ c: y; I' P( f. [3 @
    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
" l4 D; h" l8 D8 `  b        }
! l& `, k  p, L% u; Z& B4 i; ]/ t        System.out.println();
2 n; s! |- l. x7 K# G+ G6 R) l    }
! g3 D; L2 j" H, X9 p}
3、栈的测试
( n5 L  ^( W. y  cpublic class StackTest {
    public static void main(String[] args) {
        Stack stack = new StackImpl();
# F; e+ U7 B' K/ f9 d- J; e+ X
9 c7 u  e( Q9 k- c  Z0 I        //第一次入栈:压入1-15
. i9 w5 F: T- m/ Y  S        for (int i = 0; i < 16; i++) {
            stack.push(i);
        }
, p& p% m2 M6 L$ v' k        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
8 d0 A2 ^6 R; m0 R        stack.traverse();
- ]/ i$ x4 u: z0 {, p
        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
            stack.push(i);
6 Y: q' s7 S1 t( x( L        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
% |7 ^# N- _, F8 U9 n$ J
# x& m- [8 u- c. j5 G* P* G* Z        //第一次出栈:取出31-16
: s# Z. ~3 _" [/ W. I. o' K        for (int i = 0; i < 16; i++) {
# G; c. P: M- _0 @$ |$ t  Y            stack.pop();
        }
4 \# @( n& f& A) F8 y2 V        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
/ Q2 ^7 W0 r( @  s2 c% X+ t        stack.traverse();

: ?4 t8 l# g% [- Z        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
  C* v4 ^  A9 M$ f7 a        stack.traverse();

        //栈中无元素，出栈报错
        stack.pop();
# Q# ?) G6 _* c) d. t- r
    }
}
8 U4 c! t- ~* k% w/ t, `
, L3 w. q- |9 b* U* j
  a/ |6 l, o! F* V; o$ ?2 s" S
/ W5 [$ j8 F1 Z; U0 _5 q
$ r6 s( ~3 u2 Q! x0 M$ D三、 用数组实现队列1、队列的接口定义
# f# q$ ?  K; X. D9 ~9 \/**
; o) s7 q7 ]9 V& u) e8 t& e1 J/ w * 定义队列的接口
*
( F. m; N. O9 k* N  g% o * @author zhuhuix
* @date 2020-05-01
  A$ `, R# K& m# i: f$ B */
public interface Queue {

6 J! y( g/ W* I0 ?    /**
     * 获取队列大小
     * @return 队列大小
     */
    int getMaxSize();
8 F1 q' k% }  j8 r/ M0 O
/ T4 |5 n( w9 J' @$ [/ V; A, w    /**
# z! q6 P) X, y. G( `3 L4 d! q     * 入队
     * @param object 入队元素
6 g- J8 x, X6 b1 _9 a8 M( x     */
/ l( V9 k* k5 O/ u# b    void push(Object object);
, V; A% ]/ w$ T6 O: b
    /**
: g; B- ~# ?+ F     * 出队
& Y- P% z; u2 _+ ?" @2 p% v     * @return 出栈元素
     */
    Object pull();

    /**
     *  获取元素个数
2 z; I3 J% Y$ K7 C- K     * @return 元素个数
     */
    int getElementCount();

    /**
     *  获取队头元素
     * @return 队头元素
# n1 q# H9 f1 d3 [# u! a" o     */
9 Y( R* L; V9 i* |: x    Object getFront();
' e1 |% C' ?+ Q) [" Z) Z/ `/ i! K1 Q, R
    /**
     *  获取队尾元素
, l1 l( L; U% U3 A     * @return 队尾元素
/ ]! C' r* p3 s) \     */
7 V. K+ ?5 u6 h$ R5 W  F& |+ C1 _9 D0 o    Object getRear();

    /**
2 L0 q0 e# B/ g7 I% [: {" ^; ~     * 遍历队列的元素
' |2 {/ ]! C" w# y- L8 u9 ?6 I! Y     */
1 k$ \: E, i( R5 F7 b" A    void traverse();
}
4 O+ p5 d( B0 v; K8 u2、队列的接口实现
/**
: v6 }0 a9 F5 S% e; C * 队列的接口实现
*
* @author zhuhuix
* @date 2020-05-01
1 y  K, N, t3 `, k */
* y' R9 e8 d2 _public class QueueImpl implements Queue {

    protected Object[] element;
5 ]" h! v& }7 q  F  M7 G5 r
    protected int elementCount;
$ f  @6 @# }1 m. f0 B4 j" ~( D
5 v& w3 V$ {0 s; K    //队头
    private int front;
' R1 ]/ E; Z8 l) _  L
    //队尾
& D0 R& |' @* W    private int rear;
- T/ G* l4 ^0 T7 F& @
* i$ \3 n( G% A4 M! g    private int defaultSize = 16;
. C$ M' n4 `8 v7 L/ N( M% U
5 ~: x/ `1 f5 w4 Z! m/ \, N* }    private int maxSize;
5 {" z: `2 d2 g* Y% L1 D" U# h( e
    QueueImpl() {
$ o( A4 ~5 j" G2 _0 ~$ F9 e        element = new Object[defaultSize];
7 u! ?; ?/ h% {- L3 [2 m        maxSize = defaultSize;
# f5 _* T/ Q4 n6 ]6 g        front = 0;
* D; L' ?$ V# m( u( U) R        rear = -1;
3 L) ~7 {# V' B* p    }

    QueueImpl(int size) {
        element = new Object[size];
        maxSize = size;
- O5 M3 q( }. A  y        front = 0;
+ W' v9 ]  D' d  I+ Z) C7 R/ ]        rear = -1;
; h( b8 _2 s& K/ U) Z    }
& u5 @3 u7 I2 P: M1 [
    @Override
    public int getMaxSize() {
        return maxSize;
    }
9 {, x5 `2 ~6 P% [3 H
    @Override
    public void push(Object object) {
% K- Z! w% T- ?& m: c# k' \        //如果元素个数已经达到数组的最大个数，则进行扩容
+ r$ Q/ X# S6 i        if (elementCount == maxSize) {
+ K/ G. }) w( h4 s( E& W            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
4 \% W* |6 ^. }; e# \6 D4 E        }
8 T# d% {$ l3 k8 E& ^8 \        element[++rear] = object;
7 k+ A3 m- J0 z' W: {; g$ P        if (rear == element.length) {
# P2 w; l* }/ J4 [4 Y7 ^) E- t            rear = -1;
        }
( z( Z7 ^1 e# l/ Q* J; H$ ]1 U        elementCount++;
    }

    @Override
    public Object pull() {
        if (elementCount == 0) {
$ q3 p& O) N6 J' y* ?% f8 @* X0 V) H            throw new ArrayIndexOutOfBoundsException("队列中无元素");
( ]) w5 I) x. O5 C        }
        Object object = element[front];
        element[front] = null;
        front++;
" f/ R: Y+ _  I% r0 f7 [0 r* }        elementCount--;
' ?% X" l% u" X1 M1 w+ @        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
6 r! k# e: \# T; a; A. j* s            front = 0;
# E5 h  f3 c! [( h% E1 {7 @            rear = -1;
        }
5 m" s  _% w$ u2 u6 u0 L        return object;
    }

3 ^- R. H6 T/ y5 t# J' J3 n    @Override
& K, C6 p( a1 ?$ d    public int getElementCount() {
& V, `+ t' h' p+ K; ]% q1 N        return elementCount;
8 Z  h- _& i& z+ b4 c: @6 q" ?. v    }

) p  `# A; m0 ?$ G% T6 z: z    @Override
2 a* x3 Z# i7 c/ g9 }' {7 W    public Object getFront() {
, Y1 W' J5 g9 G* w  S        if (elementCount == 0) {
            System.out.print("队头无元素");
            return null;
( b8 {: {4 y8 T% ^& y% {4 h% @        }
( k/ \- u- B& T4 `4 I/ h' L        return element[front];
- p2 Q+ y8 E5 N! T+ [8 _    }
7 u4 k* j+ {3 Q
6 q$ b1 H* A# ~, h9 z    @Override
0 ^7 E- o: Z/ x# |* k    public Object getRear() {
        if (elementCount == 0) {
  J$ R9 q4 U* _/ d            System.out.print("队尾无元素");
            return null;
1 s) ^& u# N8 I# L& u& `        }
        return element[rear];
    }
3 w- ]$ q5 |7 C0 l5 G9 Y
    @Override
    public void traverse() {
        if (elementCount == 0) {
            return;
: j# }: K' k7 A        }
7 h  u4 ?- b, P+ u1 w+ a        for (int i = front; i <= rear; i++) {
3 F9 e* o+ ]4 E0 e* N            System.out.print(element + ",");
9 C, [* r: c, s0 B7 H        }
7 S  a5 F4 S1 t' X) ^; |' m/ c0 p        System.out.println();
    }
7 t+ \. w4 \( k8 N& d}


3、队列的测试
9 S' e7 I8 N+ e" apublic class QueueTest {
  ?" X3 q" T  o) ?& J    public static void main(String[] args) {
2 b2 b; ?2 F+ E9 m        Queue queue = new QueueImpl();
3 y( H4 y9 E4 Y
        //获取队列大小
; x# s  a4 r3 ~; V/ ^, h        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
" L+ {6 ?3 s- z. y) Q, a9 U
- h5 t. x6 M# [3 K        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
" ?$ T7 }; D& L            queue.push(i);
        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
" L0 n+ H! X9 U4 E6 _' ^! n        queue.traverse();
4 }  y+ u4 S6 D" @$ O. \+ z7 A" F        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
; c9 ~' L& v7 I0 d# S  T* d1 Z  _* A' p
        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
+ e+ o( c7 k8 T1 X3 w            queue.pull();
0 U' W2 _5 A" |9 I        }
, |" ]1 F  b# J0 S6 F1 b        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

0 ?# g% M' m/ F! Y# ]/ S+ O
5 L+ Z+ y. Q- n, f. U! u1 O4 j) C        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
            queue.push(i);
        }
1 C5 |. p' |  x" E1 b1 j& i$ Z0 \$ C2 ?        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
8 o; |1 F6 V5 O# l9 `/ g+ Y+ U$ m        queue.traverse();
3 x8 ?) `; s! Q5 I1 ?

: F5 u) Y! I6 D+ U        //第二次出队:取出16-31
% d& f9 I9 s" l# X3 P        for (int i = 0; i < 16; i++) {
            queue.pull();
& k7 C' k9 [6 N; x$ X, k        }
: w: J* L  j" v        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();

/ X6 O3 P$ N, ]9 l" M        //空队列出队报错
7 @! C/ Q( l5 b, ?8 S' k8 I        queue.pull();

; j' {+ ?9 L9 k9 K' z8 T    }
}



' [: X# p$ w& C

' X2 C8 b/ Q& N5 T- v# o5 b1 F
- V+ D& X* ?1 b1 n
9 J2 o) ?) }8 m7 q$ \
& J/ m3 M" R! z3 d, O; H. o
+ ^+ l2 r8 E0 |
- I& [4 R7 |! w
& q! F; ]- x# V
+ Q4 _% N+ D: ^+ c* {3 Y# x

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

/ I7 V  r. k* o: q( X; h