数学建模社区-数学中国

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

---

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

6 ]% g0 r1 b$ W* v- b数据结构——栈(Stack)与队列(Queue)的手写实例
* V$ c5 V) M" O& |$ y1 M
[color=rgba(0, 0, 0, 0.74902)]文章目录

' o  o; |# y( T/ l. [6 V
• 一、 栈与队列的定义
• 二、 用数组实现栈
  $ P1 U6 X- V- X2 e- z5 O6 {3 Q
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  ' G5 ]: E: q5 i$ v
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    4 v( J& }& U5 C1 r. g

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

4 Y) _6 x7 t- l2 ]7 y　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
. k0 m( H  E+ u9 R2 x

; b# R- a4 n3 h( i
& @! B  Q5 w/ r% q. q) r: A二、 用数组实现栈1、栈的接口定义
/ d; M2 ~- ?0 t! h% u2 r/**
. U+ N$ V' Q" U7 } * 定义栈的接口
*
* @Author zhuhuix
* @date 2020-05-01
*/
- e8 j- i; u; L% I; lpublic interface Stack {
  ^) ^( w' `* z0 _" r7 Y    /**
2 W9 Y  H4 e, j( c8 }. `8 v6 n     * 入栈
, ]+ D/ S+ J: U' `" U( r     * @param object 入栈元素
: j1 h( s7 k/ ]  _0 v, I! i: Z     */
' E/ w! E/ h6 o( E+ h& a    void push(Object object);
8 Y; ~) d: r2 n2 s1 u
    /**
     * 出栈
/ X9 @. J/ q. n# y" \" D/ @& e! ~7 i     * @return 出栈元素
, N  t/ l$ ~* a4 X1 [$ L: n     */
5 ]4 h8 _! F1 I" H    Object pop();

    /**
     *  获取元素个数
     * @return 元素个数
     */
$ q' v. G( y4 t4 x    int getElementCount();

6 G7 J3 A4 r6 j4 R    /**
; v- S3 z4 y, w     * 遍历栈的元素
     */
2 W& ]2 g% |  D) u    void traverse();
. W: m/ H. K. ?# p& U6 X5 |5 a
  q, m& J0 S  E; x  Y+ A  S" S$ `}
" |' L" K1 C- e1 B# D* R2、栈的接口实现
/**
0 c9 P% X$ y# u, F' D6 {" _# q7 K * 栈的接口实现
*
* @author zhuhuix
* ~( H! ]. q/ q% r. H, s7 S/ P * @date 2020-05-01
*/
public class StackImpl implements Stack {
       
    protected Object[] element;
& `3 l5 z" ^, d9 X0 A: n) V0 r' ]: m  y
    protected int elementCount;
! Y2 A/ Z  Z4 t) p3 r$ a, e
    private int defaultSize = 16;
$ {+ F5 Z0 F  w
* c- T! K7 J, u0 U5 g5 [& K    private int maxSize;
2 b6 \2 x& Y) G1 m
% S4 f+ E% L  Y9 `# @8 s+ t    StackImpl() {
7 u! u, p# U# k; |% A4 ?        element = new Object[defaultSize];
6 y: w% D" w0 t: W5 y7 }9 V+ v        maxSize = defaultSize;
    }
3 J  d4 X  W) l2 T9 w: n) r
    StackImpl(int size) {
        element = new Object[size];
        maxSize = size;
    }

: a' Y& Q$ `% G3 W' K    @Override
    public void push(Object object) {
* R/ D" B& e( G3 G        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
' y0 @( X- X5 e7 I. a! a9 ]+ F: E            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
3 u" I; t3 `* b8 ?0 v! H        element[elementCount++] = object;

    }
6 U" }( C" b& C3 h* u* q/ L        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
# h. f1 r8 k& {  I/ \8 s" j- E    public Object pop() {
4 B6 m$ O- K: v3 @        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
. }! K" N# B% `" _& A2 C        }
        Object object = element[--elementCount];
; Q9 {6 s4 l) t& N3 W: ^& q        element[elementCount] = null;
- q3 _5 t; T" H* R        return object;
# I8 N1 g0 b  N    }

