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

杨利霞

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

[color=rgba(0, 0, 0, 0.74902)]文章目录

" U( m/ h/ p4 t' L* Q/ j" @
• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    / K( S9 I$ D7 p9 y+ D
• 三、 用数组实现队列
  , a9 F7 |( M; ?8 L. R  W0 @
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    $ [' r( s3 M5 B2 u4 r6 n

3 @3 G( q! {) s7 h8 c, M
1 J( d( W+ @! D  V! D一、 栈与队列的定义
$ F! Q3 Y; g* J" ]" D, E% _, L( a栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。

　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
' G" W! b* @4 i, O  f: ~

; S! `2 W( G, s  H' ~5 [* k
& z4 u8 C8 W  U! ~8 E5 c2 _' v2 T二、 用数组实现栈1、栈的接口定义
/**
9 M6 q) h8 C$ s) l! i3 ~1 m * 定义栈的接口
*
* @Author zhuhuix
* @date 2020-05-01
* f% h' T. _. z. `$ Q  ?0 C' v4 ~ */
public interface Stack {
4 g3 P! ^* }% u8 t; o9 v6 X3 w8 s: N; P    /**
     * 入栈
     * @param object 入栈元素
' I4 S" l( o4 ]8 [- O/ J- h     */
    void push(Object object);

& ^6 c8 F/ R2 Q    /**
% j) _2 B- v! N: q! e. o, e$ O     * 出栈
     * @return 出栈元素
+ p: |" x5 J% h6 G6 b7 d4 |     */
    Object pop();

' ?6 L' r2 ^$ r" s    /**
     *  获取元素个数
7 a1 x. M: _3 Z$ `/ p# Z: t, T     * @return 元素个数
! d) d& m+ V% I6 X  [6 b     */
    int getElementCount();

    /**
- d2 A/ ]8 l7 w8 K8 ~4 ^# N     * 遍历栈的元素
6 d" M4 F. T: R; G' K: a0 a     */
    void traverse();
, ?, ?9 B5 ]% [' U- b0 c
}
/ i1 D2 w; ~3 o1 R' K7 q' W2、栈的接口实现
/**
) F; m& ~* o) S( U9 [ * 栈的接口实现
*
# {0 X  K7 _# ~# Z' m/ H. T* i% [: F4 n * @author zhuhuix
* @date 2020-05-01
*/
public class StackImpl implements Stack {
       
! U  `' B* {0 T5 B4 V    protected Object[] element;

    protected int elementCount;

3 C1 K, C  [) n: {0 ]0 o0 r# |, }    private int defaultSize = 16;
3 H6 M4 L! E6 j
    private int maxSize;

    StackImpl() {
: g* p2 N2 f5 T! U0 x9 I        element = new Object[defaultSize];
& v0 d4 \9 K- ^9 H( M        maxSize = defaultSize;
    }

% X7 e: n$ [# k' m# B  e    StackImpl(int size) {
! w2 _4 h" H/ v0 \        element = new Object[size];
" N# m$ K0 ^, X0 G$ B' {        maxSize = size;
( E- {7 h" r8 C% i  b1 P    }

    @Override
# o+ |$ w6 A2 D/ o7 i! ~) I6 G) q    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
6 L  h2 V/ T8 \& f8 M" a2 `7 E        element[elementCount++] = object;

    }
. ]& x0 x' `6 v* o7 [2 Q        // 本代码未实现数组的自动缩小，具体方法可参考JDK
# ^. p; u5 [% b$ v! O    @Override
, ~2 t5 J. u1 C5 z    public Object pop() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
9 c; N; ?4 o. Y  B7 x/ d        }
' E" V0 z; X8 d+ }  {5 v, t        Object object = element[--elementCount];
: }; r; Z' i5 q$ ~! ?% m' w2 p" i, p        element[elementCount] = null;
0 d3 }6 f6 I, G2 q8 |! k( Z        return object;
8 H! L* ^4 l% }/ l    }

# W& W' u6 X2 v; g3 k, R- `: G7 T    @Override
    public int getElementCount() {
- U& b7 I/ Y+ t# |/ F9 b  q        return elementCount;
    }

' ~& N( v) V+ T, f: R    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
0 Y6 J6 y. a! s# r7 W2 q        }
        System.out.println();
" O  [" x0 h9 x/ |# v    }
# k" a- }1 Y& p# T* s}
3、栈的测试
5 w" L6 Y. w. k/ s9 @public class StackTest {
    public static void main(String[] args) {
0 `3 }& C. X; f" I* X% T: P0 e        Stack stack = new StackImpl();

        //第一次入栈:压入1-15
2 a/ `! E  G7 X" y3 i        for (int i = 0; i < 16; i++) {
            stack.push(i);
        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
. o" d3 W  D1 k7 t* T5 T' `        stack.traverse();
/ m1 j) }  A) R8 u+ n8 A$ o/ l$ A
4 e# J0 T4 _( V+ p# Y8 |        //第二次入栈:压入16-31
% r& c! [6 Y4 D8 y: ?        for (int i = 16; i < 32; i++) {
+ c6 _3 ^$ r3 H6 a            stack.push(i);
        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
% K) @2 w4 c4 C* G        stack.traverse();

7 Y4 a; d1 Y% B. H( W6 g8 R        //第一次出栈:取出31-16
$ F" K) r1 p( i! K        for (int i = 0; i < 16; i++) {
            stack.pop();
; I- m/ u# Y4 [$ \# K' ?/ u        }
" }  j+ n( z& D* }8 ^5 }! e        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
# Z: n' P9 O& {6 t
        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
4 C- s7 @5 R# a9 b        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
5 {5 Y) _# x+ @  _* E$ B4 |
' a" ?2 Y9 Y+ J7 d' k- C        //栈中无元素，出栈报错
4 p; k0 M+ i  j& }4 j( Y' f/ o0 u        stack.pop();

    }
4 d& m7 g) {0 q. y! ?2 {}

3 u( n% R& J2 y! L* }
* U2 R0 a6 A) D4 W, o$ r

三、 用数组实现队列1、队列的接口定义
/ W+ k9 q; R' {! t0 V/**
: G  x1 p- N& G: `; G1 I * 定义队列的接口
*
; y* C. m8 W/ P& b * @author zhuhuix
* @date 2020-05-01
6 _7 L6 k; q1 K9 z( E */
8 N6 A* l0 I5 c/ V+ Z  e' C8 Spublic interface Queue {

    /**
7 K4 Q8 b; `7 Y& c1 o* d     * 获取队列大小
# ?( c# g/ M" G     * @return 队列大小
: ^' C" f+ ?# G! G     */
    int getMaxSize();
; E4 B5 h4 |# F+ r6 A
) `4 ~5 [$ j$ a# h! {4 B    /**
     * 入队
( q) b7 `6 V6 \( a5 @     * @param object 入队元素
4 _+ l) w. H$ G( z8 |' V% }4 z- e7 R8 q     */
    void push(Object object);

    /**
     * 出队
: ]) m. S- W4 w, d0 U6 T6 ]     * @return 出栈元素
, I8 F5 R7 M. `# w4 \1 V- G     */
    Object pull();
* O/ C$ F' T4 |3 b$ P: j4 P$ G
, d+ S  H1 G- Y+ O% L% |; g    /**
: i6 k& H/ j: [: a  f! `- L0 L     *  获取元素个数
0 [) o& u, d4 b" m     * @return 元素个数
% T/ x5 J# P0 U' p9 z( {% _4 J  s     */
    int getElementCount();

8 }8 J! Z; S" `% M# M4 J    /**
     *  获取队头元素
     * @return 队头元素
0 w$ f  q/ R. O     */
9 _- D7 z/ c+ F. Q0 I" z3 K    Object getFront();
/ ?4 H1 D) @) F7 s$ p
7 F/ ^: l& T4 o% V$ K$ S7 g- z    /**
     *  获取队尾元素
2 w. U5 Z8 E6 R& b" _     * @return 队尾元素
     */
    Object getRear();
