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

杨利霞

数据结构——栈(Stack)与队列(Queue)的手写实例
* r! o/ Q6 y: d1 ~3 [
[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  " q) E& s# l& ?; Z
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    % x7 Q9 w/ p! f

2 I/ x' x$ D3 ~2 T4 S1 b/ S
  J2 T4 Q+ g$ V/ j" ~" B7 ^; h一、 栈与队列的定义
* e$ q. U. C$ O4 c; P$ w; V栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。

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

9 p6 e) k5 `' y

0 p5 Z6 I5 c/ v$ v' Y; D二、 用数组实现栈1、栈的接口定义
0 r, m3 V# N, t$ i4 S8 l( n/**
* 定义栈的接口
*
. V. T+ H0 z1 k' v$ S$ s% a+ K* D * @Author zhuhuix
; y/ l6 [. s$ G, [( |( F * @date 2020-05-01
*/
( T# O. e9 ^# M2 s; a& vpublic interface Stack {
$ h9 L" e5 M( u( L, {% `    /**
     * 入栈
     * @param object 入栈元素
7 `+ x/ e2 w$ Q. o     */
! }( W+ H0 s, M) Y# m& v* ^    void push(Object object);
$ m+ J$ N1 ]7 x8 p3 ]4 g% Z3 K
1 K1 f9 p3 s  _+ z! K    /**
     * 出栈
     * @return 出栈元素
! y4 C' t" K) s3 x* h& o, n) _     */
- t$ Q& |( e" S6 O; Q- A' E' p    Object pop();
  k( l! _8 U+ T  s
1 A. q1 l+ c7 l; f: G    /**
     *  获取元素个数
     * @return 元素个数
     */
    int getElementCount();
* h/ E0 W/ X- _3 H$ J
    /**
6 K) E5 u" q* W; [  m     * 遍历栈的元素
# C3 `4 c/ r9 X: y4 l     */
4 j2 B( Q. J, Z4 C! e    void traverse();
' R1 W; R( \7 f
}
; i1 r4 G; c) E, x' W' R1 q4 N2、栈的接口实现
/**
* 栈的接口实现
*
. C# J5 f! e- z/ T! V/ o * @author zhuhuix
* @date 2020-05-01
. E( c* ]) h) E! k' B+ Z */
% p) v3 X3 u* d' H" @public class StackImpl implements Stack {
       
- S( l5 B3 D" W6 ^; V  l    protected Object[] element;

9 }- @( r1 b6 Y% a2 {    protected int elementCount;

- K# {+ |/ e" v* Q$ ?/ h    private int defaultSize = 16;

; S4 J5 M3 A9 i9 ^3 c1 I    private int maxSize;

    StackImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
: C) T  |8 q% {& F9 u) N& \    }

    StackImpl(int size) {
        element = new Object[size];
        maxSize = size;
    }
3 e; I" ^, n9 u, n' {6 r( _
( W- V$ w( P: I5 h7 ^8 O    @Override
, A6 S, e: g& A2 A' }& u/ ]4 h1 i    public void push(Object object) {
/ g, S, \+ r/ J4 g        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
        element[elementCount++] = object;

, y" k" q0 n4 E0 |6 l! P    }
& w  ~9 t" h0 [$ R' @% B. h        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
) ]# m5 ]' B6 i+ `$ z/ ~) {' v    public Object pop() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
3 }3 D- V0 M6 n9 z( U& V% ~        element[elementCount] = null;
) O7 e9 _$ O# ?; o* p& E        return object;
/ J. T5 w' z0 D    }

