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

杨利霞

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

[color=rgba(0, 0, 0, 0.74902)]文章目录

• 一、 栈与队列的定义
• 二、 用数组实现栈
  
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    0 x* W8 H% O( h+ t

4 y' |+ |' \2 B7 e9 E5 `$ }
一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
* z/ R1 J. P0 I4 C
  }- s+ N6 ^( p　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。

; ~% f' }5 r$ r

# S* E7 q& x) `. n' ^. U1 f二、 用数组实现栈1、栈的接口定义
/**
- q$ N: }7 V$ e# j% ^1 r * 定义栈的接口
*
* @Author zhuhuix
/ Z0 t/ r& J1 Z! V: n0 l& i * @date 2020-05-01
5 |: L$ B7 ~* \/ ?. p+ Y, E */
: l/ n1 L; v/ Y% ]6 Z4 L( q, [public interface Stack {
/ p8 l" a- Q1 N0 }! @    /**
     * 入栈
     * @param object 入栈元素
, ^( Z( ]5 P5 R6 G     */
/ J  Y" W" O# Q6 a* e    void push(Object object);

    /**
     * 出栈
( |2 o7 R9 V  B0 A. J) u/ r8 d     * @return 出栈元素
1 E* w9 o+ i+ ~( ?% `     */
1 H" ~8 j" |, }  ^    Object pop();

    /**
1 q. Q) c- g; o/ c     *  获取元素个数
0 q2 `  l$ D. D9 f5 j2 f$ B     * @return 元素个数
     */
    int getElementCount();

    /**
     * 遍历栈的元素
! N  m1 N. `3 c. L( e     */
    void traverse();

}
7 m- Z, M3 T7 }+ M2、栈的接口实现
/**
! i3 B1 E4 f3 A, s8 y! B * 栈的接口实现
. F5 e* k) p/ k# v# T+ q& a *
* @author zhuhuix
' w* c7 g1 q$ A8 \+ A. F * @date 2020-05-01
*/
public class StackImpl implements Stack {
       
    protected Object[] element;
: ^- H2 B1 D/ u* R4 t8 }7 A
    protected int elementCount;
; M% Z% ^7 i* w' n" b
! E$ o8 |0 K, C) h  q6 t. y* k    private int defaultSize = 16;
3 H. g! s; M. E  K) u* E, x
    private int maxSize;

    StackImpl() {
        element = new Object[defaultSize];
) l" Q/ o4 t) K0 V+ }        maxSize = defaultSize;
/ l" K' D$ K/ f% ~. Z! }    }
0 y3 m" ^6 @- k+ w
    StackImpl(int size) {
# i9 j- H& {& H% v        element = new Object[size];
        maxSize = size;
    }
; H$ S, Z4 Y8 u1 K4 K0 f% V
    @Override
    public void push(Object object) {
4 }- T# ]# u' |        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
: \' p4 v" G0 c. B7 ], r6 M            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
        element[elementCount++] = object;

6 G4 e$ b( G5 ~    }
7 H7 ^' Z  f* Y, R/ v. D- j1 L        // 本代码未实现数组的自动缩小，具体方法可参考JDK
, V. y7 I1 p1 G+ o! A    @Override
; |9 s' S' c5 M8 c2 F9 q    public Object pop() {
        if (elementCount == 0) {
# J- }% T; J3 t            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
. {8 {: {1 a8 @  r        Object object = element[--elementCount];
        element[elementCount] = null;
        return object;
    }

: s# q/ o4 \0 b7 f0 Z    @Override
    public int getElementCount() {
# w% W) |- r7 w+ a, i        return elementCount;
3 X4 d' V$ T. `* p' M    }

* m9 ~2 O" h: S/ m; L% m  r    @Override
    public void traverse() {
        for (int i = 0; i < elementCount; i++) {
            System.out.print(element + ",");
  d8 e) V8 o. ?+ M1 }* r. G( f        }
        System.out.println();
" Z+ A& _! D" ^" x/ y# @7 F% ?    }
}
3、栈的测试
4 Q; W/ l) C8 Z: K! ?  ~2 ^public class StackTest {
: l. g1 t0 r' w) u, {    public static void main(String[] args) {
/ S4 s" p; a/ s: y        Stack stack = new StackImpl();
0 l6 J. n3 i! c* m: C+ E
        //第一次入栈:压入1-15
2 {+ C" e7 X; w7 R1 @+ `, u        for (int i = 0; i < 16; i++) {
8 C+ p" k9 l% e7 K4 y            stack.push(i);
        }
2 O7 q. k" s1 P9 j8 m. h- m        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
        stack.traverse();
4 S' [9 w& x' ]6 u, h' t) }. q& \
2 z, |( F+ P+ Q        //第二次入栈:压入16-31
        for (int i = 16; i < 32; i++) {
" W2 |5 `, r3 N( {! k' r/ d            stack.push(i);
! j6 t. m* K: e5 A% X        }
/ V# ?% K: e# A+ S: c        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
' z# G5 r! ^& R        stack.traverse();
8 d2 J8 k6 ]0 ]0 g
        //第二次出栈:取出15-0
        for (int i = 0; i < 16; i++) {
1 }5 }" f2 f/ q" f# V; r            stack.pop();
        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