& q! G4 e8 r5 ]' m/ [3 O
    /**
     * 遍历队列的元素
1 U# E* u  t7 ]0 [% g3 @     */
    void traverse();
}
  L% f9 J  I6 k1 m" H0 E. |0 k5 ~2、队列的接口实现
0 u4 Y# V( N' h. J8 o/**
6 m6 {% h3 E$ ~9 C: V2 m * 队列的接口实现
" K. [  g! p4 x! O6 | *
) K: ~/ n& d& ?% D. }9 g * @author zhuhuix
* @date 2020-05-01
% N. l2 m3 _" }$ e% m */
public class QueueImpl implements Queue {
5 K  w7 i7 M1 A
) p0 R0 p" M# W, X2 M1 N. o$ i    protected Object[] element;

    protected int elementCount;

8 d  n: N2 F2 n+ e" q    //队头
    private int front;
9 X. B$ ~# ~" C' n0 }
) P" c1 W# c4 ]" D    //队尾
    private int rear;
' ]+ E$ A) k; W; _
    private int defaultSize = 16;
5 @, o2 A" L: U3 k2 `: t: a% U  q
+ D5 U) [! X" k6 N0 ?! q    private int maxSize;
& {( s% A: T+ I9 L/ [% P
( @0 S! @% W1 N& d( S- c/ ~5 C6 j    QueueImpl() {
        element = new Object[defaultSize];
- j/ f, ?+ m( C8 O7 p0 f        maxSize = defaultSize;
- |; @# m9 b9 O4 H9 y! W% k9 \        front = 0;
6 d" R9 T2 m- a  r' _0 o        rear = -1;
    }

    QueueImpl(int size) {
        element = new Object[size];
        maxSize = size;
        front = 0;
        rear = -1;
$ }- s: x4 ^- y0 i) B    }
5 p, T' |% Y7 z: Z
5 c5 _" d6 P: n+ b9 S7 t; j: Z) Q! b    @Override
    public int getMaxSize() {
4 m6 Y' H! V9 v        return maxSize;
    }

    @Override
7 a: W# G9 y- \: B7 }+ T- B) z7 x    public void push(Object object) {
. J6 O2 g# M5 L( L0 h! q3 N        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
        element[++rear] = object;
9 y# Y6 K  L. v% E- \# e        if (rear == element.length) {
            rear = -1;
        }
        elementCount++;
    }
0 i' c+ b  {3 j8 ?( H: J
5 h$ g2 M$ m: c( A7 q% |8 a    @Override
    public Object pull() {
% w9 l# f4 B4 Q        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
        Object object = element[front];
# K& X( J3 o& o, X0 \        element[front] = null;
        front++;
        elementCount--;
        //队列清空，队头队尾恢复初始值
7 E7 I! x+ U# U7 q1 W+ w  V: Z  v        if (elementCount == 0) {
            front = 0;
            rear = -1;
4 s3 h8 S3 A! O% M4 T9 i7 X4 m        }
        return object;
4 u& q8 R6 l* s    }
. O% n9 y' \+ Q# j- [9 A
    @Override
4 l! g& e% S. v  f5 y  E    public int getElementCount() {
        return elementCount;
    }
1 C) |+ g  b, f0 K6 a: q& S
  |; j( [' G* V6 h    @Override
    public Object getFront() {
        if (elementCount == 0) {
            System.out.print("队头无元素");
            return null;
3 F) X. ^; ]3 W& J        }
        return element[front];
  F* R) k0 }0 [$ ~( U; ]    }
% l9 U' t" R; P/ j6 r
    @Override
% }- l% W" ]' d# q( W    public Object getRear() {
        if (elementCount == 0) {
            System.out.print("队尾无元素");
            return null;
        }
