数学建模社区-数学中国

标题: 数据结构——栈(Stack)与队列(Queue)的手写实例 [打印本页]

---

作者: 杨利霞    时间: 2020-5-3 15:29
标题: 数据结构——栈(Stack)与队列(Queue)的手写实例

1 y5 k& E( Y, z, S* N, B# x( R数据结构——栈(Stack)与队列(Queue)的手写实例

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

: [# |" S8 F4 @) \0 W
• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
  k- G. z3 ^' G4 c3 Q
4 G6 q- X, ]* F( Y! Y　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
$ x  z! t/ l! s9 D9 h5 \- R) |


二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
*
* @Author zhuhuix
* @date 2020-05-01
*/
, ~/ }2 M! f* d+ W  wpublic interface Stack {
" f( q% L' p  F; u    /**
3 i& x+ q- z& u1 r& P- I, v     * 入栈
. S# G% t/ ^( ]3 O; P2 {# {# p     * @param object 入栈元素
     */
    void push(Object object);

; S5 x, r8 y0 Z/ o: }0 S    /**
8 ]/ E8 O( E7 S+ B6 N, z     * 出栈
     * @return 出栈元素
     */
    Object pop();

% o: H8 X6 K& @+ x    /**
7 b7 T2 g( S5 ^  J/ i, k     *  获取元素个数
     * @return 元素个数
( D% C4 s$ r  _3 L0 q& ?, G* |     */
1 O  H, f" }1 i  G% n/ l    int getElementCount();

