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

杨利霞

( a0 S& O% u) B数据结构——栈(Stack)与队列(Queue)的手写实例
/ n2 q+ g+ j; I
8 [6 ?) R8 n. g; y3 D& k1 j[color=rgba(0, 0, 0, 0.74902)]文章目录

1 o/ W* s4 p5 ?( s7 F
• 一、 栈与队列的定义
• 二、 用数组实现栈
  # u$ e! @! h* ^/ {
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

一、 栈与队列的定义
( L, T! X6 b8 V栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
  c3 M* Q( d. `: u
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
" [: V! ~" j$ e9 P: \
: f+ D! L1 k& H2 p. [* d3 q
7 j, y( y( m  @+ a
' [& F& [4 m; U二、 用数组实现栈1、栈的接口定义
  {  K7 C% M/ ]! S5 p& e% A/**
* 定义栈的接口
9 k! f* i1 o7 o4 ?1 } *
3 [" i( M* a: f8 {% D3 [/ _ * @Author zhuhuix
8 X1 z% n' k$ Q( h/ Q * @date 2020-05-01
$ e+ q) @6 G. U. v, T9 G! A */
public interface Stack {
* Q, \+ E. s/ f) L2 K* N2 Y6 s' v" X    /**
5 \* `! M7 I- h     * 入栈
; y' p" O' }8 I' x5 o4 Z; a; C     * @param object 入栈元素
, g9 H9 G. i8 {( a- c3 Q( R     */
    void push(Object object);

    /**
5 M! o* P- X- L7 N: C; \5 ^# }8 m     * 出栈
     * @return 出栈元素
     */
    Object pop();
! z5 J. i& q3 z
    /**
, N' y$ k! V, L$ h+ q5 n     *  获取元素个数
: a+ `2 s1 N3 R; Y# ], P     * @return 元素个数
     */
6 f6 [9 R' v. K% l! a2 @    int getElementCount();

8 V; B; B+ t" y; S1 K- a3 V, \; U    /**
     * 遍历栈的元素
$ r4 d9 o6 O, z9 e0 L+ p# \  |     */
    void traverse();

}
2、栈的接口实现
; W' T+ E- o1 n. U' z" Q/**
4 k4 W: m1 n; X' g * 栈的接口实现
*
* @author zhuhuix
* @date 2020-05-01
*/
public class StackImpl implements Stack {
       
6 y" Y+ L" J8 |4 i* i# ^  ]    protected Object[] element;

& P# [0 Z$ Y0 R6 E    protected int elementCount;

) ?. e( ?( H3 a* r: M    private int defaultSize = 16;

/ @! x. S+ g; }( z( p6 `$ y( C# ^  i    private int maxSize;
3 b% h( E1 [6 q3 E1 @) c
! O* H  i; S" N- W" }8 }7 z    StackImpl() {
) d' {; L% [7 |" y: q        element = new Object[defaultSize];
- n! u" ?+ i. O( J. i3 h! Z        maxSize = defaultSize;
! O" U' {* d5 w9 P) v; D  N! P) L    }

    StackImpl(int size) {
        element = new Object[size];
5 u4 w6 C( A/ G0 F! w( T        maxSize = size;
% [" R% j- K% J0 }' W3 v- j    }
" z/ G) N2 l! Y1 T
    @Override
) |, |, v( d, F. |  |6 G3 a    public void push(Object object) {
3 Y, x& r3 V& y) W/ g+ x        //如果元素个数已经达到数组的最大个数，则进行扩容
4 u9 g1 z" [" i        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
7 e+ I5 M) e& C7 n% Q) V6 c$ G        }
, _5 {" V9 F' {* e        element[elementCount++] = object;
2 u  X) {5 V" J, F7 S9 F
    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
6 d) N/ y* }( n  ^. A1 B# D    @Override
    public Object pop() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
+ D1 U; x  ~" U6 A* M        }
        Object object = element[--elementCount];
' C% Z9 ]" ~5 t) O        element[elementCount] = null;
        return object;
    }

    @Override
; s4 i- V3 w$ {" ]6 r    public int getElementCount() {
        return elementCount;
" l  }3 c, z5 v( E5 e3 i    }
- i5 z8 A) f4 L
' k; n: v3 j' N; P& ~( P    @Override
* k" o3 S6 L, y2 }    public void traverse() {
8 @4 P( N5 d/ z: `+ t) i        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
% r6 c7 w9 K) T        }
2 G- V( }9 {" r* ~2 q% \! [; @; d/ @        System.out.println();
    }
$ r- p5 E  A) ~1 y  T3 _) n' v}
- W& [! A1 P7 S7 _3、栈的测试
public class StackTest {
    public static void main(String[] args) {
        Stack stack = new StackImpl();

' \( \: [, J" w( x8 e6 D! z8 i        //第一次入栈:压入1-15
1 w9 B  L5 j" M) m4 o- w% R- m$ X        for (int i = 0; i < 16; i++) {
            stack.push(i);
7 u4 v- D$ X) w# D: Z9 ^4 a! j        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
8 ^- Z8 |. g& H/ [, |        stack.traverse();

! H# w$ Q8 \9 M5 F: H        //第二次入栈:压入16-31
- |) E4 ?* k& Z3 X8 j        for (int i = 16; i < 32; i++) {
9 \4 q* I; T- w  B) c7 k( z6 V: k            stack.push(i);
) [) S; S9 U+ J4 v        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
% D5 D$ B  ]& T, M5 j        stack.traverse();

4 ?/ [+ [* T! R9 Q        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
, @+ {  ~# W1 s* L6 a            stack.pop();
        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

9 ~0 o; M  I- d8 p- c' @1 u1 j/ U        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
/ u6 g. y3 \  M            stack.pop();
        }
  p- }, S# {6 F$ D/ e- w+ |9 u        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

# q! U# I3 [5 r; M% e; u6 ^        //栈中无元素，出栈报错
        stack.pop();
, r' o+ o' p4 l/ X& Q
    }
! R4 D2 G, Y1 b0 n) E}

3 a0 r7 d* m+ @  l% D& W


0 t" }! z4 z6 m三、 用数组实现队列1、队列的接口定义
/**
* 定义队列的接口
0 g- V4 ~" `' B$ \+ w+ U* u *
* @author zhuhuix
* @date 2020-05-01
+ f2 P3 n  T4 q3 q; b! [3 I */
public interface Queue {

    /**
     * 获取队列大小
. h, y: @) P6 o. C( }- R6 `     * @return 队列大小
  R1 r% U3 R. ]2 {* f' c9 Y! _     */
    int getMaxSize();
5 ]$ l: `. ~& Q6 a6 H; ^
    /**
     * 入队
) F$ q' l" \. `* V: k     * @param object 入队元素
; d2 B+ o2 [" o' L     */
    void push(Object object);
+ o; @! D/ P8 N1 P3 N8 V7 I
$ m6 R, s3 U: w. R! _1 A: t" R    /**
0 @# u0 B, x8 ]/ P: x9 x     * 出队
     * @return 出栈元素
     */
    Object pull();

. N8 p9 ]+ O( R8 ^    /**
, u, B6 G6 L% i* ~5 ^; A# M1 K     *  获取元素个数
     * @return 元素个数
     */
    int getElementCount();
$ X7 i, u, s% d* t: x; \$ Z! n: K
    /**
# T% ~5 z  _9 j* N     *  获取队头元素
1 @, L- R) e% p- o3 p( T- S9 g# ~7 h     * @return 队头元素
- c2 m" u9 C: i: G; p     */
4 l# P  r& m! v# d    Object getFront();
9 z$ v" J, |- |( I& z
    /**
     *  获取队尾元素
     * @return 队尾元素
- Z; s3 y* L5 [; y* H     */
: r  ~: [' X6 k4 H0 {$ c0 Q    Object getRear();
) I. h  b! \6 [5 D
7 g4 i1 \8 v" h# c! _2 S    /**
     * 遍历队列的元素
     */
    void traverse();
}
2、队列的接口实现
/**
* 队列的接口实现
*
* @author zhuhuix
* @date 2020-05-01
- P0 y8 f6 m* a$ c */
public class QueueImpl implements Queue {
) I) @5 _9 @3 ^0 t( v& \
    protected Object[] element;
1 ~7 Y+ A# R" P8 f6 T7 Z
+ a2 y$ b$ e- d; K% @) |" Y5 @    protected int elementCount;
& Y  \+ M9 x6 }5 `* b
    //队头
; E% a% ?% l5 `; y' x    private int front;
8 j+ J- a* q3 E* ~) i( i/ ]2 ]/ r
5 E" U7 R- h; ?: B    //队尾
7 f& j* u9 R' |' w9 ?$ ^    private int rear;