/ n7 F; J0 F( t* W5 S& e" P$ M3 c        return element[rear];
8 c$ R/ b8 `* p) [7 t5 }7 E9 W2 W" H    }

) W5 [. y1 e9 ]+ T. J, K$ K1 l    @Override
    public void traverse() {
        if (elementCount == 0) {
; B& m* v. ]7 e) Y9 ]( a3 \            return;
        }
        for (int i = front; i <= rear; i++) {
2 D9 W" ^3 y8 m: N0 ?' R            System.out.print(element + ",");
        }
; i/ \9 f5 a; t; R: `        System.out.println();
9 P) S1 }: ]; w: V    }
}

& R( x8 K/ h1 ^# M8 Y, a
1 X! l8 T+ [+ b2 N; m3、队列的测试
" `( n  y$ ^2 L( [public class QueueTest {
6 m% O. n& w% b9 @    public static void main(String[] args) {
        Queue queue = new QueueImpl();
! I0 r" {! [8 H
) o, O# Y, J. [6 x5 G/ {        //获取队列大小
: V$ X, [1 ?" h5 ^* d        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
2 r2 _! |+ L6 x) {" f' U$ z
" O5 T2 ]& L  e- _1 p        //第一次入队列:压入1-15
% l+ Z' ~( R3 p' x+ S  B, |3 u1 Z        for (int i = 0; i < 16; i++) {
/ @4 B" b* R* ~            queue.push(i);
* N1 G& z1 ~. i/ h6 M) W        }
6 I9 l/ ^. ~$ h7 U. ~        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
( |3 C* a5 l6 u( I
        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
; r5 J' D; J  l            queue.pull();
        }
2 H0 Y4 ?: o/ K- H        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
3 S1 h+ a* i( k1 i* J% S        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
) @3 q  |3 n2 Z1 T

$ b  P9 ]% M2 F2 V. y+ z$ s0 X0 `        //第二次入队列:压入16，31
& D3 S* U3 Q' v* i. i- T7 H# t        for (int i = 16; i < 32; i++) {
# @) c1 c4 V8 ?; c2 n, {4 a' h3 e            queue.push(i);
        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
* O9 n7 b7 t; j8 t        queue.traverse();


        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
            queue.pull();
% R6 q( |8 }$ ?5 p& d1 ]        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
/ N: u6 P# E; L" Q9 E        queue.traverse();

. s! Y5 C' m4 q+ V) F        //空队列出队报错
        queue.pull();

    }
* t3 O1 {; ^. w4 [9 T}
0 M1 S) s8 j' b2 Y
$ ?! U! i: Q' ]; @9 g
0 v: Q, K% L& |) Y2 }: e7 p
1 \( g3 g0 n; X: v* S
! {! N% g$ I( q) R, a% Y. t0 V

0 |/ E8 E4 |0 o) Y! K
4 q0 Y  Y; c) L, H

# d5 ?+ }" W) e' }8 z! B

3 V2 C8 h/ ?" R8 P) l3 @$ h' _
. [  e: S& x9 V# E1 W

, w  S* ?5 S4 [8 O, C) j
————————————————
3 F. V4 a3 I, h  O9 g1 J+ @版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
  m0 N5 E; X8 u: @* x$ A/ P  P原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785


6 \% y+ p* r0 V* B* G9 T! Y