0 W; Q) {: D0 D7 w. a$ U
        //栈中无元素，出栈报错
        stack.pop();
0 H; L3 I! h( N/ r
    }
+ w- o6 l0 I# o! j% v1 q1 N% f}

3 O; y" s$ V7 A9 Y/ j
' I/ m% \1 S* |5 y: q

% F2 [" G9 C+ B% e+ T+ I5 K2 T三、 用数组实现队列1、队列的接口定义
/**
* 定义队列的接口
*
* @author zhuhuix
( j4 w+ H, R; @+ i( z/ d. y4 D4 t * @date 2020-05-01
) y1 ~; i, m* ]& Z7 R */
% H. B; r0 t, Cpublic interface Queue {

+ F: c2 c) w5 A    /**
) L$ T3 |. r0 t# h# X9 s     * 获取队列大小
     * @return 队列大小
     */
( o) t6 i4 h. B    int getMaxSize();
& U9 j. O+ \' {/ }8 |
    /**
     * 入队
     * @param object 入队元素
     */
" ]( Z* Y3 {7 _* R& R& w) I0 }    void push(Object object);
8 J; p$ P2 ]  s% s7 n( F
    /**
     * 出队
     * @return 出栈元素
     */
8 @/ @3 q8 T% s* V& C2 d: F    Object pull();

: d9 L  l, U) X- ?    /**
; V$ a) u6 ^+ Q& O# ^( B1 D     *  获取元素个数
$ U. B$ P: ~8 ]# }9 c9 W     * @return 元素个数
4 U: }! z$ ?6 K8 _- Y     */
" }7 E! z1 d. W- H/ b    int getElementCount();

2 n% W, w- j+ b! O1 |    /**
4 y$ y( ^7 J- g0 M1 A     *  获取队头元素
     * @return 队头元素
     */
    Object getFront();

    /**
/ `7 i! ~* i0 Q! Y     *  获取队尾元素
4 J2 h$ [1 H5 O7 }% ^6 R     * @return 队尾元素
* [5 e2 p# u7 p3 z     */
& @( j, [+ a# ?& E    Object getRear();
+ V, b1 U# c; }3 I
& m7 ]+ M1 w  d. g! s0 ~    /**
, I' y* |% |" h6 \0 e     * 遍历队列的元素
     */
# b( L- M( L0 ]  h    void traverse();
}
# Z- J' j5 N1 G, H7 I! {  E2、队列的接口实现
/**
9 C# H! w1 K) K/ T. r' @ * 队列的接口实现
8 b8 Y- t' B9 J! u/ s- B *
* @author zhuhuix
* @date 2020-05-01
*/
public class QueueImpl implements Queue {
; y" z2 L. x0 b
- W% F/ ]; X# w9 V    protected Object[] element;

) m# _5 U5 B9 E  {/ r    protected int elementCount;
( T7 M) A7 }2 z( y
    //队头
    private int front;

. J2 g, {, u% t5 {9 n3 Y/ y    //队尾
$ m  U" M8 P( a" l$ J" w    private int rear;

9 G7 _+ t( E- u$ N7 d! _, P# I    private int defaultSize = 16;
- N6 ~/ `0 s& z0 q, I$ W) y
    private int maxSize;

, Z. Y$ f2 e( H$ j9 \3 |    QueueImpl() {
- d6 W- h- M1 w/ o# d) ?        element = new Object[defaultSize];
7 x) ~, }( y1 |& i        maxSize = defaultSize;
        front = 0;
. d1 }2 B( E5 A! j4 Q* a0 G8 ~2 |        rear = -1;
    }

) L1 J0 ?6 I; s' T) B    QueueImpl(int size) {
        element = new Object[size];
# L/ Q5 z' [  ?$ _        maxSize = size;
        front = 0;
/ a: P# k5 B( D* C) e+ x        rear = -1;
2 Q; r% n& M3 t; S! }1 ?    }
8 h( o; E, x7 ?5 x! B
+ @# q- o( i& w* ^4 d% Z7 {    @Override
    public int getMaxSize() {
7 U- x) b4 D! O! M' ~# p9 H        return maxSize;
( i0 F( R0 f( T: i1 \; f    }
5 p6 [4 q! Y" f6 e* e
    @Override
    public void push(Object object) {
. a% [3 m6 ?2 S$ u& M  _5 U        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
, D9 {2 v8 U( Y% h: l( L        }
        element[++rear] = object;
        if (rear == element.length) {
8 K4 K9 }, ]  `4 k- P/ |* Y            rear = -1;
! }% l3 E6 h; p6 y" Y        }
$ c7 L4 y5 {% `0 F        elementCount++;
    }
; d+ R, Q( X- |; M4 L
# b7 [6 C- i) D3 ^    @Override
    public Object pull() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
        }
! y# |) {, e5 f2 w4 l        Object object = element[front];
        element[front] = null;
        front++;
        elementCount--;
: U/ Y8 l" O: o! {) a& Z0 r( {        //队列清空，队头队尾恢复初始值
2 k: d5 x+ D& T- x5 L; F        if (elementCount == 0) {
            front = 0;
            rear = -1;
        }
        return object;
    }
6 Z* {% C& e  I# N% m" B* Q. b
! h- a, n: a8 L  ^( o" x, m& l) t% s9 L    @Override
4 a. u  L7 G: ]1 @7 i% e7 {  U    public int getElementCount() {
9 a# q1 R$ b0 l5 H. o        return elementCount;
    }
" O. q5 L# f. o0 P' ~2 R
    @Override
: X) k1 t* X( U: o7 u3 b    public Object getFront() {
, O( ?$ l# @7 }# i% b3 Z& t1 j: J        if (elementCount == 0) {
& B1 `2 t  C! G" j1 v            System.out.print("队头无元素");
            return null;
        }
& z  B/ q' [( F# ^% j( o" ~! A        return element[front];
    }
1 P! _9 d8 J0 S5 u8 ]5 G$ N
    @Override
    public Object getRear() {
        if (elementCount == 0) {
4 t( Q/ q0 l4 F& ^7 Y4 M            System.out.print("队尾无元素");
            return null;
        }
        return element[rear];
    }

) Q' G. Y( w7 ]0 n% p9 H1 z    @Override
2 Q/ B4 M) @) E& i# ~4 {- N4 B2 V    public void traverse() {
; q  u# x4 {/ d/ f        if (elementCount == 0) {
            return;
        }
        for (int i = front; i <= rear; i++) {
$ v) ^+ Z8 U" ^. q- I; D            System.out.print(element + ",");
/ Z1 ~. @  a# r3 E) s# l- y        }
7 H: E1 ~' y$ j9 Q  _- J0 x# ]        System.out.println();
1 z) u8 n& z6 p, d2 L: @    }
}

