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

杨利霞

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

2 I. `" o# n( E( C6 T# w9 L! w  M[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    ; S5 |3 y* ^0 k
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    8 R( n; t: c- Z4 ]

# z+ [4 ~8 t" A9 L# D
一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
# ~* t3 j) E* R3 w
  q$ M6 u  o6 m. h　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
5 r$ F1 g, D' _6 ~
! a4 N4 R. ~" c( p3 i

* L7 c4 `% @2 a) |5 @二、 用数组实现栈1、栈的接口定义
/**
6 D8 e) f; A: [0 z * 定义栈的接口
*
* @Author zhuhuix
8 E) O5 u0 e* t * @date 2020-05-01
2 |/ ^+ D4 s  A" `& u$ T% E: `# J */
public interface Stack {
    /**
     * 入栈
     * @param object 入栈元素
8 M7 i5 h3 G" a5 a& c6 y     */
% M2 b) L2 h( \% o% y' l    void push(Object object);
- [) @& b# A! [" S7 v2 o
' F$ y6 m. `$ s$ w1 `6 R    /**
# C: P6 N/ J5 M) h     * 出栈
     * @return 出栈元素
& L. x: s" H! H; Q     */
    Object pop();

* f8 m" @3 ~5 L3 A    /**
4 t8 u6 o6 D$ @) }% V, N     *  获取元素个数
# {  ?8 `: p3 }/ D     * @return 元素个数
     */
" F: E6 X4 V) m- g) ]9 W6 o0 {6 X    int getElementCount();
4 L$ q1 _! u, \3 j
  t) F* v, O- w5 C+ q  O    /**
- H+ M" v1 T; w/ e5 V. |/ g& f     * 遍历栈的元素
) j7 c3 R6 G. I+ M0 r' F     */
" Q3 B( z! R4 f3 o( z& i5 A    void traverse();

8 n: ~' L0 P9 P& e5 R# c- ~5 n8 N}
2、栈的接口实现
/**
6 y9 b* x3 ]5 t( S0 p * 栈的接口实现
*
6 U2 R8 [- R" K# n% ]/ }* N * @author zhuhuix
* @date 2020-05-01
9 A, T' G1 v2 W7 j& G, h */
  t; I5 m3 o/ v6 u5 k, C0 x1 Lpublic class StackImpl implements Stack {
       
2 j/ i) y2 p9 L    protected Object[] element;

6 c6 G( m6 P4 w2 L    protected int elementCount;

    private int defaultSize = 16;

8 \8 Y. v" p/ W, T    private int maxSize;
/ t6 R( Q  L/ y) W& z0 ?, o  p; t
    StackImpl() {
4 I$ W7 L: T! A) `        element = new Object[defaultSize];
8 N  A* |! x0 k& Y" S& S, |        maxSize = defaultSize;
* z9 _  C! X( _: L! X    }

    StackImpl(int size) {
        element = new Object[size];
        maxSize = size;
    }

    @Override
) B5 l6 l- D9 {    public void push(Object object) {
( L9 I) O1 M+ p        //如果元素个数已经达到数组的最大个数，则进行扩容
6 b$ X' [& r1 l        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
: ?% ?/ u, M5 K* m, Q        }
3 [$ b- y/ F# r. n' b+ [4 w. P        element[elementCount++] = object;

    }
) k( A: _: e$ i+ J3 ^        // 本代码未实现数组的自动缩小，具体方法可参考JDK
8 A. A. P- e9 q& R  J) Z    @Override
    public Object pop() {
- Y( ?  n7 z5 N+ J$ c        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
6 n% I; c1 b( x' e5 I$ g0 K        element[elementCount] = null;
5 P8 v* ]1 \) V; q3 e        return object;
    }
. C/ F+ c8 U: P! r0 l' Z1 l
1 z5 ?( r8 {7 \4 ~1 a; F. r    @Override
    public int getElementCount() {
        return elementCount;
8 A7 D. H/ [% D! ~; \6 y    }

& y  @/ M6 x, y( K8 p$ m    @Override
9 L# _( X: U: Q6 _0 F& P/ w4 X( w    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
- k, \$ f/ P( M$ K7 Y            System.out.print(element + ",");
        }
+ t9 m2 }% N/ g8 @" H        System.out.println();
9 E- S, ^( ]; \# a1 o* ~    }
}
3、栈的测试
; T' k' K) e% D" apublic class StackTest {
& |1 \7 n# w3 u  E! I$ P6 L    public static void main(String[] args) {
( k9 ]. d/ R! }* X        Stack stack = new StackImpl();
2 E: i/ ]- R; I3 q, v
        //第一次入栈:压入1-15
1 L- q6 _/ i" g* e$ {$ M        for (int i = 0; i < 16; i++) {
            stack.push(i);
1 A  Y' Q$ I. T# Q& E& S        }
7 @6 F8 i; h4 D9 q- b        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();
) r) y- [- R# n
" Q  ?# k: d) D+ H+ F% h        //第二次入栈:压入16-31
* R/ t2 e, u7 O2 n" W) ~2 H) h        for (int i = 16; i < 32; i++) {
            stack.push(i);
        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
, L( T( W$ y6 X: ^! D3 n8 ?) [; m3 ^
        //第一次出栈:取出31-16
# Y! k/ D/ `  K1 P, O        for (int i = 0; i < 16; i++) {
$ X6 x/ ?! M+ @  l* C+ r" j            stack.pop();
$ \0 C$ K: \- a7 z        }
/ s) J% O0 y" d/ u* C, E        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

