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

杨利霞

! |1 Z3 h' Q. f5 @% j数据结构——栈(Stack)与队列(Queue)的手写实例

8 S  i3 |8 L) O/ m7 o4 Y[color=rgba(0, 0, 0, 0.74902)]文章目录

8 |- W' t3 ?1 s, b' D% M
• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  3 ^; O5 v+ H/ R% c( e6 D) B2 g' H( L
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

5 B0 _+ C' A( h
一、 栈与队列的定义
4 c8 b, d; A- v. U5 }* z5 E栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。

; Y7 j; S8 g2 l5 u( m7 Y' ^　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
7 n4 A0 H) ]- z2 |" A

( [  c; r1 v3 B/ q' K
二、 用数组实现栈1、栈的接口定义
  v/ N! }  ~5 o' `4 I3 v1 _: M4 Y8 Y/**
* 定义栈的接口
*
* @Author zhuhuix
! m* Y; G$ o  X+ {$ @, C+ |& c * @date 2020-05-01
*/
8 Q+ E, K' L" kpublic interface Stack {
! P3 o0 Y+ M1 |0 y/ e/ C5 {    /**
     * 入栈
, F* r, ~6 }' d1 l* d     * @param object 入栈元素
     */
    void push(Object object);
7 b* }0 Y) D6 t  V) P2 W
    /**
     * 出栈
     * @return 出栈元素
2 p* i* R/ h5 a1 N     */
    Object pop();
  X# M8 B1 B6 ?% k. ?) m2 J
    /**
. ^& [1 |7 ~" [+ N; L9 V     *  获取元素个数
     * @return 元素个数
, ~$ R) u' v/ n2 E- T2 b  N; e4 Y4 P     */
    int getElementCount();
. B( C$ M4 x+ q& k( g
9 i' V1 U3 Y4 D' }# U    /**
" u. J4 M5 x( s8 B3 ~+ s5 l     * 遍历栈的元素
; t+ _/ W( p6 Y% I& j- ]     */
8 X* `, m, A5 s) X8 G( l8 x, A7 B    void traverse();
  i& h% e" P) a7 j: G/ h6 ]2 K
}
' T$ w( h0 {9 O& x. L9 Q5 z! R2、栈的接口实现
2 H1 s) V3 t5 Q9 {6 W' V/ Q/**
* 栈的接口实现
. z4 {" A* Q- m" ?5 ` *
* @author zhuhuix
* @date 2020-05-01
*/
public class StackImpl implements Stack {
5 ?2 x! A8 Q# z. j4 R# O       
    protected Object[] element;
( O) H- ~" x9 P' W( B
4 }) l& D& U- E, Z/ A    protected int elementCount;

6 b5 V, _- h- e9 t0 r& v    private int defaultSize = 16;
* e# x+ y9 E. S% s
& M7 @, B! G; B! \1 E: m1 t; @    private int maxSize;

" z7 H  u  q8 \( A  n7 V. L    StackImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
    }
7 ?* N: i# s- H. N' K
$ [7 R0 z6 g8 g- K3 o# m    StackImpl(int size) {
        element = new Object[size];
        maxSize = size;
    }