$ [$ d3 E* r! P
4 u  J1 A: S$ Z# H& U  u' N& x4 @3、队列的测试
public class QueueTest {
    public static void main(String[] args) {
, `0 h3 W+ z1 ]  h' i" M) Z7 C' d, [        Queue queue = new QueueImpl();

3 q' d* X4 N0 G/ F        //获取队列大小
2 Y' Z( n+ s3 |- N        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
9 b7 E. _% g! b0 a) ~
        //第一次入队列:压入1-15
        for (int i = 0; i < 16; i++) {
            queue.push(i);
        }
7 f4 y, Q( f$ O  d& X        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
. o2 ^  `1 P* s$ T2 U5 g4 {        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
% o+ @! W' n1 j1 m0 b
/ V" z5 q. w0 R% I- Q        //第一次出队:取出0-15
/ P9 `( X7 d+ }        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
! m' I1 ~+ D4 s' a/ j, b& r- x
- P( J- {& p6 H/ Q5 G+ z
  o7 P2 U2 Y# G& A4 B: w' r        //第二次入队列:压入16，31
- |( F: X- e/ i3 w1 h# D        for (int i = 16; i < 32; i++) {
; r6 |! w: t$ a/ O            queue.push(i);
/ g3 w& R* m! c+ y        }
& e; k0 J. L* z) z. K, g        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
        queue.traverse();
) a; _* B" t; X# e' R

+ W* N0 b) }! `6 S! ^3 O        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
# @$ \' p! t# g! f; q1 Z* Q            queue.pull();
        }
        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
& [( z3 V# ~2 O4 q7 B7 [
5 t5 E; R5 I: F2 P        //空队列出队报错
8 c  E3 L# F* l2 }        queue.pull();
- @/ F. H& r/ n, h& m
    }
. T5 {/ A& E. T7 K, A}

/ `: f$ a% s  c- ?

2 @% T- N9 y5 S( ^" i* @

: U, }# p$ f& k7 s


) N2 d3 @: u% Q) _! {

  x& A: X6 z: [2 m6 m0 t
/ U: @( U, A- x; N' l0 p4 ~) {; B' M

: ?6 K. z2 J; R  \; H  ^9 |/ O

" _4 K+ Q9 [5 f  w————————————————
, v2 f3 \3 U  W; j! b1 v& I. G8 p版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785

7 {. d9 o8 [  s0 [2 [# `7 \
; w  \5 f; L! t