3 w1 s1 w" O* C8 ]- {3 y" F    /**
3 c. N; T: L9 ^0 i     * 遍历栈的元素
; u  k# C1 l& d5 }     */
* W4 Y. V2 Z% T- P    void traverse();
3 E; J: K& {5 A/ L& l
}
1 k3 t, a0 P* ]0 o" q  i2、栈的接口实现
& k6 D( f( u' y/**
* 栈的接口实现
*
% T9 P0 g0 b; n" y; I * @author zhuhuix
9 }; n  o5 S* i! r6 j- z. o( v0 p * @date 2020-05-01
6 @( E: W' K) V' b: C */
! z% B3 V: R; @6 hpublic class StackImpl implements Stack {
* V8 a' B3 F% c( K; s, N       
    protected Object[] element;
8 q* n! Q! w1 h7 H5 }  ]8 z5 T
: {- K/ j$ F/ X4 w; H2 f# a    protected int elementCount;

& }  c  o: T2 }+ m    private int defaultSize = 16;
& i. h& H' g- g5 Q% V
+ {% f" P& O, e  Y6 x2 d2 H    private int maxSize;
  ^( m2 Q( x0 }8 C3 s- g
; ]3 k3 X9 |# z. v    StackImpl() {
. K4 V! o; v  \; W        element = new Object[defaultSize];
        maxSize = defaultSize;
    }

2 B; f. h/ ^) Z1 d  t2 h) k/ |4 k6 P3 M    StackImpl(int size) {
( l( n/ K1 v1 O) X+ Q5 F! a5 [        element = new Object[size];
        maxSize = size;
' g/ n; ?6 z! J, s: Y    }

    @Override
; D3 ]( L9 J+ R  W+ j0 |    public void push(Object object) {
+ H3 O. E1 a1 t  \  ~+ L        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
/ d  m1 A, y& y. Y            element = Arrays.copyOf(element, elementCount + defaultSize);
  i# J. K- ?+ u! ], g        }
! o! d: D2 M6 |/ ^" U$ B0 W$ ~) N        element[elementCount++] = object;
: s+ p3 _* m: I2 {% a$ l
: o2 j3 M' I  ?    }
. T  [6 q% V/ w2 u0 ~% F8 L* g        // 本代码未实现数组的自动缩小，具体方法可参考JDK
7 V+ f# ^, q- U0 v    @Override
9 S  N* H( W# _( d3 G  \4 C5 S# M    public Object pop() {
        if (elementCount == 0) {
% A2 s; w7 s; N            throw new ArrayIndexOutOfBoundsException("栈中无元素");
/ w' E1 i5 i9 `8 k/ n* w        }
; y, H! B4 ]4 a- l4 Y        Object object = element[--elementCount];
7 B- u) a9 n. C+ ~. B( m5 V        element[elementCount] = null;
        return object;
    }

    @Override
    public int getElementCount() {
        return elementCount;
7 F, J; k: c: D2 J1 R. C    }
* `) D7 Q2 w/ @7 }/ e; G
( y9 P- e* x' d  u3 R    @Override
# h1 b1 F# W) l4 N6 M2 |- E    public void traverse() {
* a3 r0 z# ?2 S2 F0 U+ m+ H/ Q        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
        }
        System.out.println();
    }
}
( t* ?2 X# v  k% F3、栈的测试
* C$ q! _& W; K- ~$ p8 O' qpublic class StackTest {
    public static void main(String[] args) {
        Stack stack = new StackImpl();
: Q; P% H4 T5 I/ N
        //第一次入栈:压入1-15
        for (int i = 0; i < 16; i++) {
            stack.push(i);
4 g9 k) N: {5 s. K/ C" r, U! {6 m6 l* C        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
$ _! J# c( ~6 S* Q# I        stack.traverse();
. A/ x- P" u1 p
        //第二次入栈:压入16-31
+ G9 S% e& w( _8 V        for (int i = 16; i < 32; i++) {
            stack.push(i);
. X( [2 x1 A0 D7 [6 j  s        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
+ ^( E: }$ v/ P8 h# T        stack.traverse();

' Y, i" t$ W1 ~1 S+ |/ Y        //第一次出栈:取出31-16
! k5 C% f8 B( c" y4 Z0 @        for (int i = 0; i < 16; i++) {
5 o: t& u, o$ T( {4 ]+ [" @" B            stack.pop();
/ d$ X' _9 K+ L1 m2 E        }
4 r. L3 Q+ R8 v* O% y        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
7 p: F% u: N" \( u        stack.traverse();

        //第二次出栈:取出15-0
& x& |- B: w  G' y1 [        for (int i = 0; i < 16; i++) {
7 _+ D# r) Z$ P) }( D5 t            stack.pop();
        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
3 a6 g# ~" y& \" k        stack.traverse();
8 @$ Z- C( J0 `) _: A  K8 }
. q( s; s* B! ^: _+ R7 n0 O8 K/ E# f        //栈中无元素，出栈报错
        stack.pop();

    }
}
( _; B1 Q% a* G, n( V


) v$ ~$ S4 Y( {, v; I( E! O5 r+ M
4 ~7 P  ^* p9 S9 x三、 用数组实现队列1、队列的接口定义
/**
) O( F! U0 w5 n * 定义队列的接口
2 V- g! m* O# P( ^8 @ *
* @author zhuhuix
* @date 2020-05-01
*/
- u* @5 e  Y4 [! F$ W" Z8 j* Vpublic interface Queue {

    /**
     * 获取队列大小
     * @return 队列大小
     */
" f0 J* P6 p! {8 L  y    int getMaxSize();
9 u! a! u: f: J3 C4 ~
& k' ?* W. F( n) k7 G1 X    /**
1 ~" m( c, t, M1 ]     * 入队
     * @param object 入队元素
. V7 e1 O; w& }     */
    void push(Object object);
" F+ [0 }7 v( `( U
1 q9 M# H1 y9 v9 d    /**
     * 出队
! S( @: r$ u, E2 ~     * @return 出栈元素
/ s3 D6 b. E1 k2 [0 a+ ]. b& j     */
    Object pull();

- j1 B/ B$ f6 Y% j6 f+ k    /**
     *  获取元素个数
     * @return 元素个数
/ |) n$ n' U) w1 I3 h( m     */
7 U) _$ o- ]( a0 F    int getElementCount();

    /**
     *  获取队头元素
     * @return 队头元素
     */
    Object getFront();

4 n3 l9 Q* f! u( f4 T    /**
$ m4 B# v$ @: }5 C     *  获取队尾元素
     * @return 队尾元素
* _2 e' S( [7 h. ~+ y5 l# @     */
* \! r  ]  _+ M9 f3 i    Object getRear();

    /**
     * 遍历队列的元素
* e, H1 Q0 g; D2 R( L     */
# h4 z. S) c2 C, f. o    void traverse();
: j! }0 R1 w/ h6 t1 @8 g}
2、队列的接口实现
/**
* 队列的接口实现
*
! ^  C. b) d3 `; Q, {/ P * @author zhuhuix
; X3 l) T' ^, M- F& @ * @date 2020-05-01
' ~& S- {+ j, N( u6 {1 I9 H */
public class QueueImpl implements Queue {
% R# l0 F5 Y& |4 o
    protected Object[] element;

6 P$ S3 T) _9 ~    protected int elementCount;

    //队头
    private int front;

    //队尾
    private int rear;
% b: m$ N2 z, b
" @0 _% ?0 v! z7 C3 z  e3 x    private int defaultSize = 16;

    private int maxSize;
9 j& q9 O+ Z$ a# ~; o5 q
1 I3 i: `: l- A9 r3 {' [    QueueImpl() {
        element = new Object[defaultSize];
3 A" f9 B+ ]& f& [: H        maxSize = defaultSize;
        front = 0;
' `8 B! v. B. A4 A, L: ?5 H        rear = -1;
    }

7 r! \6 c# c. G1 X8 I. b! S    QueueImpl(int size) {
        element = new Object[size];
. a5 D3 \9 S+ ^3 d1 z7 _        maxSize = size;
# g4 r, A2 b. A' r0 M4 M" H- s1 K/ ~        front = 0;
# V3 Y4 y9 |. t, E! P+ K  x        rear = -1;
. v1 v% }* E8 o! j5 i" L    }
1 J; C( x. ?9 _
* B2 n0 @7 z+ Y- f% J: {% p    @Override
6 Y7 s- V3 }5 Y9 H    public int getMaxSize() {
- d% p( I. `5 x: U" s0 d        return maxSize;
# r' y: r3 H% N7 D+ E- G    }
) E( }4 K; x! O1 B
    @Override
  H9 [6 K' ^$ C    public void push(Object object) {
# ~0 _& W# ~7 P' C4 m5 z  q0 [        //如果元素个数已经达到数组的最大个数，则进行扩容
+ Q8 j% k( e) [; }% i! y3 c7 Y        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
        element[++rear] = object;
        if (rear == element.length) {
# o7 x& z# s- f* U% S            rear = -1;
        }
        elementCount++;
" u( J4 y. q0 e, ]1 y    }
3 [% G9 J/ g' t; X, `/ F
    @Override
2 ?8 A! V1 {! i  d! T    public Object pull() {
        if (elementCount == 0) {
' }% k7 M. x3 S& G            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
        Object object = element[front];
        element[front] = null;
+ m2 x+ p# T* K" K( N- ~        front++;
        elementCount--;
        //队列清空，队头队尾恢复初始值
+ L" W& X% i; C+ @3 m# h        if (elementCount == 0) {
            front = 0;
6 J* F8 j# j3 L. M  n  z8 ?( Y  v7 ~            rear = -1;
1 K5 j: R2 k' ?  x6 {/ ?        }
. V* D& d+ \  r! o7 C        return object;
    }

3 B+ }$ H* v8 J/ F$ p    @Override
    public int getElementCount() {
        return elementCount;
' F$ O# F. o# T+ S7 W    }

    @Override
0 H& v" R0 @/ H    public Object getFront() {
  A, F: S2 F6 S# s, o        if (elementCount == 0) {
+ |$ V$ L3 C  N- W9 V! n            System.out.print("队头无元素");
            return null;
        }
        return element[front];
    }
7 C3 `8 r' @6 \) _: D- {$ H. W
5 O6 T8 @5 V! z4 W7 ]# E    @Override
    public Object getRear() {
        if (elementCount == 0) {
            System.out.print("队尾无元素");
! v' [- a; D* l6 C5 n8 S            return null;
        }
        return element[rear];
    }

5 l1 A. d! J* ?/ [: r0 v4 e    @Override
    public void traverse() {
# t, D; v! ~- O        if (elementCount == 0) {
9 K+ Z$ s& d7 U- O+ o            return;
        }
3 i1 k1 c4 |( z' ?  Q" G7 C  T        for (int i = front; i <= rear; i++) {
* e6 |. W! r# W6 b. E" x            System.out.print(element + ",");
( E; U( i$ ?0 y$ ~        }
        System.out.println();
- Z; G; b+ n% H2 H. J" {2 c    }
}
) A$ i5 z, d. \, q

3、队列的测试
public class QueueTest {
4 O1 {; J: f* i    public static void main(String[] args) {
# v; i4 e( A9 P8 w        Queue queue = new QueueImpl();
4 r; a8 E. c, N& y/ _, H
        //获取队列大小
! ~0 ]; z4 m- d2 F4 d        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
  c. A$ {5 A! C
  Z7 p" V5 ?5 {5 p. R; n9 R        //第一次入队列:压入1-15
( q( P( L, ?) x( ^4 j' Z3 n  v        for (int i = 0; i < 16; i++) {
6 Y+ a3 E. u0 I" y            queue.push(i);
        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
' H, J  m/ x- \( \% M) K        queue.traverse();
. l  F% N/ T: a2 @# \4 b- u1 n% F        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

        //第一次出队:取出0-15
8 d4 }) s2 X% T& h/ E        for (int i = 0; i < 16; i++) {
! I& g! h- j% |6 d( e% E            queue.pull();
        }
3 T' S, S! t/ X, `+ P! n        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
' N. |6 g  q+ C9 y4 @        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
* d% `. _1 d7 p: k7 a

        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
  S, `+ F  z/ W1 B+ k  s# e, L/ E5 W3 I            queue.push(i);
9 [" N+ a2 v# _7 B" Y2 `' ?        }
7 U( Y/ w3 d, N% ?, G/ M. g6 K        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
1 |4 D6 V- a* h( A# c4 I% c
% u' h0 ?" K) X! q, F
/ i5 ~2 b6 e$ n0 r( c        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
2 B9 F. E* k; Z' F# U+ M& J( V5 s; y        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
) `' D4 J7 ?% y; g$ z  I6 q$ j9 I3 c
        //空队列出队报错
        queue.pull();
- e& I/ w4 l# _
9 j+ g% J, m& L  V; P6 G    }
}


0 r, {. q+ Y: t$ t# c, v+ F* M

1 B/ A4 x4 d% Y2 c8 t2 |8 V

& u5 h% e! J$ r7 J
, m* H* P, Y; q$ x/ a" m. w% N1 c



" ^7 r2 ^# t4 t2 C
, |% q& h9 X6 I) N8 f


' ^. v, j* O3 g# F8 q% ?$ v0 @9 x————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
' A( D( ^4 o! N; d) q

) `+ v3 _: t' m8 u1 K) W

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5