数据结构——栈(Stack)与队列(Queue)的手写实例

杨利霞

% U. q9 v5 j# m2 \% `数据结构——栈(Stack)与队列(Queue)的手写实例
0 u9 P$ k3 b! u- [, M& M
[color=rgba(0, 0, 0, 0.74902)]文章目录

- e( `; h2 X6 c1 ]; ^+ T  d( R- a
• 一、 栈与队列的定义
• 二、 用数组实现栈
    v1 m' j3 D* ?  z" m9 i
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

( m7 T; X, w# x# L! e" k* f* ?一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
8 T- M, i) g( v2 I
% W& l2 g& M2 Q　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。



8 m8 p, n" r! ~: w0 T- d/ B二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
*
- L1 `; p% }7 U7 ^' b; h * @Author zhuhuix
* @date 2020-05-01
*/
; o& s+ O& B* P7 l% Cpublic interface Stack {
    /**
* G0 }1 h7 u' Q% J; `     * 入栈
& c1 O- |9 g/ i  @, X' Q# m' S8 g4 w$ D     * @param object 入栈元素
     */
) g2 m8 M6 h9 y  q    void push(Object object);

    /**
& W* ~! Y- M9 A" t( Q: |     * 出栈
5 K: I- l% v7 w, t     * @return 出栈元素
6 F, `9 n: `& {; N- ?1 \     */
' i' J  D5 z. P+ J8 F' G    Object pop();

    /**
& o- @* n6 n2 ^     *  获取元素个数
     * @return 元素个数
     */
    int getElementCount();
7 n' H4 \* K5 e! w6 \2 v
9 w5 r$ r( f0 p' J* k8 E    /**
+ L. u) S3 A9 y- l$ a     * 遍历栈的元素
     */
2 E' W$ }; a. Y) {5 i! ?% ?" J    void traverse();

}
2、栈的接口实现
! I' W9 K; B- ?' a! v0 t/**
3 X/ J8 H& `6 f1 O$ C8 {" B * 栈的接口实现
: b* Y2 a: y2 e5 N *
) i7 x* r0 h0 {0 |9 V( d  L * @author zhuhuix
) E2 ?- w! d  c * @date 2020-05-01
*/
/ {, \' n* x/ y- d) X  y9 Epublic class StackImpl implements Stack {
       
    protected Object[] element;

% ]' Q  ]- Q/ \2 o# e    protected int elementCount;

$ q  G! ~. b& t$ k3 f7 P' n    private int defaultSize = 16;
- F& {5 G$ f* l; a
0 F: ^5 _4 @) E2 q    private int maxSize;

