数学建模社区-数学中国

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

---

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

& g  K4 {# I! F9 v8 N数据结构——栈(Stack)与队列(Queue)的手写实例
# _3 U4 a- C7 J0 |0 J
[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
      V) u1 P! {8 d' c7 s
• 三、 用数组实现队列
  4 g& E4 P& `: @
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。

　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。



/ v& A# H# m* i" L. W  p' q二、 用数组实现栈1、栈的接口定义
5 ?' I2 n8 R8 ^, y/**
* 定义栈的接口
% \9 U, \" u/ w  k- Y" H *
1 O1 [5 t, _5 C2 r * @Author zhuhuix
* @date 2020-05-01
$ ]- ]& U/ O9 e; r: ^ */
( }" E. K/ a4 w9 \% E) ]3 u& cpublic interface Stack {
6 s5 v9 e8 T5 Y    /**
     * 入栈
: ^# |( V) j, A# P+ q     * @param object 入栈元素
     */
    void push(Object object);

! _) f3 Z5 ?8 N3 X8 {    /**
; y$ W" {2 @  J5 z) P  M1 c     * 出栈
     * @return 出栈元素
; C7 U: }6 o4 Q; x     */
    Object pop();
  g5 J( j9 o& D  {8 H
    /**
8 P. ^+ [% Y6 Y     *  获取元素个数
     * @return 元素个数
7 T- a6 N$ h! R6 M0 Z" L# ^     */
0 r6 R- U6 `% [% A    int getElementCount();
; m) ^2 |9 \* l" p) C
    /**
     * 遍历栈的元素
     */
8 }9 B7 F( B- Z6 E. n    void traverse();
$ y$ q) F9 v# g+ `! k" k
! P6 k( Z; u# d. ~) S' M}
2、栈的接口实现
% m) l" x; R' W5 H! E( i: r: T/**
* 栈的接口实现
*
* @author zhuhuix
4 @9 c1 B$ i( C: k * @date 2020-05-01
*/
public class StackImpl implements Stack {
: M' g2 M3 T4 e$ d) B) g! X       
8 `7 y- r* Z" y: g    protected Object[] element;

. B1 i3 D: Q; X+ W' I    protected int elementCount;
0 w# y  s( X" E( w1 K2 _6 g% e7 W
    private int defaultSize = 16;

) R! z. v! K+ Y( x3 G    private int maxSize;

    StackImpl() {
2 Q: b0 B* L) o* i! G" D        element = new Object[defaultSize];
        maxSize = defaultSize;
1 z7 n. W7 W& s7 l8 n& D7 M    }

    StackImpl(int size) {
" l1 Y/ _0 m5 }) F1 p: ~4 C5 H        element = new Object[size];
        maxSize = size;
$ R# z: \( }8 f; \1 d8 R& x# c    }

    @Override
6 Z5 z4 T- @. @! t4 U; K    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
/ t4 }' v. q9 D* I0 S        }
        element[elementCount++] = object;
# g5 P' d: y' e/ L7 p8 }
    }
2 |2 k* u" R+ C, i8 P+ T. Z  R$ @        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
+ G& M5 N1 V) r3 l# [    public Object pop() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
4 d: l( ?/ k1 N' u        Object object = element[--elementCount];
        element[elementCount] = null;
        return object;
/ {& F# H/ [; Q. X    }

/ D3 A) A+ K1 I- w  }! o0 O    @Override
    public int getElementCount() {
        return elementCount;
; v" k  x) r$ N5 [9 r) t    }

) W' D; Y2 ^$ e6 o    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
        }
        System.out.println();
- F5 X$ Z- U; S0 g    }
}
4 [& o; L$ [. Y$ N' u3、栈的测试
, C) v6 h# C, U6 ~" u5 j& m+ Z* ppublic class StackTest {
! A4 r% m% j3 V3 I2 D* Q    public static void main(String[] args) {
- B0 q4 A4 h- F- ?5 T- g        Stack stack = new StackImpl();
' r4 _; |! e2 d: h
- e6 q2 s0 _* B- L& p1 r: m        //第一次入栈:压入1-15
3 O) R5 X" G0 y        for (int i = 0; i < 16; i++) {
            stack.push(i);
        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
: N" u: e! ^: K, Z  z: D* f        stack.traverse();
/ }! e* H: U0 t2 `- ]. W
        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
            stack.push(i);
        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
- G. }; h6 b( ]- C        stack.traverse();

! O0 W8 k0 I7 E' C' A4 G        //第一次出栈:取出31-16
* Z/ w2 j% [9 z2 E8 _        for (int i = 0; i < 16; i++) {
            stack.pop();
# p) a: b' d( E1 A; v" O        }
+ [- M$ ]# Z- H; W" G, Q' q$ b: q& c        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
% S% T( F# v3 n, {+ l# o% _) F6 a        stack.traverse();

' {. `1 f( M! Q# a6 ?6 Z        //第二次出栈:取出15-0
( S0 M8 d9 s$ g1 z! Z7 R' W/ Y        for (int i = 0; i < 16; i++) {
8 u5 |* D/ b, w            stack.pop();
        }
+ E' Z( j  e% ]0 J        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
9 l' e6 @( T/ u! h        stack.traverse();
; m4 y7 l5 F8 ^" B" S3 E, e
        //栈中无元素，出栈报错
        stack.pop();

2 S2 q8 H- r) s  C7 Q) E    }
}
$ z$ Y' X; Q3 F5 q* ]! Y$ H: Z  J' W
& A. u' k7 z% O$ A- I1 Q