' F+ f) w( Q7 Z% C5 j    @Override
    public int getElementCount() {
        return elementCount;
# K, d4 l  i" q+ V8 J& U8 q# t  g    }

/ k% D* K5 w1 v/ o4 {    @Override
    public void traverse() {
9 M3 E2 C! f3 f5 T9 y- A        for (int i = 0; i < elementCount; i++) {
2 [& e; _0 a3 Q' n            System.out.print(element + ",");
        }
        System.out.println();
    }
}
5 i/ B6 Y2 m  k" d3 V" z2 }, T3、栈的测试
public class StackTest {
    public static void main(String[] args) {
        Stack stack = new StackImpl();
- e9 n/ U, O, p3 {# Q
        //第一次入栈:压入1-15
        for (int i = 0; i < 16; i++) {
            stack.push(i);
& C1 o' ]& u  S7 j6 L' F# i        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
$ t5 w5 U& f% o        stack.traverse();
) r$ p5 _! Y+ t& K
        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
            stack.push(i);
; o$ p: \9 ~$ Z. f" o        }
        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
) U8 o$ _% M9 U9 M* m& W            stack.pop();
        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
; Z! o0 N2 n9 K- _9 `8 b9 q4 R7 E        stack.traverse();

        //第二次出栈:取出15-0
+ w) G% F5 P4 z4 N9 Z7 y" h        for (int i = 0; i < 16; i++) {
            stack.pop();
, e/ e" v; r/ j, k# ?0 T; M        }
* n8 }( y$ x/ Q) q& x& R2 M        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
8 U  v* ^6 L2 K1 b        stack.traverse();

2 O/ n& V7 v4 P5 U' k0 ]  W        //栈中无元素，出栈报错
        stack.pop();

/ f2 X6 w9 _7 m' w    }
$ u6 Y" X3 u) s9 u# B7 J' w}

- G6 J. B. R% H1 ~4 e


- b" l. D3 W& F* Q8 f% u+ L三、 用数组实现队列1、队列的接口定义
/**
) ?  u' T& i# _: r/ k- t( Q. m( C * 定义队列的接口
6 ?! ]- d7 H+ I1 F- Y, O- ?: v6 } *
* @author zhuhuix
6 F* |2 V/ _6 ?( j6 {; {7 ^ * @date 2020-05-01
5 _. f; I0 z! M" ~9 R( P* ] */
1 V) ]  S& q3 q) b) P. \public interface Queue {
/ f9 K# B9 C2 I. C
$ K" J- d$ m$ x7 s0 d2 w" R# l    /**
: M& Z" m$ [9 M     * 获取队列大小
     * @return 队列大小
     */
  l" M! x/ S: `* s. A, Q    int getMaxSize();

8 W7 K1 n) S. @5 u4 L2 A    /**
     * 入队
. i7 h" T( s+ U5 W) s9 o1 w" @     * @param object 入队元素
     */
, c0 r$ |4 j" n2 V& _( C6 r6 \    void push(Object object);

/ |( X1 W* t, u8 W    /**
7 n3 G2 n+ @# _) z     * 出队
# x& ?* f( p7 ?$ t) |$ ]     * @return 出栈元素
/ ^+ \1 J) ~' }     */
/ {" L* I' y  d/ h' Q$ c6 Y. @    Object pull();
- g" s) c/ m& c; x1 x/ f# q" t+ t
    /**
+ h7 f+ A) ^8 r     *  获取元素个数
     * @return 元素个数
     */
    int getElementCount();

    /**
0 R7 l. N9 V( Q* g; {/ [% T     *  获取队头元素
! o9 q+ J0 j' x7 G4 ^5 l; {# k     * @return 队头元素
' f/ C4 y1 Z, s+ b' V     */
& P: M4 N& ?/ l' _7 |& k; l    Object getFront();

    /**
2 U; \- S1 L6 o( a     *  获取队尾元素
     * @return 队尾元素
     */
    Object getRear();

0 c* l* ^9 l7 Q6 F    /**
- g8 X* A$ U  `1 p' T     * 遍历队列的元素
: s( S! d: r1 |2 z     */
    void traverse();
}
2、队列的接口实现
/**
; q9 e; a- D9 ~( i5 u( j) r * 队列的接口实现
% }2 B2 b. Y5 [1 Z" f6 J4 [5 g *
* @author zhuhuix
* @date 2020-05-01
, y, a; _: ?3 B( ^' _) i */
public class QueueImpl implements Queue {

5 [, S. t# G' g$ S  l. B  T" S    protected Object[] element;
; ~* ]3 V5 i4 N* I2 o
    protected int elementCount;
+ X4 x; \9 x* f3 U3 X7 l+ V: y
    //队头
- D- m$ Q+ {- T6 D& D. K    private int front;

    //队尾
    private int rear;

    private int defaultSize = 16;

    private int maxSize;

" i* o6 u2 V4 r    QueueImpl() {
        element = new Object[defaultSize];
( j5 b+ ]" Q: {; Y1 q        maxSize = defaultSize;
        front = 0;
( B; O& Y) Z+ `) I& ^- b! M        rear = -1;
    }

    QueueImpl(int size) {
        element = new Object[size];
! w* D6 K$ `* a1 e        maxSize = size;
* F# \. t7 y9 {9 ?. U4 |        front = 0;
        rear = -1;
    }
" a% E# x0 O( H! _
( ^8 A4 C& r8 G    @Override
, M$ a. j' }4 ?) K  `& \2 Q8 G    public int getMaxSize() {
* R$ Z& Q/ u2 E. S" V) Y+ q8 X7 P        return maxSize;
    }
8 C) L  y8 y! G
! c: o. a' Z" @" ]    @Override
    public void push(Object object) {
4 V$ ~+ F" R$ q        //如果元素个数已经达到数组的最大个数，则进行扩容
& O0 |7 i4 A' U3 d2 a        if (elementCount == maxSize) {
+ v$ Q6 }. U* @7 x3 r            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
        }
" L. c% d8 l: }2 T5 f        element[++rear] = object;
: O, D3 K# J6 A. R8 s        if (rear == element.length) {
, \- j0 s  X4 A) s7 _3 O: i            rear = -1;
        }
