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

杨利霞

数据结构——栈(Stack)与队列(Queue)的手写实例
6 z( }0 u+ c$ R
[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  4 w+ h; K7 y2 I/ k1 {
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    % h  m* v: Z. ]
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

/ y; o: S6 o7 R/ Y. [
一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
3 k- Y0 E# a9 F; y. W2 C% h
　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。

6 @- M4 i' L0 D0 N
5 \4 F' |- A( ]5 B3 ~, I
二、 用数组实现栈1、栈的接口定义
' l+ y. U/ V! Z& E: l8 r! m- v8 w$ c/**
5 {0 T: K' c+ z% }2 Q1 u9 k" c * 定义栈的接口
*
5 }+ u! d, {, }  l0 _7 A: W3 f * @Author zhuhuix
  c1 r) C; h% r& q; [ * @date 2020-05-01
1 }. }: q# L1 K$ g* A- w */
public interface Stack {
    /**
     * 入栈
$ w) t7 }) h7 K  w$ O0 G     * @param object 入栈元素
     */
+ x1 d' \/ P% r2 K    void push(Object object);

    /**
     * 出栈
     * @return 出栈元素
: _, O. L* V4 s2 X     */
    Object pop();

7 e; @0 @9 r6 k$ g8 @    /**
0 D- p! `  U8 X9 X' J1 A# m     *  获取元素个数
0 v2 i, q% M. T6 I9 u+ v     * @return 元素个数
     */
+ e( O4 J$ L$ h/ V4 [    int getElementCount();

- W/ f1 K. B4 n& V$ ?# m7 @$ k: ^8 Z    /**
3 U& r, I, N* }     * 遍历栈的元素
! P) Z: ^: W7 ~6 f/ @/ o4 G     */
    void traverse();
0 o& H. \( I! G6 K; Q
}
2、栈的接口实现
: b4 r$ i- U5 w* G  I) P% ~/**
2 Q# n. q4 j% W- V4 B * 栈的接口实现
; v9 Q8 ]8 v% k( ?% a *
* @author zhuhuix
* @date 2020-05-01
: @& k+ J* l" V: O5 w" k */
6 x  s( S" Y: c' q3 hpublic class StackImpl implements Stack {
       
& J! N7 Z( ]9 V, `4 C" X) D1 p$ _    protected Object[] element;

    protected int elementCount;

    private int defaultSize = 16;

+ t7 S/ j5 O8 n9 K0 Q& o* a8 e    private int maxSize;
8 d# V3 |1 M- }2 D; P( N
    StackImpl() {
7 c5 G+ X: P4 L% T4 W        element = new Object[defaultSize];
        maxSize = defaultSize;
. u7 ~5 R) f( p% D% m+ ^    }
0 u* G& @5 |; A& e2 R* ?
8 `" H/ |) o& Q* F    StackImpl(int size) {
        element = new Object[size];
        maxSize = size;
2 q  s% v# H  t( N3 ^  z    }

9 ?4 ?; s$ [, d) k6 N    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
; v+ Y+ a2 Y. T5 A0 J            element = Arrays.copyOf(element, elementCount + defaultSize);
# V4 r% h: `( {2 h- Z; X        }
4 P7 L+ a/ z' v: k8 N: m/ ^        element[elementCount++] = object;
, ~+ R# d0 A* ]) a. c# Q0 D! M, y  ~( G
5 y" }; N/ F/ [8 G    }
4 r. o" ?1 w) U+ R5 W        // 本代码未实现数组的自动缩小，具体方法可参考JDK
* i$ V) f8 ~! C    @Override
" s- L3 d$ b3 ?5 v4 c0 h    public Object pop() {
/ a5 k1 I( b) }0 A/ i1 O$ k        if (elementCount == 0) {
6 }+ h) R6 d% p' e6 @/ O4 u$ c  R            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
' u& E6 S, y9 m8 G+ _* d        element[elementCount] = null;
2 g  P) \" f6 C; i6 }" v1 z& j        return object;
    }
