数学建模社区-数学中国

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

---

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

' f' D) k% l6 |8 U数据结构——栈(Stack)与队列(Queue)的手写实例
. |$ ]1 x' Q. S  S4 p# S
( y" u. d& g3 P" O( Z5 i1 g[color=rgba(0, 0, 0, 0.74902)]文章目录

5 O) n  Q: F$ ~
• 一、 栈与队列的定义
• 二、 用数组实现栈
  " @9 A+ i/ \4 {- E/ t9 p, y- @. c
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    8 g6 {- B  {" Q8 {  p& \$ X# q
• 三、 用数组实现队列
  . |3 C: z% K0 e+ h  `' E  T
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

9 b: l8 |+ H1 l8 ]# I, P
一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
3 A- m) L6 W3 _& `5 T+ g& r2 m  [
/ m; O. ~5 O' z( o1 P9 z8 b: K; D　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。



二、 用数组实现栈1、栈的接口定义
/ v* [9 V3 a' ?9 v/**
* 定义栈的接口
, p5 V/ X: r% O, x *
3 g: C3 Q# S5 x& J4 e' k7 z$ M * @Author zhuhuix
+ B- Q( x9 [9 q0 B * @date 2020-05-01
/ ], ]8 O3 F2 l* S */
public interface Stack {
; J' b2 N; o$ a7 @5 \: P% [    /**
6 K4 ?% G5 V) _     * 入栈
) p1 ~1 G6 l! Q$ N$ \; r# i2 o     * @param object 入栈元素
; P7 J0 {/ ]* Y; ]3 n2 W' a- Y     */
, }+ f3 q4 g: a* i% N+ ]1 ^, X* i    void push(Object object);

    /**
; F& |/ T- H2 A) B- h     * 出栈
5 o& G0 }: K# s% g9 ^7 X4 T  H/ T: O     * @return 出栈元素
5 z2 D9 {+ u# r- l' a9 W* W9 h: l     */
' [: |, A7 |. P9 X    Object pop();

0 h+ ?5 A+ b) }5 `) ~% b) l$ c    /**
     *  获取元素个数
$ G0 Q% K, P4 [7 T) F' M/ \     * @return 元素个数
+ ^/ q+ L5 @" B! M     */
) k4 |# \  S0 U. p    int getElementCount();

; A  V/ v, \$ f5 t4 h    /**
     * 遍历栈的元素
     */
7 [& f/ |1 A; p    void traverse();
( x8 r/ k$ d) N+ e6 s
9 C# C5 t: v0 Z. f7 `}
2、栈的接口实现
/**
* 栈的接口实现
( R/ Q: H6 ^% M( f- v% Z/ Y *
* @author zhuhuix
* @date 2020-05-01
*/
public class StackImpl implements Stack {
       