; C6 U2 C: B6 g- ?" @& E1 v! P! @( p- b
+ o8 m! u/ e% O$ S( [3 R3 [    @Override
    public void push(Object object) {
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
, b1 C7 H5 p* f            element = Arrays.copyOf(element, elementCount + defaultSize);
9 _" }3 r/ s! D3 H! Q) R  t- w        }
        element[elementCount++] = object;
5 u! R1 c% V( r! o4 y. X# D1 ~
3 V7 w; u: e% E' X) b5 y    }
* P7 N# ]! r1 q/ Y; Y0 o0 o        // 本代码未实现数组的自动缩小，具体方法可参考JDK
! ?  l" ?6 b% c2 i    @Override
+ r, r2 I! Q, U  K9 P% h    public Object pop() {
8 M! W$ [! j! ^, ~        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
        element[elementCount] = null;
        return object;
1 Y& Y4 @9 D  @$ o0 E    }

    @Override
    public int getElementCount() {
        return elementCount;
    }

    @Override
    public void traverse() {
- z& m+ C# ]# |0 `; [. U; l        for (int i = 0; i < elementCount; i++) {
1 m) D( [! A3 ]/ Y1 h            System.out.print(element + ",");
        }
1 K, P' e2 ]/ H8 c        System.out.println();
0 ^' f4 }/ e: Z7 v    }
$ }! }- f: g$ |5 L; a* g3 z}
2 S6 M6 X, E* S. t8 |3 {3、栈的测试
public class StackTest {
    public static void main(String[] args) {
        Stack stack = new StackImpl();
. M' R- B) F7 R/ a( z
        //第一次入栈:压入1-15
        for (int i = 0; i < 16; i++) {
' u- E  a6 h# c            stack.push(i);
        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();

* C& ~# G" Q$ L# J5 q        //第二次入栈:压入16-31
! u( m, K7 c1 \3 n% M, a2 a% S        for (int i = 16; i < 32; i++) {
) I# X; _: C' L. P4 \$ {            stack.push(i);
        }
9 m/ N% z2 w. ?9 b0 |! T        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
) r) [3 Q9 d% c7 u0 D        stack.traverse();

        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
! P$ r" ^2 E4 T6 `        stack.traverse();
0 E" e( i2 u# R) p& ], X
! c3 Y2 V  _. Y! p* k/ T$ z: z        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
2 ~6 j6 Q5 {  e% x  F            stack.pop();
2 s- O# A9 q) ?5 p6 U# t8 V/ @        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //栈中无元素，出栈报错
7 w: O7 O8 \# w2 e3 n        stack.pop();

" o1 c& i: t% C+ u" v- l4 K. t    }
}
$ a3 L0 k# d) U7 u7 D8 `% b2 w
7 s+ S! h# F8 |9 X& \

0 u' ^$ @6 J7 a! [* E/ h
: \5 B5 |5 J8 a三、 用数组实现队列1、队列的接口定义
0 ]# O- H. k9 r8 q2 q+ o  G- Q  ~/**
* 定义队列的接口
, i9 E1 ^1 f- M% V *
5 o4 `+ A, {; G * @author zhuhuix
5 O0 d) T0 Y8 E. L4 z * @date 2020-05-01
4 ?! v; F) C! [ */
public interface Queue {

    /**
8 M* u' d, b2 W% d" |/ ]/ p8 K     * 获取队列大小
7 [: N& E1 C$ D* |  Z* M. d     * @return 队列大小
     */
! S+ ?, O- A; E9 L9 O) t    int getMaxSize();
, ~: D  F5 y% s5 n. M) _
4 s" P- w; X  g- n! _    /**
     * 入队
     * @param object 入队元素
. y2 e# n5 n; w+ N; U6 g3 d1 R     */
5 h+ l* o. H/ H0 v+ J* d0 V- N    void push(Object object);

2 E; b8 u8 ]+ E9 ?$ c    /**
  J5 a7 B; p4 U% u. {2 U     * 出队
  i0 ~0 {" H" X4 d/ T, P( ^3 P     * @return 出栈元素
     */
+ u! a  L2 s/ K' i0 @: b    Object pull();
8 }3 Z8 [# E" H9 u$ z/ I. U
5 |. G( `/ K  V3 h2 w    /**
     *  获取元素个数
# D" \; R" E# {' K0 _5 p/ [     * @return 元素个数
$ [; N! [: c+ S5 C: I- w* x7 N     */
5 `2 v- ^9 w% }2 C+ c    int getElementCount();
7 h9 j, {# p5 x( b' y
    /**
     *  获取队头元素
+ T$ x( r2 O# y" i$ d     * @return 队头元素
     */
8 k! ?! D. [4 i2 W1 q7 \6 R% ]    Object getFront();
7 r7 J4 k$ c; r
    /**
( ~. ?7 j/ `/ y  c; }2 {     *  获取队尾元素
     * @return 队尾元素
- l. A7 D% t- n& e) u     */
    Object getRear();
/ N6 \% H9 }- l6 ]
* }( t& d1 f5 R! D    /**
     * 遍历队列的元素
     */
    void traverse();
( k. |7 t# R& s% l3 G}
- m$ ]+ r2 k! v; M6 Q; Y2 \, B2、队列的接口实现
! j1 ^* N7 q  g1 E5 T3 q6 l/**
) z4 R& }. F9 E5 b' u! G; l6 M * 队列的接口实现
% \+ r2 [3 B# D: |( ? *
* @author zhuhuix
* @date 2020-05-01
& J& K. O- S% H/ s6 E1 [6 e! M */
public class QueueImpl implements Queue {

& A* F# K! O8 V% L! [( ~5 q# I5 u    protected Object[] element;

    protected int elementCount;
7 }( D3 `: Q+ t" w, F
( C( M" f8 R1 s8 o" o    //队头
    private int front;

( p; f8 @3 e) T; L0 {3 f    //队尾
    private int rear;
. t4 l  x* m7 @
    private int defaultSize = 16;
% u+ O" ]% O$ H$ \; ]6 n
- u- F& R, X! ?/ n0 z& k+ g* O7 t    private int maxSize;
& D' [4 f; B+ _7 V* J- [
4 v$ h5 @- L$ w    QueueImpl() {
        element = new Object[defaultSize];
4 O. V% q/ s; K# [& I2 t2 z        maxSize = defaultSize;
        front = 0;
  C/ R' Q* F- c- j1 t        rear = -1;
    }

, E8 T; W, O0 s, `) B    QueueImpl(int size) {
        element = new Object[size];
8 H& e' A3 D; J9 p0 U# Q3 U+ l        maxSize = size;
        front = 0;
8 @! N4 T+ z9 G" J4 Y  E        rear = -1;
2 V; M5 c2 p2 C0 @: g* b3 |9 h    }
: K( b( L6 O3 T( K
+ U/ d# r& P' X    @Override
7 e% S# L+ A" p" G2 ~    public int getMaxSize() {
7 z4 w4 b" u2 f* _7 N        return maxSize;
1 L5 O+ d: H+ ^  ?# m' J9 x6 c8 y    }

    @Override
3 j# ^5 B! U: P7 v& [8 q+ h    public void push(Object object) {
4 m& A7 s8 U6 R3 K  s8 I1 c        //如果元素个数已经达到数组的最大个数，则进行扩容
# \) M1 S& u. b/ ]        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
/ k: t- d2 R2 n6 u8 M$ H, m        }
3 |! l, L3 T0 A3 F1 A( O        element[++rear] = object;
& P& ~: V" [2 T        if (rear == element.length) {
% [0 C5 k+ i3 H0 i% o# B            rear = -1;
* N; `+ b/ u. ?* h  f        }
        elementCount++;
( f3 @' o! Q# X! r    }
8 o3 B0 V2 R% Z+ T- s4 u' a/ Q' ^5 T
    @Override
0 I& f7 n& |- \3 w! f    public Object pull() {
3 ^% }8 Z& G) {, `        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
( h; w7 s4 A- `# b        Object object = element[front];
        element[front] = null;
        front++;
$ e+ p9 _; w0 ]3 l0 Y( d        elementCount--;
* o+ W( f, t( l# @9 O+ l/ u        //队列清空，队头队尾恢复初始值
2 p' p4 w8 O) P1 Q7 P        if (elementCount == 0) {
) J/ x: x9 k& W5 Q9 ]1 U$ z" M            front = 0;
            rear = -1;
        }
        return object;
    }
' V: T: o' H% B4 f; k% [
    @Override
+ m- K# J3 ]+ h; e    public int getElementCount() {
        return elementCount;
    }
8 A1 j! Q% A) c. S8 Q% f
: I8 @) d' e; ~) S' J5 h4 F    @Override
    public Object getFront() {
8 n' ?" }3 @7 D        if (elementCount == 0) {
9 K; m  T, t5 a7 {, e            System.out.print("队头无元素");
  E& A0 H* ~4 M8 S1 @$ D3 u            return null;
- \& _: w! o( |4 u" ?        }
% n) H( I/ v- j        return element[front];
: j# @9 x" T& z* r3 y    }
, ^& a$ t; A- V
    @Override
    public Object getRear() {
        if (elementCount == 0) {
            System.out.print("队尾无元素");
& h0 X2 f8 j3 g. C, \0 ?  K            return null;
, N# {' H+ n! }: j, c9 ?3 h& R        }
        return element[rear];
3 F. ~* ^5 ^2 @0 t  \2 m- h    }
5 k) x' c& G' l( v' F1 N3 R9 |3 K
    @Override
    public void traverse() {
' Z+ v& D: j' J" d# V& R" O        if (elementCount == 0) {
            return;
( o" L9 W' G% ~) e2 h        }
        for (int i = front; i <= rear; i++) {
0 O: v( k! B  d- a) w, g$ u1 y            System.out.print(element + ",");
2 |8 F" R5 G+ W$ Q! o/ f        }
% N3 l3 Q8 U1 ?+ Y+ v, F- O1 k        System.out.println();
    }
}


* S; p/ I- o, [: y0 f9 N! T3、队列的测试
3 _, B( w! {: @. z4 e/ V+ F' @2 Lpublic class QueueTest {
; S% s. J! T* W4 Z, F. B4 E    public static void main(String[] args) {
        Queue queue = new QueueImpl();

( I) P& b- ?( [        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

" O" }* K% @9 z2 W9 v0 \        //第一次入队列:压入1-15
) I. L. V3 K' q( \        for (int i = 0; i < 16; i++) {
$ X7 N* l0 b1 Z8 m% J) @            queue.push(i);
- A+ w" B. T! s' g8 f3 ]; V  F        }
, \8 o* F. e' g9 c+ q, m. w+ E        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
  K/ E$ F9 \7 W1 q7 N$ Z! P4 v        queue.traverse();
4 W" N1 F- M' {) y" B1 j3 b7 V, K+ W        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());

        //第一次出队:取出0-15
- X  I) i1 v. v+ f+ f, a9 T        for (int i = 0; i < 16; i++) {
( t/ C' V6 ]$ G1 A% O  |            queue.pull();
! l: _* W7 g* H9 C+ x) F* R* l3 ]0 J        }
5 s& o$ \: j5 c9 c6 w9 S5 m7 c        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
5 ^5 t  j2 b) `4 u: n        queue.traverse();
3 L7 ^1 X- K. _/ X) O4 o9 o4 O        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
: X2 }/ K* g" j) o1 M

: u3 ~" O4 D" h$ j        //第二次入队列:压入16，31
6 _3 N' k8 r4 K  X9 w$ T        for (int i = 16; i < 32; i++) {
0 B5 ~, c# z9 {# {5 n! p8 I            queue.push(i);
        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();


+ R3 `) q  n; n! x) M        //第二次出队:取出16-31
2 T  b2 O/ l) c! m5 V2 d6 T& E0 H        for (int i = 0; i < 16; i++) {
0 c9 E$ _5 T; k# \+ S# |7 w            queue.pull();
        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
$ [0 ^5 T* w7 @7 ]4 ~        queue.traverse();

        //空队列出队报错
% g3 Z0 g; G  _2 l4 i. D1 b        queue.pull();

    }
}



5 G7 d8 J) A2 @



, x. {" W, v) ^( ^9 ~3 _

7 |$ l, P- O! W. y; U8 W/ k. P$ E


! K6 ^/ h$ Z2 i! c2 Q
' |2 W" w+ s' S4 |  l

————————————————
9 d% u9 ^7 j9 |" v' q版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785


, H  p# l4 a8 S% L, Q$ S* p