+ o# N. o. F3 c$ M. b
三、 用数组实现队列1、队列的接口定义
/**
. @0 _' ?0 r2 k, P * 定义队列的接口
*
: S" ]  z5 r9 \! z4 H  H: T * @author zhuhuix
* @date 2020-05-01
*/
3 X6 i1 n6 D( wpublic interface Queue {
4 }, ]/ b7 K' U+ s- A
+ S  p3 y3 a  _: R6 ~/ Y$ q    /**
     * 获取队列大小
     * @return 队列大小
+ I& f* _8 [  S) \5 s) T     */
1 u' f2 k# ~. y9 J    int getMaxSize();

    /**
! A5 O: H  J' V* }+ d7 r, H! {  T4 q     * 入队
* Z3 T: g$ I6 x0 u6 p6 V) R     * @param object 入队元素
6 `" d2 r2 N6 S* ]& X" l     */
    void push(Object object);

: b$ `! [; v; j# k  i( z. |    /**
     * 出队
     * @return 出栈元素
     */
    Object pull();
+ b7 N  }! p' ?
    /**
/ {6 d+ k0 Z3 A0 i     *  获取元素个数
# M, A' T  T7 g3 K, H! ~, N     * @return 元素个数
9 N) @1 N8 K! x0 l; u$ ?     */
    int getElementCount();
, }' c7 g$ a3 F$ j5 a( H
    /**
     *  获取队头元素
     * @return 队头元素
, R9 J% o" I! j# k, T+ V/ u     */
    Object getFront();
+ {7 u: O4 O5 B  }, N( \6 ^
3 h3 d) }3 L6 t1 G7 R* m5 K    /**
7 O9 {. F' y/ [, u9 t. l     *  获取队尾元素
% K9 L) ~1 @& Q. X     * @return 队尾元素
7 x2 t4 ~) v7 R& K4 y) E( y     */
9 u$ q) E  J0 t( {% K    Object getRear();
! W; X! {2 v8 O3 \* {3 Z
" i7 k8 h/ t$ R! B2 i- D* x    /**
     * 遍历队列的元素
     */
    void traverse();
8 ]- [$ S2 x7 L  t- b/ m$ ^}
2、队列的接口实现
/**
* 队列的接口实现
; a2 J: C2 c. ^  | *
* @author zhuhuix
) W5 e8 h$ S. X * @date 2020-05-01
9 c) ^2 h" t6 T0 } */
public class QueueImpl implements Queue {
% E8 i; |% t% y9 X: r
4 {8 ~7 f; c' `3 a    protected Object[] element;

: P# ]2 ?8 _, p" s/ h1 r/ z% f    protected int elementCount;

    //队头
    private int front;
8 ~& g( g' C) [3 O8 E
    //队尾
3 i% L' y2 c% D/ X- w    private int rear;

: l* x/ S8 P2 G9 o6 x; P    private int defaultSize = 16;

    private int maxSize;
1 E3 v8 u, X. {6 o: X0 V" C
    QueueImpl() {
+ i$ a) s! L3 r        element = new Object[defaultSize];
+ Q. A) B4 d: v4 O: J        maxSize = defaultSize;
        front = 0;
6 X6 q1 g  l2 a1 B        rear = -1;
# ^5 N7 }" X8 _( ?/ B0 n' q    }
2 q+ |" U1 l8 {% T4 `- U' _
    QueueImpl(int size) {
, d2 c$ k- k- M4 s& d; @9 |2 s        element = new Object[size];
: c  E+ n7 X2 s! @2 C" Z, R5 W9 R6 S        maxSize = size;
        front = 0;
        rear = -1;
; u3 X% @7 Z, `' o$ B    }
8 `  g1 k0 v/ }. y+ f* Z
* |; }. B5 M0 o& Q+ I: K    @Override
% q3 ~6 y8 j# s3 \4 t) y$ L    public int getMaxSize() {
        return maxSize;