/ ]5 J( y7 Q# F- k. E    private int defaultSize = 16;

    private int maxSize;

    QueueImpl() {
        element = new Object[defaultSize];
6 M9 v5 ~( y6 s+ S2 ~# D        maxSize = defaultSize;
        front = 0;
        rear = -1;
+ ^. E% G/ d% \5 _$ D    }

    QueueImpl(int size) {
        element = new Object[size];
        maxSize = size;
3 h# w. A. A, R  h0 w& h' a! E        front = 0;
        rear = -1;
    }
) d9 h( X0 l3 V& o, o
    @Override
    public int getMaxSize() {
        return maxSize;
1 @. a- A. X7 Y9 y    }

    @Override
% ]. w- g1 Z) T  P    public void push(Object object) {
! g+ w) V1 E) U( }, i2 i- Z, ~0 g        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
6 I  I- O( I, H* q+ N+ o; `  j            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
( a5 l0 k+ c: N0 r& P        element[++rear] = object;
        if (rear == element.length) {
            rear = -1;
        }
        elementCount++;
    }
# Q* D0 i3 {: I
    @Override
9 V4 O; U7 D  n/ d2 \    public Object pull() {
        if (elementCount == 0) {
7 T' S3 E! k0 K+ s            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
1 {3 R3 l2 Q6 z" q        Object object = element[front];
        element[front] = null;
        front++;
; h8 Q. e9 k, q( E+ [( W0 @# V        elementCount--;
1 s, w$ ^% I: j) ~+ E        //队列清空，队头队尾恢复初始值
: i$ w3 F' E) F0 s& |  B5 v/ ~/ p        if (elementCount == 0) {
6 u+ g) \4 v5 J            front = 0;
            rear = -1;
3 L/ p* |5 W0 h, J3 O* d( r        }
        return object;
, r4 t. H3 L- i; O+ l1 ?" G    }

0 |+ @( E6 F; U. ~5 q6 ]    @Override
    public int getElementCount() {
- S; R: s) a2 E/ U7 E( U        return elementCount;
    }

    @Override
& `# l! m8 e( m6 {, V    public Object getFront() {
        if (elementCount == 0) {
            System.out.print("队头无元素");
            return null;
        }
        return element[front];
    }