. B: {5 r2 K. b% K) @    StackImpl() {
        element = new Object[defaultSize];
  h9 O8 |8 `  R( {7 _1 s4 W* i  C0 A        maxSize = defaultSize;
+ T  p. f: H  m0 I  T  B8 B  M3 O    }
1 ]$ V/ k- Q4 A# A$ Q
* Y/ p1 N- R1 T5 V7 R    StackImpl(int size) {
        element = new Object[size];
        maxSize = size;
6 G# z7 f7 y1 d/ z/ E9 T    }
: i2 J" d3 [) z+ Z# R( d
    @Override
% l2 H7 K- Q9 R! u% Y! T    public void push(Object object) {
" s- y" d7 I' L1 M6 s5 w8 ^) _        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
, J1 j1 {# O- \% i( D        element[elementCount++] = object;

    }
        // 本代码未实现数组的自动缩小，具体方法可参考JDK
% Z7 [9 E! l# Q+ n. W6 }    @Override
6 X( q% g# e6 f    public Object pop() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
) I% D* i6 }( O. [+ l) T        Object object = element[--elementCount];
        element[elementCount] = null;
        return object;
8 U& ?; L' o! ^. L    }
0 ?' \3 V. ~8 R3 D1 o0 G
    @Override
    public int getElementCount() {
        return elementCount;
7 u3 V( D3 {5 t    }
+ M) l: Z; [$ `! d1 t# h2 P* E
    @Override
    public void traverse() {
# }7 u% I/ f9 H4 T) ~- ]5 p8 C) f        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
        }
        System.out.println();
    }
}
3、栈的测试
public class StackTest {
    public static void main(String[] args) {
6 ]2 ?! q' a* N        Stack stack = new StackImpl();
! t/ w! a* w! q5 c* [6 N# e8 i) b
        //第一次入栈:压入1-15
7 X& c2 F; X, e$ N9 L; L$ j: L        for (int i = 0; i < 16; i++) {
1 ~& X# J' f4 p/ y2 Q            stack.push(i);
3 U: s' h& W5 t5 B; |, M5 e& E        }
/ @# l$ T- J. ]9 R8 [1 t; H8 {        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
5 m  x" @6 Z; g  A- F, o        stack.traverse();
1 U* k$ Q6 z( D' h
        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
; v, B3 {% |% e, m            stack.push(i);
        }
8 o2 @0 l% U) n: Y. b  y* ?9 T7 @        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
2 U# \+ E) i* n- B7 \
        //第一次出栈:取出31-16
% I$ b% |3 i" N4 c' Q& X7 P/ _        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
, v: w1 G) W9 ^( t+ h        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
! k( R+ b# Q) x* ~6 Z9 x        stack.traverse();
3 h" q8 U; x; W
        //第二次出栈:取出15-0
* K5 ~9 U5 J/ S3 _1 `' q& t- [3 h! X        for (int i = 0; i < 16; i++) {
, R5 S8 e) H! {' x- y2 _' ]            stack.pop();
4 V( g6 u2 z2 v' o) m/ W& k        }
) i2 _8 s& O- F1 Z/ R. G        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //栈中无元素，出栈报错
        stack.pop();

    }
}
) U) T, ~4 X, J- e$ ~+ w. Y
4 t# f. S6 L: Q( Y2 O3 O
1 [' ?7 D/ x2 @* y$ o
2 X- G- m) ~; I/ ~' H+ P
三、 用数组实现队列1、队列的接口定义
* P2 a: k3 r% o+ w, Y0 p+ M/**
* 定义队列的接口
0 q3 r7 K0 u5 q  H: ~+ X+ |1 a9 ^ *
8 b: M" q/ o2 i * @author zhuhuix
# n/ d  V4 q  G/ u2 w/ h! n4 z+ U* ` * @date 2020-05-01
1 M7 L6 p# T- C- S( p2 `5 [5 r */
6 {; }  j0 l! O8 f) w+ ^  H* m2 z* O' Ypublic interface Queue {
  s/ {4 x/ _" r$ _4 h2 X
: g: I+ s, o' @+ y    /**
2 ]) y2 f: z# G/ }. S; f, D     * 获取队列大小
     * @return 队列大小
# x: K' B4 k2 j; R4 j- @9 x. u0 l     */
    int getMaxSize();

    /**
) g. S* M( t2 L) b1 u: Q5 b- X* C; R     * 入队
     * @param object 入队元素
     */
' s) |) R3 M5 `& v3 H3 p/ o* p    void push(Object object);

    /**
     * 出队
: M7 O) D, W; |( D) Z     * @return 出栈元素
. h: K" D* |( Z+ x1 e3 E5 c     */
# ^/ x  U  p1 F: K! _  }, K    Object pull();

7 A* M' v2 q, d9 W; e1 V2 V3 {1 R    /**
     *  获取元素个数
( b, s5 r: u; D; n* b. t1 n     * @return 元素个数
     */
' C! t. k% x  B6 u0 T' e    int getElementCount();

    /**
9 X( z& T$ @% A$ e# P     *  获取队头元素
# f9 v* E; Z8 h! ]" Z1 T) A     * @return 队头元素
     */
6 K3 s3 l' Z1 l& T( d    Object getFront();
$ e- h4 \; G3 Q, b3 n4 ?3 {0 [
    /**
* o4 n( {! c7 ~1 ?     *  获取队尾元素
+ E9 C. X& {6 a* G     * @return 队尾元素
5 L: y5 A4 q# e     */
    Object getRear();
/ j" e' z0 l7 |
4 s  V/ B2 E4 G; }; F& n4 c    /**
     * 遍历队列的元素
     */
    void traverse();
}
" W% u3 H9 a  k# L6 p) K2、队列的接口实现
/**
* 队列的接口实现
7 e$ U3 @5 h( }' T% I *
2 X" A7 B$ a  Y9 t * @author zhuhuix
7 |, d1 g' B+ S8 A * @date 2020-05-01
*/
public class QueueImpl implements Queue {

. {) B; _  m* Z# W    protected Object[] element;
% c2 W  R! F4 v0 W3 o1 t
+ m. \: H, v1 a/ c# W    protected int elementCount;

( P" @6 |- P% [! X    //队头
    private int front;

    //队尾
% G; Q: ^" x7 c9 S    private int rear;
9 h' y' J: U: `' N0 U( h9 W
' Y- g1 o+ Z% v% X& `% }2 b    private int defaultSize = 16;

9 u3 v. @2 K1 Q. L& n: j: E    private int maxSize;
0 h5 h( n; ^/ K) K+ t
9 u6 h! R, ]6 O' b- F    QueueImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
  ]; h7 ?1 `- P( Q9 S        front = 0;
        rear = -1;
* L0 U  [0 c3 t( a3 j- R% h    }
: U$ K! h3 A. a2 m- ]  [
    QueueImpl(int size) {
        element = new Object[size];
        maxSize = size;
0 ?# m" [3 ]; N) u" `        front = 0;
        rear = -1;
    }