- v. K; z  E: K. \" H        elementCount++;
. X2 G3 s$ s% _$ `( M9 x! I    }
% \, y* \8 [6 q
% }9 B( F, Q) {8 Y' j0 V    @Override
' P) s3 Y% z; {( ?8 S6 d4 L6 E: {; p    public Object pull() {
: L8 r5 w8 v# h1 c- }6 M3 _% m        if (elementCount == 0) {
8 _- C! P) Y& `$ ?# t3 }4 I5 M            throw new ArrayIndexOutOfBoundsException("队列中无元素");
5 r/ Z0 P1 ?6 ]) i  b8 J        }
0 j/ m1 x; w/ h$ ]! H4 o+ B; W        Object object = element[front];
9 t* ]8 t$ B5 N9 b        element[front] = null;
2 S2 k; d3 y" ]6 j, ^4 w  D4 a$ T        front++;
9 t4 h+ S$ D/ D) ^% H+ D  v        elementCount--;
' `  N8 N  j7 r, e2 E: P+ S        //队列清空，队头队尾恢复初始值
        if (elementCount == 0) {
            front = 0;
6 _( X! f8 k  W: ~            rear = -1;
        }
! Y8 F* B  h/ c& m3 V3 x: l2 q        return object;
    }
" D* H+ O  e8 T- @9 C- N
    @Override
! _7 z0 L: h# Y; r" N' ]3 |: k) a4 i    public int getElementCount() {
! L; q9 `4 I$ r- h+ q$ _2 |        return elementCount;
    }
, v% n3 j" W% w) K8 W) A- U* g
    @Override
, W" }. k* t! C* V  _    public Object getFront() {
        if (elementCount == 0) {
' }: Y1 F  }( o' s            System.out.print("队头无元素");
            return null;
+ x. C0 I0 Y$ [        }
) Q. z: b: t! K6 t, E# [/ {0 m        return element[front];
7 D2 Z% |( r, }2 p    }

* \0 A, }) H3 ?5 i    @Override
" R) \0 o' v& q* t- ^. @    public Object getRear() {
1 H0 ~( ?: V; F; ^2 V( _6 J        if (elementCount == 0) {
            System.out.print("队尾无元素");
            return null;
. y" K. b4 A% }. _2 l/ e. B        }
        return element[rear];
    }

2 M2 d! L/ A7 |0 K5 P9 Z    @Override
    public void traverse() {
        if (elementCount == 0) {
% i: T1 C$ y9 B6 t8 e            return;
9 e  W' |6 V5 V4 L        }
        for (int i = front; i <= rear; i++) {
; Q: [! t/ f' F. S5 N            System.out.print(element + ",");
        }
        System.out.println();
, a( G) d" v: r( V    }
, H3 u: G' Q" a5 I9 Y}

% {8 j6 D. S0 b8 l
3、队列的测试
" I+ S2 n! i/ G( i, T4 f' O% \5 ?public class QueueTest {
" t) _' ~- d6 z8 ^6 W4 r$ V/ M; V8 H    public static void main(String[] args) {
" ^) Z4 x0 U7 B: q: s' B1 K( k7 n        Queue queue = new QueueImpl();
  X" r7 C2 c% W" W6 K$ ~
        //获取队列大小
        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
  K% p/ K& q4 l
2 u1 x- p. T; D, }        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
+ K: s5 t2 W+ \# k  c4 }            queue.push(i);
        }
1 i$ A( ?1 V. X9 }# i        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
) E( {) U2 Q$ ]  ]4 b+ \5 M
  C6 G6 A5 U9 [6 g! d( z# o' T        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
9 s( m. T$ b4 q# t# r        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());


/ N  z/ b, x/ |$ Y) N) E0 b        //第二次入队列:压入16，31
        for (int i = 16; i < 32; i++) {
! z( u1 w' U7 E! s. z$ ?            queue.push(i);
, O; l' A$ H1 K2 k% \, Z        }
# t5 c9 F' P+ G6 H! z" Y        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
2 H' T! W+ W5 _, f8 [        queue.traverse();
% Q5 `( I/ M5 l' Y* K
" X+ T! _, n- n8 @
0 s4 i9 G/ e' o5 V& V9 o$ Z        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
; e) K2 |/ i+ ^3 U/ k            queue.pull();
        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
( j; L- l, H9 W3 m) x3 d" Q
        //空队列出队报错
/ H3 b+ O$ Y- I+ J3 z) w        queue.pull();

/ N1 o; j+ r; P& s' v    }
}

- q3 d% u8 h( Y
% ?* j. k8 J5 k7 \# W, C, z2 |
* X9 C  U% C# T% o$ V' k
3 O# a& v6 g9 x
( ?6 D& O. F  L" i
8 q5 v5 f! `  j" n% @+ f3 p

! j; c- r  \" S7 g, Q. N9 \" T6 s
% V! E/ E7 m) b: }2 ?


9 K8 ]' ^8 N: f
: l1 w  n7 U1 A0 h8 B& H$ f

————————————————
版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
& S9 n' D1 V9 @8 l

: i& Z4 `- I, r# _% N4 `7 P