! S$ `& o" ^6 i/ K/ I6 O! ^        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
; V/ o/ d% m8 ~, D            stack.pop();
        }
. Z. r5 W$ E* S& ]        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

* n: ?" `6 W3 _+ g; ^/ K0 G        //栈中无元素，出栈报错
0 F5 \9 g; r. w* [# u8 Y9 C! h        stack.pop();

8 Y# `5 [2 S. e    }
4 L0 Y6 |; V( h0 [1 x}
* e/ b6 a# G3 U
$ l: v) C8 K0 F0 F


三、 用数组实现队列1、队列的接口定义
2 l" K* ^) ~: x. j; [4 ?0 A/**
- }: x5 v9 V8 f0 }: p * 定义队列的接口
*
* @author zhuhuix
* @date 2020-05-01
*/
# F) x6 |1 d: cpublic interface Queue {

    /**
     * 获取队列大小
     * @return 队列大小
     */
' C$ i/ e7 E: V" @    int getMaxSize();
3 A' g& {' I1 a$ z% P& C! f
$ V; c. r8 b# g4 V8 W3 T& l; ^8 w    /**
     * 入队
( V2 V- G  e( m     * @param object 入队元素
  d- w  N- u/ ?1 L- J     */
9 ^$ e/ S' n4 j% t) X9 z    void push(Object object);
5 f: u1 E1 W# c; N( t0 o
. }2 ~$ \  j0 z0 y  x    /**
     * 出队
8 g5 W* \8 J% w2 ]  t# v     * @return 出栈元素
     */
    Object pull();
) m% z! j* Q! b# m
    /**
     *  获取元素个数
     * @return 元素个数
4 X: k+ R& ~8 w! c% U: s( k     */
    int getElementCount();

0 T% E" z& s3 ~1 o7 o( N5 @    /**
     *  获取队头元素
5 ?& f2 W, ^* H3 B$ u. k     * @return 队头元素
2 O* ^' e& n9 c% U0 s! B( f     */
    Object getFront();
0 u$ _: a; i7 I0 B+ }& D/ x: N
    /**
' a9 w: [+ l( O, }$ ]/ [     *  获取队尾元素
     * @return 队尾元素
. m3 F9 H9 a% J& B2 B     */
1 F% }5 \% T. P8 N    Object getRear();

