数学建模社区-数学中国

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

---

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

" N# @8 O4 i8 g* Z/ J数据结构——栈(Stack)与队列(Queue)的手写实例

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

# A: n9 @! R# y& f9 e
• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    2 r7 S  f6 o- }, k6 }8 d
• 三、 用数组实现队列
  , O4 O$ C( _6 ~, |( K
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    # z1 r' h7 @* X. {% J+ W$ ~

# f. m# E8 T! F! r; S一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
) H% ?/ ~/ E7 Y7 I3 x  S
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
' E! ^- Z. h* d


) n: O- b  \, @2 Q二、 用数组实现栈1、栈的接口定义
! v0 A5 M* ?+ E/ J/**
* 定义栈的接口
+ w2 ~! N# k+ q) G *
" y2 X4 E: v( j' |8 A * @Author zhuhuix
  p/ a, }  k& k+ R4 m * @date 2020-05-01
! M6 x; |' }+ S8 \4 W* e */
public interface Stack {
% H5 C/ E* ?2 B- E+ M6 f) m% Q    /**
     * 入栈
2 e. G+ b3 x1 J+ m5 \- y: z     * @param object 入栈元素
, D0 W0 f; p! R     */
) Z( _6 ^6 @! v7 C3 s& B0 ?    void push(Object object);
. N( Y+ Z6 a! F, z/ b7 y$ a; k
, {. G( W5 G% D( m! |5 \9 ^    /**
     * 出栈
     * @return 出栈元素
4 c, f3 z$ {( L. r5 |: ^# H5 w     */
    Object pop();

( T, z* d' @! s" i2 G2 N( n    /**
# Q: d9 L% `0 F     *  获取元素个数
/ {* p; V- d3 t# e     * @return 元素个数
     */
    int getElementCount();

    /**
9 \; p2 j0 y/ X/ }4 D. w     * 遍历栈的元素
) A) l% Y9 T0 _+ [9 R2 G     */
    void traverse();
1 k4 K$ X' k) ?- T
}
; F- w3 o$ x* G3 \. c8 l4 N/ M2、栈的接口实现
/**
. q6 d  p0 C" y * 栈的接口实现
*
' M$ I# f& Y# N; _ * @author zhuhuix
* @date 2020-05-01
) `7 {' v+ m% ~. B% ` */
public class StackImpl implements Stack {
5 i1 L' J" h$ E       
4 O: n1 {1 g% m    protected Object[] element;
* K9 C' L) _0 {/ f3 W
    protected int elementCount;
0 n, r/ i! F: N
& \% X# ?4 L  G5 [    private int defaultSize = 16;
  o1 I; V* Q; b; D* R+ k
    private int maxSize;

3 e9 q% j: l! P+ [) y7 i* F% Q    StackImpl() {
9 M6 s5 z  l  J7 f3 m# D# \        element = new Object[defaultSize];
" C6 e1 F* A; n; Z& {  o2 g        maxSize = defaultSize;
    }

( z" m- j- w% d    StackImpl(int size) {
8 {: X, p9 S8 o4 Y& W/ M$ J        element = new Object[size];
        maxSize = size;
6 Q- ~7 J- }3 K. t: {+ ]5 p' c    }
6 G* s( Q3 o; c0 b' u
0 l) [* J5 z5 `& l    @Override
    public void push(Object object) {
8 H" V- Z$ M2 @+ F        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
7 u- }  F6 Q% l$ a* K; Y        }
        element[elementCount++] = object;
2 t+ e! B7 h# D  X. k' V
; V) S: `! Q9 \, l2 x    }
' r5 I+ Q1 ~8 w; S        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
4 F+ }/ X9 k. M( r0 ]' _. j    public Object pop() {
% }+ Z% z1 |- Y        if (elementCount == 0) {
' j6 t' b# S$ Z8 }7 u6 ], b9 n  x6 d( o            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
& h' b, H4 L" y0 U4 S9 p4 y        Object object = element[--elementCount];
& |" Y4 b4 s% b7 H+ A        element[elementCount] = null;
        return object;
2 }$ O  v5 P' @$ z# i- B    }
) C. i. u' B" K9 Q8 J& t
    @Override
    public int getElementCount() {
( H; X) _6 R  o: V& l        return elementCount;
    }

. V6 ^0 ]- D/ E7 z    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
! O# m, ^  C3 A        }
5 l# |# C8 @7 z  @. t# n5 B        System.out.println();
    }
}
3、栈的测试
! o1 {# }# K- \3 F+ vpublic class StackTest {
3 _7 w# \/ |' O3 u0 c    public static void main(String[] args) {
; X0 }# A5 w2 x; w7 r9 |! `        Stack stack = new StackImpl();

. {0 R+ I& m: P- ~0 Q        //第一次入栈:压入1-15
        for (int i = 0; i < 16; i++) {
5 L( Z/ t: V1 U0 o# m$ N            stack.push(i);
        }
2 G# K2 A0 n( S        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();

        //第二次入栈:压入16-31
3 q5 t+ @" _; b: L) I1 s  Y% Z        for (int i = 16; i < 32; i++) {
            stack.push(i);
+ Q7 l" E" j) B9 d6 K        }
( L5 h& g0 A3 {        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
$ a  `& O$ U/ F( w# \0 Y        stack.traverse();
4 H6 x# ~- [; |: {- Y% O
, p6 i6 }8 f4 q* `' x        //第一次出栈:取出31-16
9 J( Z% B7 l5 U2 I        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

. E) |" {6 f6 }3 b        //栈中无元素，出栈报错
        stack.pop();
. J' E8 e2 ?! V3 n
* X9 I- Q( A3 m    }
}

/ C2 @( }5 v  \! g( V
0 `% ]2 W2 i. T
; h7 E- k7 Y) E" x. @5 x, g1 N
; B. }; z5 k7 B8 ~8 x& ~* x0 f三、 用数组实现队列1、队列的接口定义
- i' W+ r; I& g/**
* 定义队列的接口
*
- v7 @5 ^) h( P* G * @author zhuhuix
: s! T% C$ M3 L4 e! m" r * @date 2020-05-01
4 c% u" l& G! ?( r0 c */
public interface Queue {
8 y7 ]" Y4 {9 H# R* P" [3 V& S8 W
    /**
6 P" P& M* @) w4 _     * 获取队列大小
     * @return 队列大小
2 k1 @5 I8 t  n4 {4 r     */
* C8 t2 {3 X  B# Q- u3 Z    int getMaxSize();

  ~4 I* Z8 a' h+ G; Z% w    /**
     * 入队
     * @param object 入队元素
' r9 {' X+ Z) B8 m2 ?. ~7 @$ f     */
9 ~$ {8 p' M; q# N( {0 i    void push(Object object);

3 l+ e1 o5 l0 }6 e    /**
. b* K9 @1 y+ B     * 出队
1 W% k6 C# N+ U0 O) X     * @return 出栈元素
5 j2 G+ F) j% p* u$ q     */
    Object pull();

    /**
  k7 u- W% @9 {; J; U5 Y5 c     *  获取元素个数
     * @return 元素个数
     */
" W( ^" k9 U: F# p    int getElementCount();

    /**
     *  获取队头元素
     * @return 队头元素
# F: F: |& Z4 k" L  T( z( ^     */
    Object getFront();

& h  P. }* [" D* U" S    /**
     *  获取队尾元素
     * @return 队尾元素
     */
% D# J6 \$ h5 b! t9 n" U7 s    Object getRear();

$ k4 d/ ]5 i2 C    /**
     * 遍历队列的元素
     */
    void traverse();
}
/ o/ {# i& ?8 \- t1 Y2、队列的接口实现
/**
, G. J, s) |; k. W- Q" m * 队列的接口实现
  y2 a4 |3 j; d; z5 G( z/ S *
* @author zhuhuix
5 D5 P! y% Q7 D9 E6 t0 U * @date 2020-05-01
*/
public class QueueImpl implements Queue {
# H9 K$ r" R* h% P" r
5 @( z% F/ H( G& q  o$ i; Q9 e) L    protected Object[] element;
+ e  o; H9 j+ Z# F  b$ K
    protected int elementCount;

    //队头
    private int front;
% J. V$ F& G# ?# F0 V( q
    //队尾
$ @+ k+ e" Q: }; o: r9 o  v. t    private int rear;
# K; ]: y- G1 u) L/ |. H3 Q
/ O1 O: E) q4 I  ~    private int defaultSize = 16;

8 V- m- \. O+ n: y. c8 |( F! p" G    private int maxSize;
2 A  e2 }6 K- R* @9 N
    QueueImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
: c/ c0 x$ }$ ?% C        front = 0;
        rear = -1;
    }
9 A) O. r, J9 @' j3 g% E6 [2 h
    QueueImpl(int size) {
        element = new Object[size];
$ |1 |2 b' ~: Z3 j        maxSize = size;
/ A/ d1 F) a# M$ ?) \8 {8 d7 K1 a        front = 0;
        rear = -1;
* Z/ h! V$ C& T    }

9 u8 i* e1 i# ]    @Override
  V- p6 Q7 K: a; N* I: Z    public int getMaxSize() {
        return maxSize;
) g0 u7 v  u  d+ l6 N, w" N/ m+ C' B    }

4 l# J+ t5 e& F) z$ g; f" J    @Override
- f. a# F9 O' p6 I9 r: ?    public void push(Object object) {
" B: F, S0 b0 E        //如果元素个数已经达到数组的最大个数，则进行扩容
% N8 ^9 b/ \* L: x        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
" ]% z4 u" @! {9 I        }
' p6 I  S- l2 ?3 `+ i8 W( e" y        element[++rear] = object;
        if (rear == element.length) {
! E. n3 Q$ O( B; l* w2 ^$ e            rear = -1;
        }
        elementCount++;
/ \5 c1 w$ C! \" \- ?& b    }

    @Override
    public Object pull() {
        if (elementCount == 0) {
/ @" n& y) m8 `1 u' V, h8 }. B+ \( w            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
! A5 E9 U% }% e' f* m& K        Object object = element[front];
        element[front] = null;
        front++;
        elementCount--;
        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
9 A: o! z0 h  c' w% w            front = 0;
            rear = -1;
        }
; _; u6 D2 z8 |" ?" h% P, f        return object;
    }

6 \7 o! Y3 S& x7 y% ]0 |% B' a: a0 S    @Override
4 O' t1 j; u8 w( _5 D    public int getElementCount() {
. O$ J% H/ U) i8 m; K" {        return elementCount;
    }
3 {5 l# f9 x! X: U' i) ~
% o6 O9 c; J, j- L2 y7 t    @Override
    public Object getFront() {
% M) H/ @9 T& F- Z3 Z* v        if (elementCount == 0) {
            System.out.print("队头无元素");
4 w1 \7 y7 B! k1 R- v5 \            return null;
' I; N8 h' x* N% r        }
        return element[front];
    }

    @Override
9 t7 _" @" u* I    public Object getRear() {
9 ~1 l9 k$ Q' ]4 e1 |. U" }& o        if (elementCount == 0) {
- y$ a9 [% `' J4 `  t            System.out.print("队尾无元素");
- }- t+ l! s5 g$ K+ N! C            return null;
: }+ ?1 S5 T5 l. l: [        }
        return element[rear];
    }
( D9 A: r9 ]: D3 `1 ^# M0 P  E
    @Override
    public void traverse() {
        if (elementCount == 0) {
( K3 ^+ M8 Y" ~& A* b# J' {            return;
: y* f% k% ^$ @7 ^" L9 p. I7 d        }
: A& ^5 {1 M* C% |        for (int i = front; i <= rear; i++) {
! o; y0 D. X) M; \5 J/ O, m            System.out.print(element + ",");
        }
4 I* w' a5 N( ~( h7 a! P9 B        System.out.println();
5 P) i. ^4 ^& O2 g( Y' ?* m    }
}

) _# Z7 t, u+ B1 E1 s4 L$ F6 p
3、队列的测试
5 w2 k0 l4 j5 V; rpublic class QueueTest {
" Q8 Y7 h, i+ M  G- z; B    public static void main(String[] args) {
        Queue queue = new QueueImpl();
* K  s  e( h! C9 D
' q. V  ?- ~; U6 ^        //获取队列大小
4 Z8 o% q4 f6 v. _0 W        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
7 P& c/ K( k% T" T! L: p4 i3 X            queue.push(i);
        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
7 Z  x! l" `, g3 i        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
1 S6 {: \( r4 o" a! L3 c& C9 F
        //第一次出队:取出0-15
& y' W4 x6 U3 `3 n. n        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
4 @7 _$ f8 `% q% d7 Y5 p/ e        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
! W6 U: d( ]) d
+ o8 l5 k% q7 d/ v
        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
) h4 z' I% u7 X9 g7 n8 `3 W            queue.push(i);
        }
+ W9 k1 Y; m$ _8 J( K) m9 ^) ]        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();

! L& A  `! \8 l5 k" {# r
        //第二次出队:取出16-31
' ]/ ]' Z0 p" ~" {6 ?6 z        for (int i = 0; i < 16; i++) {
            queue.pull();
! F9 j+ Q4 t6 I% C, a9 n        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();

        //空队列出队报错
        queue.pull();

, b! u9 f% l4 u& B  r    }
# @) O- R& i4 M* B}
# S  \4 n0 Z  ~; b7 n
  o2 ^! ]6 ?: R0 ?. l' q

) t0 j+ h- E3 X
( e/ u! O. f! V' P
2 Q1 o4 Y5 z& H



8 ?  P+ L9 V. G; Z! F+ A
) M- O: x( A* }9 B, l/ G

7 R3 H  c# Z6 N8 [9 c8 I1 g% H
8 Y6 ]& N+ `5 z0 ^) m

: P; i8 z/ f/ [————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
  g/ l4 C$ k2 ?; t
1 U' y; [; u* D9 J4 b0 W. n+ U

---

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

Powered by Discuz! X2.5