' _7 \- f, }6 v0 b    @Override
    public Object getRear() {
7 L/ A, K- v! O5 `+ C: v        if (elementCount == 0) {
            System.out.print("队尾无元素");
% u5 ~4 {0 i0 Q6 d* D2 ~' f            return null;
3 D  L! p$ v6 E7 C        }
        return element[rear];
    }
; r. q4 Z" Z' ?8 v) x% ]" I9 y5 y
' l! X2 |; s7 m6 K1 p    @Override
# E* d- \/ ]) g2 ]+ p1 b    public void traverse() {
        if (elementCount == 0) {
' E( L7 D0 L" W3 T8 n4 p            return;
        }
        for (int i = front; i <= rear; i++) {
# k* A* r5 E* g7 S            System.out.print(element + ",");
        }
        System.out.println();
" t+ P) X. N8 ]* q    }
: F8 R  ~8 W7 p5 p" C! W8 Z}
9 V9 i  U/ y* v( l+ x
, O6 {" `# P& d# R0 F
3、队列的测试
; X  H5 \: g0 Q- ipublic class QueueTest {
5 k$ @. i! V/ O: U    public static void main(String[] args) {
: R3 Y( K  p( O        Queue queue = new QueueImpl();
$ Z3 m+ Y" C9 z4 J1 q0 Y+ |+ b
3 t3 ^1 f; \0 A        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
0 d6 y7 C* _; R% o: H
; }$ ]2 J$ {( W8 F) @" L7 h, ]        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
2 R: |& ]0 Z0 V( |" X            queue.push(i);
        }
, v8 |% L; p( o: D$ [: N        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

. T7 V: y5 g" Z: V        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
' O2 Q% [" a: `$ u  m        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
* A8 j- z5 E, g3 [& A. ~/ k
+ p" P+ K. E0 V7 `! r" @! f
        //第二次入队列:压入16，31
7 f2 k" z- L. |- _8 T        for (int i = 16; i < 32; i++) {
            queue.push(i);
        }
" P0 _& V. _* F+ v7 H- t, C        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();

% `5 ?' t2 I$ r) }4 J8 q
- H/ T5 }) F2 q2 j7 r2 K3 F        //第二次出队:取出16-31
0 `. j4 [7 \4 n/ m1 I9 f* K% \        for (int i = 0; i < 16; i++) {
6 X5 U" A, D) g7 F% ^! v            queue.pull();
8 H6 }% ]4 A- k' y8 e0 u        }
+ f  }1 a' G% q# e) a; b        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
2 n  J: F) h, e% K        queue.traverse();

! B- e( B; b$ F! y! O! q        //空队列出队报错
& L4 [. J2 y1 p+ e, m        queue.pull();
7 [2 S6 P' U2 p
5 I  u6 U3 K1 I9 i  [0 ^    }
+ x% m0 z" F3 {}


( M) z& K& [0 Z$ M9 ^
+ V7 m+ K$ n+ f% g$ ^: O/ w; _5 u




$ s1 m# f$ W& q7 `& Z: o; s

( u5 E3 x$ c; [' J




/ G1 `3 L3 X8 x7 P4 y) F————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
$ o" e" V# z, @9 D. k5 n/ k2 T

6 C4 @9 r5 ^" A3 Q1 ]3 w