    protected Object[] element;

( a, J0 C/ N4 x0 v2 Y% w  f    protected int elementCount;

3 R5 ]( h( I, ]3 S9 o9 N    private int defaultSize = 16;

    private int maxSize;

    StackImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
    }
" S9 z9 c0 U7 q4 Y, W
    StackImpl(int size) {
        element = new Object[size];
: M* N( v& [- m% C+ C, x) T  c% D        maxSize = size;
    }

1 G: Q4 X1 A9 F; Y# B    @Override
    public void push(Object object) {
$ E2 Y% o( W% r& d3 C  }* i: _        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
; I5 f! j/ I# V  }9 f. F        }
, l( K* [0 ]: K% k. L6 A4 K$ {        element[elementCount++] = object;

    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
' `; p% S# K2 V/ D    public Object pop() {
" a6 I% ]& o, \        if (elementCount == 0) {
3 p1 `. ?4 X: z4 J4 n* U6 ?8 I            throw new ArrayIndexOutOfBoundsException("栈中无元素");
) M. ~; M6 A  L6 d* j1 m        }
        Object object = element[--elementCount];
6 ^. f. Z" c# _6 M1 [0 c        element[elementCount] = null;
        return object;
    }

1 e( Y: f2 M& D    @Override
    public int getElementCount() {
5 N4 n. U, E- F' u' [1 I- p- c        return elementCount;
! r' ]# H4 G, z7 l5 D; W    }
8 D! k1 E: V( m5 B
    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
        }
        System.out.println();
    }
. h( Y& J* ~' h1 i# d9 J; {, y}
6 e- E. f4 h* [2 o8 d3 l% Y6 X: ?3、栈的测试
public class StackTest {
' \, j1 Y9 v3 v    public static void main(String[] args) {
        Stack stack = new StackImpl();
% w. Q% j& ^1 t+ J5 e+ u
+ _9 _( T1 p5 E        //第一次入栈:压入1-15
" O- W- m1 \3 D% z( H        for (int i = 0; i < 16; i++) {
% e2 U: Q; M: Z+ R            stack.push(i);
; m9 x% b. Y& Y' Z' W3 C% ]; }        }
- k9 H* J9 K/ r6 V  t' i+ K: Y: {        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
# W5 O5 Y8 ~2 ^/ o, X+ Z        stack.traverse();

        //第二次入栈:压入16-31
) v* \+ t5 y6 d: s: M1 F        for (int i = 16; i < 32; i++) {
            stack.push(i);
, V$ c# f1 ]  Y  i        }
$ N: u3 s& F  L        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
: X/ V9 I3 F8 T# d8 w9 [1 j        stack.traverse();
( A4 ?! W9 F8 c2 J! A
        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
            stack.pop();
/ o) o. ^3 R1 h) f/ x$ g, t) R        }
. t+ N/ {% t5 \2 z        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
% v" y8 l8 ?+ T* i        stack.traverse();

. f- @/ U7 V( t6 l) f" X; F( e8 A4 l        //第二次出栈:取出15-0
1 M! d& Q* v# d; q* R+ R) C% s        for (int i = 0; i < 16; i++) {
# {! p, b1 K/ N; Z: Z5 v+ D9 Z            stack.pop();
, u: u- P+ i* {2 W) \1 L/ r        }
- y, U* W/ j) G) E; p' b* e        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //栈中无元素，出栈报错
/ a0 c4 V/ @% \% o6 p        stack.pop();

    }
5 e$ j8 t4 F7 X; {6 x3 `}

2 J4 v8 S' y1 \7 q" l! @
; p. T* w7 Y! q& \

7 K, _2 S- y0 U  y2 x三、 用数组实现队列1、队列的接口定义
* \& o2 p  L/ Q5 X/**
8 V, p) i! S1 a  y$ I* E * 定义队列的接口
*
( l$ O; E7 A  H9 O8 \+ } * @author zhuhuix
* @date 2020-05-01
' \2 v* u! v+ ^# B5 W5 P */
public interface Queue {
0 ^$ k( m9 f7 e5 F
& f+ e9 c! F, }2 k, m7 o' H+ j6 X    /**
     * 获取队列大小
     * @return 队列大小
* k& h5 V/ F! U- i0 J% r     */
, \4 T; s0 E% B; [& D    int getMaxSize();

    /**
     * 入队
: I$ f, M4 r. J  S# J     * @param object 入队元素
     */
5 o2 J+ y$ e! a, M$ Y$ v    void push(Object object);

    /**
' v( k) S6 ]/ m) q* p+ s% y- W# F     * 出队
4 M, v$ O' h7 K/ q' q     * @return 出栈元素
     */
1 n( s' _$ [9 \) T5 s    Object pull();
2 [  B. N0 b& E$ e
    /**
7 i1 J" ]; c1 L$ h* ~, ]. q$ \( B     *  获取元素个数
     * @return 元素个数
, F. w/ P/ l& \4 e  S9 Z     */
0 s  R3 z  D. N) C" @" W    int getElementCount();

    /**
" ~! ]  x( x) }% V5 T) ~  c! S% J     *  获取队头元素
     * @return 队头元素
     */
% z! k  v) |- z* U/ g/ d    Object getFront();
6 n$ _& u, g# E# a4 v* P0 y: h
    /**
: @( N+ ]! N0 u+ o% e, T     *  获取队尾元素
1 c+ X* O, x7 M( o' {* h7 [     * @return 队尾元素
* w+ W( b+ _. L  h7 |     */
    Object getRear();
7 `) v, e7 t! n
0 w8 t- T7 Q# r    /**
0 {- k8 N! j9 F! L     * 遍历队列的元素
  q$ \% p5 O: H5 d" p     */
5 L* X' o. J5 p' E    void traverse();
}
/ t3 c; i* U; v2、队列的接口实现
' w- K% ~8 \1 I/**
( g" a2 w/ G" o; s  x% j * 队列的接口实现
8 R) X0 D0 ]* y *
* @author zhuhuix
' `7 C* o7 ^9 V" g. A- b& V, `0 x * @date 2020-05-01
*/
) Z* {. E5 Q2 @8 vpublic class QueueImpl implements Queue {
  o0 @7 g7 m$ |, c9 K! V0 z! s+ ]; n
    protected Object[] element;

# K$ ]* b* R* s) \    protected int elementCount;

: [6 i) G+ e# I1 N- g+ e    //队头
    private int front;
' d9 e) ~7 ]  Q: n. S
    //队尾
    private int rear;
$ F  d) ~9 C9 Z' a; r8 q
    private int defaultSize = 16;
9 ]' `. l! F# e' u
    private int maxSize;
( K4 ~/ b& W  s& w' x2 T
  [  L9 q( k( F    QueueImpl() {
8 ~, u/ P* _, j7 L: ~% a" H        element = new Object[defaultSize];
( X# w5 E$ L7 u, b9 v        maxSize = defaultSize;
        front = 0;
        rear = -1;
    }
9 @* i+ A5 ^/ H5 w/ q
1 o, Q8 h. L% _5 p    QueueImpl(int size) {
        element = new Object[size];
. @& V9 C/ P, C6 w        maxSize = size;
        front = 0;
        rear = -1;
/ d6 j2 |: O, [    }

    @Override
    public int getMaxSize() {
        return maxSize;
    }

. Z$ U8 \: f% d5 @    @Override
    public void push(Object object) {
  @' i3 Y7 }  c+ @3 m5 Y/ L        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
/ p4 [% s! [9 D# e! ]: `        element[++rear] = object;
        if (rear == element.length) {
1 C" V( s; a' v- j+ L; J            rear = -1;
4 s: |2 P8 a; B. @9 j" N        }
        elementCount++;
6 q& X* g  y; c6 k) l    }

    @Override
; @4 ?6 E8 q) }) Y8 v: n$ U0 k    public Object pull() {
! k* t8 s1 ^& N        if (elementCount == 0) {
8 E7 A% N9 r" g- ]" H. v            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
        Object object = element[front];
        element[front] = null;
; e8 {9 Z; t3 S1 p: ?1 z* v        front++;
        elementCount--;
        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
$ o4 x; s: a7 V& m4 K# T2 ^            front = 0;
            rear = -1;
        }
+ Q/ [+ M' D0 x( ~1 S# O3 I        return object;
    }

    @Override
    public int getElementCount() {
0 K) x( b5 {4 t1 R8 g  u        return elementCount;
; P9 W5 Y. k( c3 [# O+ ]    }
. Z8 p; E' V* V/ C' T4 i
8 m2 x+ Q  C) e9 `2 k7 Z0 b    @Override
    public Object getFront() {
        if (elementCount == 0) {
            System.out.print("队头无元素");
8 @0 Y5 Q4 B9 G2 c/ y            return null;
: \6 f' a2 h5 c4 Z  P0 Z        }
; @+ L: }% I0 @' |        return element[front];
    }

    @Override
    public Object getRear() {
# z) C: J: H$ c7 h" C! [  K        if (elementCount == 0) {
            System.out.print("队尾无元素");
0 D4 P: D7 I8 ~. f0 x            return null;
) p$ o$ Z1 h) a& O6 g9 @        }
        return element[rear];
, P, I0 t% a1 o    }
  D: x' c) F" U! m
    @Override
    public void traverse() {
        if (elementCount == 0) {
/ L$ H- r; _. j( Y$ @1 b9 t            return;
        }
& O6 X: u6 A5 V0 d5 K! w        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
        }
8 W' ]$ p( a# _2 M3 H        System.out.println();
9 O; z2 Q) X( U, ~1 l    }
% P1 ^+ P. T% x" R% k3 n! U8 ~. ?}


3、队列的测试
public class QueueTest {
    public static void main(String[] args) {
2 s6 |& X; C. _: h% n3 `        Queue queue = new QueueImpl();

) [! O! \' k' K2 ?; |$ M' @# r        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

* O; O7 V0 h  s$ ]: U. a        //第一次入队列:压入1-15
) h& m- {- ^; V6 \        for (int i = 0; i < 16; i++) {
: F; f/ r0 ~7 G% y            queue.push(i);
& [1 p& N7 x' t7 O% b- E9 J        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
8 P* ]$ d# q+ S; w5 C* ~8 k        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
8 D4 n. T6 \1 C9 g, ?
        //第一次出队:取出0-15
' R5 [" N; [  H3 r        for (int i = 0; i < 16; i++) {
$ i4 Y2 s8 E( o7 Q6 [, L8 {7 o            queue.pull();
4 a4 v+ z- A6 C! O        }
2 \3 M% ?7 @' I4 P! E" ]$ q        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
& j2 _8 D# E7 u

) o/ M; p( `8 ~  e4 x* ~' s* R        //第二次入队列:压入16，31
; |. w* X4 L+ z* S/ k: o. Q        for (int i = 16; i < 32; i++) {
            queue.push(i);
1 P/ w0 }; w4 s' g5 K        }
  i, l# Z. i6 K        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
& J8 }& i- l6 s3 T        queue.traverse();

- p6 U& {6 @; I8 y! N2 d& W3 r9 |
        //第二次出队:取出16-31
! u9 I# |3 }. W$ O7 Q        for (int i = 0; i < 16; i++) {
- Q2 _& ~& [0 z& j            queue.pull();
        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
5 U/ ?3 _# i4 w) e4 S        queue.traverse();
; \7 C/ n" U6 B5 N$ J9 y+ J/ l
        //空队列出队报错
2 J3 O5 q' ?& ^- ]3 V        queue.pull();

2 C! U4 L( x* {2 w# ~  e0 l    }
}






" k. j7 t1 |; ]9 o. i4 `


% H$ x' p, J0 E$ L% A
- ]/ p7 G1 f( P& ]+ s



- l* q1 R" `# o% d) D9 U
————————————————
: F6 R% X# _) f; o# v版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
  g, x6 o+ u& C) ]0 s/ n& H6 {) x
; H- \5 S+ L5 J  }& `" t) o
" {$ N) m2 m; k

---

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

Powered by Discuz! X2.5