0 {4 P* Q) [0 a  f: z  j$ Z& D    }
: I0 Y% Q( V$ W( G
0 P" w: t) p4 ]0 t/ J    @Override
    public void push(Object object) {
' h$ B* T; Z& ?& \* e3 t0 U        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
8 n6 T1 X5 u/ {5 j- d$ W3 j            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
        element[++rear] = object;
        if (rear == element.length) {
            rear = -1;
        }
) V- @/ w, m2 a- Z8 o- a% Y5 k        elementCount++;
+ K( v0 }& B# ^$ S    }

    @Override
$ U1 D& m7 A' g& T1 f, C    public Object pull() {
        if (elementCount == 0) {
. z5 A+ k" ?6 O- C            throw new ArrayIndexOutOfBoundsException("队列中无元素");
4 K  `; o$ q, h        }
& K7 h7 R' Z; b3 Z- O        Object object = element[front];
$ M- P6 u6 A: U& d3 v3 y        element[front] = null;
        front++;
9 v5 @5 Q( W" y- ~0 E. M        elementCount--;
        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
            front = 0;
            rear = -1;
: `' m5 Z- u1 }& N. T0 s2 v        }
        return object;
    }

  D' }8 v9 g6 |6 y2 i  I* `    @Override
* w# V! q6 ~8 f& P# p4 O    public int getElementCount() {
        return elementCount;
) Z3 J# R) v2 g) s: Z    }

    @Override
" b8 y- ^2 |: f+ d. v    public Object getFront() {
        if (elementCount == 0) {
            System.out.print("队头无元素");
            return null;
        }
        return element[front];
    }

    @Override
; U) E5 k/ B- ^, I    public Object getRear() {
. |4 ~+ P# p' w* T, j1 |4 R: v        if (elementCount == 0) {
. c" ?; O! ?6 V5 {            System.out.print("队尾无元素");
* _4 q# ~& R( F- i            return null;
8 O% H7 i, x8 b  K" n8 k) ^        }
: f/ K# [& m& y        return element[rear];
    }

, q" w' ~" T9 E    @Override
    public void traverse() {
        if (elementCount == 0) {
            return;
        }
        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
; z0 Q) q/ t5 V; `, j        }
        System.out.println();
    }
3 a$ o7 ?. D9 i6 I}
  D" y8 Q9 b% ]* x  w

3、队列的测试
* Z: ~) U+ O: c9 u8 A1 G" Upublic class QueueTest {
( h7 C; A7 i9 u2 p0 {    public static void main(String[] args) {
        Queue queue = new QueueImpl();

2 i+ N# K# @5 T, Z        //获取队列大小
1 O; ~5 r- H2 r, U' |7 t        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
            queue.push(i);
9 i3 \! ~5 _& u; W& F        }
        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();
6 L% i9 f- ?+ M  ]! j+ `) D7 @& G) C        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
# i+ f- a* s! r! u        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

: l/ W& W$ y" d1 p2 `4 x3 g
        //第二次入队列:压入16，31
) C% X7 A" O* Z$ x3 X2 W) ^. j' e; ]        for (int i = 16; i < 32; i++) {
            queue.push(i);
' c' K/ _3 ?" m- o, D$ f        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
* A/ J9 h+ p& C1 P

( P! [  B; I' _6 ~        //第二次出队:取出16-31
+ ]  W% I# S3 y7 Q2 s, N        for (int i = 0; i < 16; i++) {
4 [8 R) C: Q+ s  v            queue.pull();
        }
: B! i! x7 y9 y* R  z& C! ~, h5 ^        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();

* y5 O* M7 N/ a1 u- `9 L        //空队列出队报错
. B5 @. T* o: _* m3 w9 s        queue.pull();
* {: \; V- Z6 Q3 I7 N5 N
8 i4 r: [1 g6 r    }
: U1 e" o" Z! u  M, o6 O8 I$ N}

4 U9 Y% ~' Q9 g: M. g
" C/ f# R! N* e1 L



/ K1 E+ B) f- d$ {
0 I$ |' f% r4 S/ L2 d


8 d  l: y. g, E& J; Z$ {4 S

% N2 K) V# P& v2 l. H
( i- }+ D+ ]& Z% y8 l# Q  f

————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
7 J, ?" [' L. i7 e+ L! e- ?

9 F% W$ g! w! b' L  O

---

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

Powered by Discuz! X2.5