7 R: I0 x8 `! }* Q! ?* \    @Override
    public int getElementCount() {
        return elementCount;
( t) ]& V8 s4 L6 R3 U# r    }

0 ~1 }- }7 ]4 _    @Override
    public void traverse() {
$ G& R7 B/ K- n  \: f        for (int i = 0; i < elementCount; i++) {
) v; _; y. j; k5 d2 i6 f            System.out.print(element + ",");
* t# @4 T% L3 a; q. o8 M& p        }
1 i; Q8 e( V5 N- j  G& V) [        System.out.println();
    }
+ D2 O3 c( G+ ?, l; ~1 t}
$ A7 E* }  H4 N  v3、栈的测试
public class StackTest {
    public static void main(String[] args) {
7 {: j3 v( d1 M5 a, ?# M3 ]9 [        Stack stack = new StackImpl();
) ^" M1 o4 w  `# l2 `7 `
4 ^( K) {! N/ F0 @( e        //第一次入栈:压入1-15
1 s( @3 j6 y  a# b/ z0 Y        for (int i = 0; i < 16; i++) {
" x/ r$ P4 s: Z" t- B8 A  P            stack.push(i);
4 t9 f6 ^& \6 u# a  k* f! E; [        }
$ m1 `. K& F! H        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
+ i, ]2 `9 H( ~        stack.traverse();

, X- d5 B" v; `        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
            stack.push(i);
2 B) {5 X9 ], H        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

4 q1 u4 n- a* u        //第一次出栈:取出31-16
& r! {  K. C+ T; O% L        for (int i = 0; i < 16; i++) {
            stack.pop();
8 z2 E$ Q3 w$ S! }- b        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //第二次出栈:取出15-0
5 w; I3 \, P2 z; o4 d        for (int i = 0; i < 16; i++) {
+ |6 f3 g0 O4 H  K3 S            stack.pop();
4 Y5 u1 ^" s( i- M6 j& D        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

+ ]( _  @4 A; H. T        //栈中无元素，出栈报错
        stack.pop();

    }
}
6 q  G0 k* T4 d4 a- B' N/ Z
! p7 G! L: u$ d/ D3 a# g
1 Z! S+ K4 d. F+ g; h% T
4 Z$ U( O& W4 G* e2 K& c
- ]/ @( z/ S( u7 h! {% f; G  G# R三、 用数组实现队列1、队列的接口定义
/**
. U; @( U9 U0 C" t; A! k * 定义队列的接口
*
* @author zhuhuix
+ C/ O9 j5 Z7 m! n, n4 z) V * @date 2020-05-01
*/
public interface Queue {

    /**
     * 获取队列大小
     * @return 队列大小
     */
    int getMaxSize();
/ M0 V- l- Z# p
    /**
     * 入队
     * @param object 入队元素
     */
- m7 R% T6 I2 x  a5 ^" K0 n" d$ G0 D    void push(Object object);

4 ?2 F) X; J3 f% s' k, b! ~    /**
     * 出队
$ ]9 w( _' e# Q2 u5 [9 T4 V8 v     * @return 出栈元素
: o$ D9 t" i8 l" J( }2 j3 H* t5 Z     */
    Object pull();

    /**
     *  获取元素个数
4 X9 h; r2 n6 W( b2 c     * @return 元素个数
. C) h2 |: }/ T( w     */
    int getElementCount();
8 R3 U4 i  z6 T$ L0 n- w
    /**
6 n5 R; w( x, z# J2 g1 A     *  获取队头元素
     * @return 队头元素
- `# m* J! C9 N0 ~     */
    Object getFront();
! q! o& |2 M0 v  A* p/ a3 |: b
4 ^1 v/ R* P7 f: y9 h1 A7 H    /**
( n; y# f& e7 ?9 r: @     *  获取队尾元素
$ ?6 E  [- H3 ^% p/ F8 \0 ?% _     * @return 队尾元素
     */
    Object getRear();

    /**
, U+ \% G$ C+ e     * 遍历队列的元素
& \% G9 ?1 V+ G4 `     */
    void traverse();
* ~) m5 F8 L) i: g3 o" V}
2 F' J/ _: A. K8 E2、队列的接口实现
5 f8 H. d4 S8 ?( Z- R$ B( x/**
. @, z; Z5 ^8 U2 v9 U% U. o * 队列的接口实现
/ Z. s7 O0 v5 g *
1 p" c8 G  [, z# \ * @author zhuhuix
) a5 l+ @2 b/ [4 N% t* O- l * @date 2020-05-01
*/
public class QueueImpl implements Queue {
* [: Q; X3 S9 R; l
% J% x% K" g$ K& s    protected Object[] element;

    protected int elementCount;
- e+ L. h; {/ i% H: G
/ ~% l( F) p+ N+ V/ v    //队头
    private int front;
; l9 R: l* U- ^
/ P& f, b: h& [& ]. i3 Q    //队尾
    private int rear;
- U, T5 v1 g6 B+ O
; T7 O" W  R8 G    private int defaultSize = 16;
  S: n9 E2 F$ n$ y7 D
" o5 F9 n1 ?$ A1 B    private int maxSize;
( m5 Y* R# I, X  i! C
! K( L, w6 D3 E% {    QueueImpl() {
        element = new Object[defaultSize];
  [2 c: i, u! d3 E; X% C7 K) E        maxSize = defaultSize;
        front = 0;
        rear = -1;
    }

    QueueImpl(int size) {
        element = new Object[size];
$ V; W8 f. s/ F& X6 Z        maxSize = size;
        front = 0;
        rear = -1;
) q, Z6 o7 J( V& Z: r    }
3 ?  {2 l8 G5 C5 P' o% R9 |
    @Override
/ v6 d" K& e) P" o) }9 ^    public int getMaxSize() {
        return maxSize;
    }

    @Override
    public void push(Object object) {
4 q! \7 i+ ^& m        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
1 h6 `  I6 a" M( j% p  R- K        element[++rear] = object;
        if (rear == element.length) {
            rear = -1;
2 w: a( r  V1 S. P6 k# k9 z( Q* w        }
        elementCount++;
    }

) \* o2 V! T/ ]9 f, i    @Override
    public Object pull() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
        Object object = element[front];
        element[front] = null;
        front++;
        elementCount--;
6 L- o: W% B! g  }+ A0 h% X        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
9 T3 a2 w. G# M' a8 N+ z9 T# I! P            front = 0;
            rear = -1;
( d; l3 |4 l: h1 e  M0 ^+ y# q        }
# ?3 P+ f, k3 r$ p2 Q+ S        return object;
9 Z( \7 ^# F) ]    }

    @Override
    public int getElementCount() {
        return elementCount;
& p+ V8 Q1 N2 v1 B    }

7 O' W2 m5 S1 f    @Override
    public Object getFront() {
        if (elementCount == 0) {
- q* k! @7 J' [% ?' B" X            System.out.print("队头无元素");
            return null;
        }
        return element[front];
    }
! L* c8 x- l2 n
6 G2 D0 N$ U8 b3 e# l    @Override
3 s3 ^. ?: j, p8 v! v0 k+ q    public Object getRear() {
; T: _9 R7 H5 x' |        if (elementCount == 0) {
& ^2 Y' i, k9 \/ i  S" C1 E            System.out.print("队尾无元素");
            return null;
        }
        return element[rear];
9 y3 Z. S9 s% ^& z0 f    }

/ _; f0 L9 e8 w, o0 s% S6 o/ B    @Override
    public void traverse() {
' x7 J$ j/ A/ V: m) t) P3 b! b        if (elementCount == 0) {
            return;
        }
        for (int i = front; i <= rear; i++) {
            System.out.print(element + ",");
7 U9 b7 ]3 Y- K2 \        }
        System.out.println();
    }
' D& n5 p5 F: x7 Z3 ~* n, T}
5 J; j! }/ G- l- J; E* `- W
' H. i, R% B  b( Z; U9 D' U
/ l0 k6 {% p( U3 ~7 d3、队列的测试
public class QueueTest {
, [* K1 H& Z8 [- {( U% f    public static void main(String[] args) {
5 Y5 [: {: K* J( o5 k! e2 S% R1 p        Queue queue = new QueueImpl();

- D0 q. j  h5 y! h% o        //获取队列大小
( U  Y! N8 d- E, K, N        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
6 a4 e. t! g. s  Y' u0 ]# ~
) D, b/ l' K! m7 n        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
1 X) C3 T0 g. c& q            queue.push(i);
9 j: U: R  C- q: z        }
* V  I& `& U) p        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
6 M0 L& x; [" W1 {4 S6 u        queue.traverse();
* C; L- z( k! P* K- t        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

        //第一次出队:取出0-15
- l- h7 A8 l3 O/ w        for (int i = 0; i < 16; i++) {
% Y, r7 G6 s: ^, T8 v7 j) Q6 R            queue.pull();
        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
9 y0 x- w# `9 ]( ?  l5 n# |& O

        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
            queue.push(i);
        }
9 a* p0 D0 X# r1 O- C! L5 D+ p        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();

( D% b5 P2 U7 q  H
        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
. \& }7 S3 I4 `5 W            queue.pull();
        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();

1 n/ Y  D" }1 K7 \        //空队列出队报错
        queue.pull();

    }
}
# ~+ K$ P" h: ]) F: A: r% Q
) P) b0 e! [/ A4 s9 m; ^

7 w) ]0 P( l' s: ^# X$ a( l

$ Z3 d+ h& ^1 H9 c: n6 c4 j- K. e. Z! h
& a  U9 d6 G# z% k2 m

2 n: [7 I8 G% `; B  c7 W3 r
8 o# I% t1 k! r/ K; D3 J" E4 h

' M( e. {" @2 M! q% e4 K1 r
. y% l8 d- e4 k* u5 O

, S! L6 b& q# U: O$ o; s
0 E: w7 B7 o$ h' g8 n* y————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* R% W7 P( \- v, @5 T, K原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
6 y- y% h% W0 E) y3 a
4 o2 g- ?7 @8 u) X: q% g
# m  v: Z* u; n3 h3 h7 h

---

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

Powered by Discuz! X2.5