4 P, a* b3 ~. i# H
+ P+ z& x* |1 G% g    @Override
# j  K' y0 ~" d/ l5 z    public int getElementCount() {
, P7 I& r8 p9 X- [7 n9 |        return elementCount;
6 y9 s/ G2 r0 Q+ q! [2 K4 Y& e6 _    }
' l6 B! h& b( o" T1 M+ n" x% {
2 e( ]6 a$ H2 v& }) u& r. q3 Z    @Override
9 A" [4 F( {! q) U) M" U) r    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
2 x% I. ?) Q  k! r- Y        }
2 r- B3 ]' T5 f' a; W# ]        System.out.println();
& s) h/ F) h) \! V3 h# I    }
}
, e7 V( k; K6 I' c) v4 ?3、栈的测试
public class StackTest {
    public static void main(String[] args) {
        Stack stack = new StackImpl();

* t+ W) E2 M: e0 \; r4 \) {7 K        //第一次入栈:压入1-15
+ ~$ o+ I3 p, f+ L8 o) h        for (int i = 0; i < 16; i++) {
- m, U  @. F5 Q5 u, e7 |8 t            stack.push(i);
        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();
* X+ _2 T3 f% b4 `$ }5 x& o
4 O  z! V" |0 ?) O1 y5 b) C        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
            stack.push(i);
% r6 V# _! X( J+ s0 v, l: c* S" B        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
8 @$ s4 ^% z& [. N
        //第一次出栈:取出31-16
' ^5 k# D. u. N0 Q, S8 ~& D# q        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
9 C# w  S2 X* G: x6 \        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
6 r* P$ I1 P! [* e# R        stack.traverse();

; m) b, m$ n; q: d, d9 m) S        //第二次出栈:取出15-0
) [& j3 ~! K8 u8 X        for (int i = 0; i < 16; i++) {
3 ]- _1 J2 g7 H7 ~6 Y' x& _4 \( G            stack.pop();
        }
- K0 s$ e  _; C/ n& v        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
& \% n/ U2 w/ ]        stack.traverse();
7 s$ Y: I, S, Q% K9 Y, `/ |: r
8 ^0 E8 _6 u" s; Z        //栈中无元素，出栈报错
" |$ U* T- K0 C; F: v5 N        stack.pop();
* V& d9 F* N, e9 g* N
    }
}
5 @: Q; Z* j; C
, E+ `8 Z: Y( S  d! B5 H8 t& F9 ~
* ~; U# }3 t& s1 @

三、 用数组实现队列1、队列的接口定义
' v0 s! f9 Q# J- K/**
7 ~3 ~' K7 D* z8 \% p9 j% l5 G+ B * 定义队列的接口
*
: t8 ^  u, D& h$ g * @author zhuhuix
* @date 2020-05-01
*/
  J2 ]7 D) |  J' K) ~$ m8 U7 Ipublic interface Queue {

    /**
     * 获取队列大小
     * @return 队列大小
     */
1 @- \$ P. z+ v$ o- y4 G1 o    int getMaxSize();

    /**
" r% P& i' c" I* t3 K& d0 g" i' ?     * 入队
     * @param object 入队元素
     */
    void push(Object object);
' v! ^% G2 g& O* m9 @. p
" \9 S. a; Z/ K8 Y7 T# a    /**
     * 出队
, D2 P+ y2 o8 g# O4 Q3 w; b     * @return 出栈元素
1 i9 ]5 Y, w) b' g- v' a5 u     */
0 c1 e6 w9 @5 R5 d0 P( B    Object pull();

  v) V; s  x- b: {. v9 g/ C. U    /**
     *  获取元素个数
     * @return 元素个数
4 V- N; Z8 ~3 \8 [# J     */
5 O# L+ l, C! t+ ~! D9 ]9 G( ]    int getElementCount();
# G1 R- y$ I5 V5 W& H1 ?7 o
5 u$ L. z( l( i  Z/ S7 z    /**
9 r! c/ O9 L, e     *  获取队头元素
     * @return 队头元素
1 e" b3 ^+ c0 v. w+ s     */
) j1 Q5 n- ]% }    Object getFront();

* R! o- ]+ q5 t    /**
     *  获取队尾元素
! o2 \. @4 W. X) b     * @return 队尾元素
     */
    Object getRear();

8 I" T9 h: N' D    /**
5 o/ N% u# p0 F: k: C2 S$ Z. O     * 遍历队列的元素
* e) m# o/ T5 Q# \) s     */
    void traverse();
}
2、队列的接口实现
) v. F& J% J4 Y$ X9 \/**
1 d2 q* |3 I* i9 q) d0 l. M * 队列的接口实现
! j1 u- ^& F& G! y4 ^; P5 Y8 t  H *
7 T2 ~/ {) g- J  f8 e * @author zhuhuix
) K7 @, |2 s' H# S0 u/ B* J8 Z * @date 2020-05-01
*/
public class QueueImpl implements Queue {

6 N: u# a% `: F: c    protected Object[] element;
  f& V1 ?; g9 e
    protected int elementCount;

    //队头