8 K) L" e( M( i4 n4 i; I. W6 R% Y    /**
; f1 C4 v8 F5 M& l, H     * 遍历队列的元素
" \9 s4 v  N; q/ B     */
+ m. x1 c2 D/ _    void traverse();
6 _7 B1 _: I# v# u% b}
2 X  M) I- s7 H6 d9 M2、队列的接口实现
; a4 l# O3 U% f/**
5 K; v$ O0 ^! [7 G+ h * 队列的接口实现
# P4 c% i) X- s' G6 ~: R4 |5 g *
- k0 T& O" g$ G8 h: M * @author zhuhuix
( `! M0 E6 y6 F * @date 2020-05-01
6 P0 Y" W. n8 u8 p! n* ]2 I2 y */
public class QueueImpl implements Queue {

! K, f9 `* X9 H+ o8 C% t    protected Object[] element;
- [3 `' U' V) g4 _8 R
( b1 J/ I( y7 r" [    protected int elementCount;
& H5 x4 M1 S4 ]5 h+ k1 P
    //队头
    private int front;

    //队尾
- B6 t' S9 v0 O0 x' {7 `    private int rear;

# N' M+ p, r) F" p; _    private int defaultSize = 16;
; F) z0 R+ \$ U4 v/ S& {( @
- b0 Y# ^0 J6 P5 k    private int maxSize;

    QueueImpl() {
$ `7 ~) V: G7 r' y- \. _        element = new Object[defaultSize];
        maxSize = defaultSize;
/ ?( j' N# j' D- _+ \% \        front = 0;
        rear = -1;
5 h0 P0 Q: i* H6 E. n( M8 N    }
" L. J  ?, R3 O
! p! T. R( f' F, b" a9 c! `    QueueImpl(int size) {
0 A/ R( J4 }" R        element = new Object[size];
, Z/ g  z* B  e        maxSize = size;
        front = 0;
        rear = -1;
    }
9 h9 f9 B2 C  N. U- [8 m
    @Override
    public int getMaxSize() {
7 q; |8 |6 j8 M! ~2 L  l        return maxSize;
    }

' a% p0 M) |  z" D    @Override
" j! g5 u; N. U    public void push(Object object) {
# l0 s' d* q7 G6 G        //如果元素个数已经达到数组的最大个数，则进行扩容
4 [. M& _- R( {4 t; k% {# x        if (elementCount == maxSize) {
2 S! _& `, ?1 k6 N/ E            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
6 k$ {& Y5 e9 c% j; n        element[++rear] = object;
        if (rear == element.length) {
1 }2 G* J, v; M9 N' m- Y- ?0 y            rear = -1;
9 C6 E+ C" a* w        }
        elementCount++;
! n1 F. K' |: ]' Q    }
8 U6 u3 {1 [7 t: ]* f
& p% E2 Y4 M8 _. Q# E    @Override
2 x: s& I0 t  N/ S7 I    public Object pull() {
        if (elementCount == 0) {
& j2 S  I( E! y! f+ `            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
        Object object = element[front];
) k/ C6 u& [/ @7 A3 p) V3 {        element[front] = null;
        front++;
" g( [9 u+ b, e9 E        elementCount--;
( k  [4 i* J8 }2 R        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
+ p/ A, j. R& k) @# a0 ]            front = 0;
            rear = -1;
" P8 l7 h; o8 p6 H        }
        return object;
    }
. @2 _4 V4 |: ~4 u* h
, B# ^) m3 i- R- V( b2 Y    @Override
    public int getElementCount() {
& ^4 g! s* [5 S% l        return elementCount;
" ~( Q- I7 o2 D* S' @    }

! R7 m9 m8 K4 Q* R    @Override
    public Object getFront() {
: R" Z3 N3 M# @3 a( G8 A5 }8 F        if (elementCount == 0) {
& z& Y4 h2 ^' U% `5 b$ _6 W            System.out.print("队头无元素");
            return null;
7 w1 r7 n3 s1 b) U( q        }
7 A; n% u6 p! |/ T8 W2 y        return element[front];
    }
4 l3 m( }% C% [- |* J7 h
    @Override
    public Object getRear() {
+ j5 I+ A' f6 D8 r) F+ t        if (elementCount == 0) {
            System.out.print("队尾无元素");
            return null;
        }
        return element[rear];
! F# i2 W0 J. v7 y3 m. t    }
  I- q* N! p% o) @4 B! _: |
    @Override
0 b, f" O+ ?: [9 }8 s8 @- A    public void traverse() {
        if (elementCount == 0) {
            return;
& e. z( Q% V+ \" f+ ?- O" _  E        }
6 o- K. W, Q/ E5 U, D0 ]        for (int i = front; i <= rear; i++) {
7 M: V" W* C5 P* c# H            System.out.print(element + ",");
        }
        System.out.println();
    }
/ M2 @- \$ R) |+ Y  P- M* N  [}

- L1 k3 b7 \; a/ y7 s) Z8 E
3、队列的测试
% o( @0 U1 r6 r* H# U6 ipublic class QueueTest {
    public static void main(String[] args) {
        Queue queue = new QueueImpl();
  @7 n$ S$ ~; K% A3 V! w2 ^, C
        //获取队列大小
! h& \- v; Q1 G6 o; A4 N  ~        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
! b1 |/ V! u" t. W8 p0 V
        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
1 B" i  G5 @/ G4 }- b            queue.push(i);
        }
! O* X) n3 |$ B5 J        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
, @( s4 k: V. G( q( d        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
7 }& l# h' K1 r8 K7 a        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());


        //第二次入队列:压入16，31
6 O; S* V% G: l' S# w- c8 D        for (int i = 16; i < 32; i++) {
            queue.push(i);
, w4 Q/ u8 ~- p$ f2 k/ S9 W% A        }
+ q* s2 u; y; k& p        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
8 ^$ V* k) g  O2 [7 a        queue.traverse();


! L) T* C0 w+ i; Z; R- X% Y0 ]        //第二次出队:取出16-31
- t- R# u/ `+ M; b9 X( Q3 D" I2 a        for (int i = 0; i < 16; i++) {
6 _% [6 r- o, y* Y            queue.pull();
        }
3 I* d* C$ C2 |5 s        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
. X: D, X; g4 m0 }) @: d3 y        queue.traverse();
. A" ]8 ^* C; f
1 S6 q3 Z; J4 P* S! `6 k  Z1 T        //空队列出队报错
        queue.pull();
8 f0 k; X3 d/ y2 q( F! R- Z( D; G
    }
* ]: e# y% }- j( D}
5 T# R' Q& e" w


5 |% g9 @* F& n- n6 m2 \
8 B0 r- A, \6 h6 f  Y" x) n



- X0 O! D4 V4 g! N. f9 Q  d3 y2 B
  Y6 g# {1 R4 h+ ~) m

0 \$ `# h! x: I, p4 `. f
; a- o! g$ A3 R& r+ {4 _$ d


————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
" P  _7 L# I0 F$ a, _. _) [8 F* C
2 \* k) P0 a5 Z1 [" Q5 G5 R* k1 f$ g
6 T; @6 K5 V4 w" L/ w