    @Override
    public int getMaxSize() {
        return maxSize;
9 Q: E/ ]2 I& \& Z6 N" N    }
  m( m0 i* k! W) n9 _; ?3 o" }
    @Override
4 z" n8 y3 p' \- N6 l    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
! M% R3 i% C2 J4 v/ \        if (elementCount == maxSize) {
( X, h" \$ ?: Y, Y            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
( ?7 ^1 \4 j) n        }
        element[++rear] = object;
        if (rear == element.length) {
            rear = -1;
/ A" \- c. w% u6 Q3 g; t        }
. G! J# Q; A0 ^, R3 |9 @! E        elementCount++;
    }

    @Override
    public Object pull() {
* T3 t1 X% E1 ?: y5 V" c: W! j        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
        Object object = element[front];
5 R4 N) J' N$ |9 u2 w        element[front] = null;
        front++;
7 f; c: G5 U/ F/ a        elementCount--;
+ A2 [4 x; ]! [+ V2 ]        //队列清空，队头队尾恢复初始值
) j, J' C; z! S" j        if (elementCount == 0) {
            front = 0;
            rear = -1;
        }
        return object;
    }

    @Override
' A+ H- J9 z" e3 V    public int getElementCount() {
5 g/ B. M; L8 u: [        return elementCount;
0 c- |. c4 k6 Q9 I' G    }
4 I. A3 G! s  R% N
    @Override
    public Object getFront() {
        if (elementCount == 0) {
6 R7 i! F2 l$ u1 Z* a            System.out.print("队头无元素");
            return null;
        }
$ y" F& g; ]: `# H  z4 c! V" D        return element[front];
    }
. M* Y, M: T3 V: L- y: l
    @Override
    public Object getRear() {
& Q: m9 K/ L/ U$ ]9 f! ^* d& o. l        if (elementCount == 0) {
& F! x" _1 T0 e; y/ h1 N7 U4 Y            System.out.print("队尾无元素");
            return null;
( g$ }' i0 @: [8 {8 E8 b( N3 ]        }
5 S" a6 ?( C0 t; Q- `! m        return element[rear];
    }
# {3 x+ P6 I5 L( H: `4 m5 r$ A: {
    @Override
    public void traverse() {
        if (elementCount == 0) {
$ b0 g  \$ G) i            return;
% S- K( ~/ b/ A3 ?% c+ C        }
4 E- w. b/ w' r        for (int i = front; i <= rear; i++) {
! K& E. A8 V  C7 {            System.out.print(element + ",");
        }
        System.out.println();
, P0 y$ |- a" d8 z9 M: K    }
}

0 {1 f& V, Q% H( B: K$ y
3、队列的测试
% i. S5 ~6 t& p. A+ lpublic class QueueTest {
4 F% i$ @$ z! f/ t# A    public static void main(String[] args) {
+ v; p+ K; i* j! Y! Q* b/ I        Queue queue = new QueueImpl();

        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
6 g( S& w! M' L* O0 r3 h            queue.push(i);
, y9 }  S/ g, x, w4 D        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
& C6 D& Y2 ~  G! t8 f3 Q6 g9 M9 Y        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
6 t. n( d  v7 v# N3 h! F
        //第一次出队:取出0-15
2 P, b; \( |; H( _+ p" ]3 d& e8 @        for (int i = 0; i < 16; i++) {
7 Q! {& Z/ O" A' Y* \) c: ~4 [# V5 q+ u            queue.pull();
        }
9 T& r: S- I( `9 t' G- C$ r2 d2 v        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
- B! ^9 u: n" D: V        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

3 X; F! w+ b8 g
2 D  Y1 D/ G3 U: x        //第二次入队列:压入16，31
$ V% W) v$ s' R) @        for (int i = 16; i < 32; i++) {
! i; G! H) ~3 E4 K" F. y            queue.push(i);
        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
. D$ j! N- G! f$ B, Y1 u
! Y/ I8 v/ d" F- a3 K
; O0 M' }2 R7 i5 [  l  s3 ?        //第二次出队:取出16-31
3 i0 q) T+ H8 E& }. S* ~        for (int i = 0; i < 16; i++) {
: u9 x3 t; F, m* A  H0 V            queue.pull();
        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
& Y) S& O$ x" e1 T. H' ^; N        queue.traverse();
+ d$ U/ p1 N, B. Z9 p( A# B
. g4 r/ ]. U/ [- L" l6 }        //空队列出队报错
        queue.pull();

    }
}
( s, `& q2 Q# B& m% c
8 I' ~, o# W7 H  m: V; t, r


4 F2 n: P' G! {


: V: Y) s. _: {; V% U



; G$ L5 y+ e' [# @$ u
9 j- g8 @% }. o( K& l8 b. m9 f
! ]& o) t# W) w) K& h2 f
9 ?4 H. m7 I3 j3 G) |# G
————————————————
% D! ?0 a& n+ h版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785


& a% X) {* I5 f# y2 h