$ r5 T3 q6 j( h( L& b3 z    private int front;
9 j- I! k7 L3 `7 `4 h; [
    //队尾
8 Y4 H; ^8 h. O6 P$ {9 U    private int rear;

    private int defaultSize = 16;

/ i+ k  l3 y& K. H/ b' J& g    private int maxSize;

- O7 k# c8 D8 J  b7 r6 ?7 L  _: J! Q    QueueImpl() {
7 D* Q, ]  \+ L( S3 V        element = new Object[defaultSize];
. ]& l/ @( d8 I        maxSize = defaultSize;
        front = 0;
        rear = -1;
    }
. H3 j& w" n, p6 k
- s$ x9 p( W5 {1 ]5 _  k    QueueImpl(int size) {
) f1 z) x$ k7 U, g: r0 C        element = new Object[size];
        maxSize = size;
! K4 Q. q# ]! k1 {  x% X$ B* n        front = 0;
        rear = -1;
    }
/ K+ u: }9 N: [, `. z
$ B, {5 A/ `. h. }    @Override
    public int getMaxSize() {
        return maxSize;
    }
8 C5 W9 Y9 P* T$ `( C$ q4 X
    @Override
' @' w3 F+ I# }    public void push(Object object) {
: d4 d* d% x  r! f& y6 h        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
        element[++rear] = object;
% f4 l5 M; I' R7 A* C        if (rear == element.length) {
! D$ T9 @* C6 \( k/ x3 S1 I) R. m            rear = -1;
        }
9 W. i3 y2 q; s0 U! U, D        elementCount++;
0 ]; V2 O, O7 M; \: J    }

) q3 g! s  t. u4 l! Z    @Override
    public Object pull() {
5 D, v7 z6 q2 l! k2 c# s) _3 u: X        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
3 D+ A  m/ b& X2 T0 N- }        }
        Object object = element[front];
/ K( ^) e5 l( m  j2 r4 S        element[front] = null;
        front++;
3 l1 |( z7 a& {9 k        elementCount--;
9 S3 y% `" c5 {: l$ R9 E5 x  J        //队列清空，队头队尾恢复初始值
) \- F9 J1 H& `; Z        if (elementCount == 0) {
! `$ o; f1 f* H! {            front = 0;
            rear = -1;
        }
$ O8 i$ o6 z  d        return object;
* A& i9 B$ K, z! X8 d9 F8 T8 P    }

6 T) H5 x) |1 f    @Override
    public int getElementCount() {
        return elementCount;
    }

! F/ a; ~' }7 L+ \    @Override
+ \  i( S* D8 `    public Object getFront() {
1 D0 F, p8 o/ s' w0 [$ x        if (elementCount == 0) {
8 J9 W8 b; ?6 |            System.out.print("队头无元素");
9 C/ J3 {7 N; V% k$ C  Z" V            return null;
; @, R0 j, q: i3 D' W) ?        }
        return element[front];
    }
/ L+ H2 o$ s& b: w% `6 a
9 ]# D) C7 M3 z    @Override
    public Object getRear() {
        if (elementCount == 0) {
            System.out.print("队尾无元素");
            return null;
        }
# D5 H* U( t" K- z0 P& Q! O/ `( I        return element[rear];
$ C, H- _) f8 D5 u% W    }
# E; q  j9 K" v5 V
6 a$ S  ^3 R4 u    @Override
4 B8 g9 K) y% W* a( W    public void traverse() {
        if (elementCount == 0) {
            return;
1 G- h' ~* K. \( e" \        }
        for (int i = front; i <= rear; i++) {
) H$ d! i/ h0 d            System.out.print(element + ",");
* L) ?* q3 E/ e3 N8 ^/ ?# r        }
* G2 }4 q! _9 k# ]        System.out.println();
    }
}


+ l& p) D/ b$ w7 Y# ~# V3、队列的测试
public class QueueTest {
    public static void main(String[] args) {
        Queue queue = new QueueImpl();
% K8 \% B5 _. ]. I1 Z
" l  k9 E& {6 e# v+ O+ r$ V# u        //获取队列大小
/ V4 j. V2 f* I7 L: v* X; l        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
: N# B; _, y- `& ?  W: }0 R
5 ]6 A6 M* C3 }        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
, H/ @' H# `  j* O2 i            queue.push(i);
        }
% x7 Y8 |* U+ E        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
" J5 S4 `( ]! V% F        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
  e5 V6 F% X" \/ j+ ~
        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
1 T$ k7 a2 Q; V& n! T7 T        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
8 g4 f1 j5 t9 ^* k+ j6 N- O        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

$ R! A/ M$ p5 H  r1 E
/ _! H( p* f1 J* _' {1 H        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
1 a1 c& q7 z$ w8 R7 a* R  w            queue.push(i);
# ^# B9 d1 E3 D6 y9 E/ |% `4 L- i        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
' i# e. x0 D, B        queue.traverse();
4 k# K5 i1 I! v3 j3 u/ X! V

- B/ o" H0 m) ^1 p4 L6 @6 w, Q        //第二次出队:取出16-31
/ Y0 k  }4 f' c/ C/ b" K7 S, e        for (int i = 0; i < 16; i++) {
! t' {* N, E" n$ O+ B* B            queue.pull();
) Y2 |$ X& u; Y7 ?" X/ {        }
* L( }5 r8 X% V$ q; D        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
* L1 l6 j# D. T# l, X' B* }        queue.traverse();

        //空队列出队报错
& T: d* c4 w  s+ |% s7 J/ j) f0 Z5 \' t        queue.pull();

    }
}






1 [3 _+ i3 l+ ~( l( Z3 |
6 p/ E. a; T4 e! s% p6 k
9 f" o, f& K& r8 [. w

, q2 @% L0 v/ h' ]- p6 R
1 q; b3 X- O! }5 R$ @



# ]9 ^2 H5 e+ H6 j) U————————————————
( @  T. ^; E. z! _/ B  e版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785

% a% X- `* |% o) \
2 F  y/ o! O% `0 b4 ^$ D