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

杨利霞

' L/ S2 ?: {- M3 P; @5 C数据结构——栈(Stack)与队列(Queue)的手写实例

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

7 V+ D6 k1 u1 e- I  C
• 一、 栈与队列的定义
• 二、 用数组实现栈
  9 r& W6 f8 L" p9 ?
  • 1、栈的接口定义
  • 2、栈的接口实现
  • 3、栈的测试
    
• 三、 用数组实现队列
  
  • 1、队列的接口定义
  • 2、队列的接口实现
  • 3、队列的测试
    

一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
, i0 J; b4 O$ ?8 J& t
( _% c9 ?5 S4 O: w$ R　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
# [3 T5 T* _4 Z$ g8 J1 H6 O


二、 用数组实现栈1、栈的接口定义
/**
* 定义栈的接口
8 w6 i: J/ a; b  R; L0 f* A/ }4 L *
; Z& u2 Z. U9 ?0 j/ `- H * @Author zhuhuix
* @date 2020-05-01
1 d4 I0 u* G7 f# c9 _; [+ [ */
public interface Stack {
, e! R$ W. p$ S7 i, Z7 U& S8 H    /**
3 t% \1 R) G) B5 @: U     * 入栈
4 b/ I+ H# @, u     * @param object 入栈元素
     */
    void push(Object object);

    /**
     * 出栈
     * @return 出栈元素
     */
    Object pop();

    /**
# P- @4 f# f2 y- [2 k) \& m( ~! l2 N     *  获取元素个数
     * @return 元素个数
+ r, K. Y3 B6 h3 D8 p# t3 n     */
( u8 M$ p* E' f; }" ~" u- M    int getElementCount();
$ ~' h1 `2 b4 t1 _6 O  i1 u5 a3 @1 w
    /**
5 d. q9 b  p+ ^     * 遍历栈的元素
! W; C8 G: d/ e* ^2 y. D     */
    void traverse();
) k+ u6 ?2 v4 M" c! u
1 D+ c/ u$ G* s+ G$ M: i( _}
2、栈的接口实现
/**
* 栈的接口实现
# K- C: ^/ ~1 j2 Z *
' D( P  P" e1 n8 R * @author zhuhuix
7 k7 S; n1 |3 p+ L, } * @date 2020-05-01
*/
public class StackImpl implements Stack {
; B  G1 r/ `2 f! ]  M& b( r7 ~: U9 ~       
3 U  O% A6 M+ T5 u( n; R9 X    protected Object[] element;

% Q; D9 ~" L8 \+ I& o" J3 @) f' B    protected int elementCount;
9 B% {$ }# a# W: ^# c: P1 k& s
    private int defaultSize = 16;

    private int maxSize;

1 Z( a1 `3 S5 n8 G0 i    StackImpl() {
        element = new Object[defaultSize];
" l7 h0 ?/ S6 w5 C7 s, X: ?        maxSize = defaultSize;
    }

    StackImpl(int size) {
1 t& v1 ?7 N+ U$ r; x" B6 [0 L        element = new Object[size];
        maxSize = size;
    }
7 w7 u3 Z6 ?; V2 n. R9 O
    @Override
    public void push(Object object) {
2 z$ u- s4 u" L9 w8 x        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
        element[elementCount++] = object;
% [& ]2 v4 \2 [1 v* n
    }
: X" M0 W" W2 K9 j4 L        // 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
    public Object pop() {
        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
, M+ E2 m8 C: |; C" [* a2 f        }
        Object object = element[--elementCount];
        element[elementCount] = null;
% M% G$ H. u; i( ?+ X- A& ]        return object;
5 n, P- b: V* v1 L    }

    @Override
! Y$ Y( R! T! E$ ^- V- H    public int getElementCount() {
        return elementCount;
    }

    @Override
    public void traverse() {
6 F" {% B4 y" b2 ^1 g# u# F        for (int i = 0; i < elementCount; i++) {
8 r8 P7 X- Q, y" k5 }) A" s( \            System.out.print(element + ",");
$ H; [0 K- [0 l2 {3 `0 o        }
        System.out.println();
$ `0 F0 e. {, e0 d9 T    }
$ L4 s$ H) C; Q$ [}
3、栈的测试
' \1 ]) K9 k; v5 \2 y  e* z7 V3 |6 Rpublic class StackTest {
+ m  |6 l! D( c1 \4 M    public static void main(String[] args) {
' F* E1 O$ E! `) }        Stack stack = new StackImpl();

  ~; [5 l' f+ a  e- M# X$ i, J        //第一次入栈:压入1-15
" O8 S" d0 R9 m1 e' d        for (int i = 0; i < 16; i++) {
            stack.push(i);
        }
        System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
6 ]7 L8 p& J) t" k5 X        stack.traverse();

4 X4 i7 Y7 t/ O  t% y) t, f        //第二次入栈:压入16-31
8 J- M- O1 I! e% A# S/ q        for (int i = 16; i < 32; i++) {
. H% I# |% H( Q. F( C            stack.push(i);
        }
4 x" ?* N" Q! w' d) O" j0 C+ s; @        System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();
% n2 i# \7 ^7 u' y
8 C" _: y) S9 }" h( r        //第一次出栈:取出31-16
        for (int i = 0; i < 16; i++) {
  i6 O" u1 |9 b0 w            stack.pop();
3 L2 R, `0 ?; y% i3 Z* Y        }
, o9 h# p+ i  B, {/ B        System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
) ^, R7 O$ Z0 K1 \        stack.traverse();

. X! [) G! v3 k        //第二次出栈:取出15-0
  r8 s3 ?& X# A        for (int i = 0; i < 16; i++) {
            stack.pop();
        }
        System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
        stack.traverse();

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

( `  {+ o7 \% d3 u    }
}
7 S: t" {9 `5 \- P# @

0 f6 }' g$ \  I7 K/ d& E

三、 用数组实现队列1、队列的接口定义
7 V- N( a/ X3 h, n; V/**
* 定义队列的接口
: M) \: F) B, k- T *
/ o$ z/ N. l. D) M, n * @author zhuhuix
4 [3 z' [+ u. A9 m# T, J% n * @date 2020-05-01
7 d4 N2 p, C$ e1 m8 n! F5 T */
public interface Queue {
) H% J( \: T# {3 l& ~
  _7 S2 H& f: f3 O    /**
- z& t3 }+ l9 t& m     * 获取队列大小
     * @return 队列大小
3 d0 i/ S2 f1 N" c4 ]. u     */
    int getMaxSize();
, Q5 v2 T* A4 B* c- ^; K- i
& h. Q% Z4 }4 ]* {3 G# b    /**
/ {3 G& R, ]" E$ w     * 入队
     * @param object 入队元素
     */
    void push(Object object);
% H3 c4 S% Z% k) b: h+ `
. A' d, F' F" U& Y! v+ ]+ Q    /**
     * 出队
     * @return 出栈元素
2 r0 M8 @9 G5 _8 R     */
    Object pull();

    /**
     *  获取元素个数
& M, p' P  x  O+ [, }% w     * @return 元素个数
     */
    int getElementCount();

    /**
+ x! v" w4 H2 V- {6 |0 |) o+ B) O     *  获取队头元素
1 |# D' d, v: x" F  e     * @return 队头元素
     */
    Object getFront();
$ S' h. E& E" w. _  t" ^
8 S) H  d$ k6 ]    /**
9 j6 n2 V" ~) i2 I. t, U# C     *  获取队尾元素
% J, L- v& ?  O; l     * @return 队尾元素
     */
    Object getRear();
2 _8 T# a5 r- \
    /**
     * 遍历队列的元素
     */
2 k5 d$ K# l8 t, Z: J6 V* c    void traverse();
( P. W6 U" W- U}
! F4 {! [+ e5 T: U! p) j2、队列的接口实现
2 O0 K% I" ~& @( Z5 |' |/ y/**
* 队列的接口实现
*
* @author zhuhuix
* @date 2020-05-01
*/
5 @' l# G- M; b4 I- Mpublic class QueueImpl implements Queue {

    protected Object[] element;
  Y% i$ V. _8 c5 w, Z
& w/ O8 Y- d  f) g- J1 h    protected int elementCount;

    //队头
1 B7 e# X5 Z' D! u! I    private int front;
( W' a% p8 i) D) W& v& x5 b
    //队尾
    private int rear;
: g$ j: g+ }9 R6 \  {# i
    private int defaultSize = 16;
9 z/ N! [1 o5 K, o1 E
5 g  i1 \# G; ]: u! c    private int maxSize;
9 G0 [+ O* S6 [% q0 ^& c* J9 y
    QueueImpl() {
        element = new Object[defaultSize];
        maxSize = defaultSize;
- D8 z  k% Y3 \5 u        front = 0;
        rear = -1;
    }
5 n8 t/ W1 ?; ?. U" {* |
    QueueImpl(int size) {
        element = new Object[size];
        maxSize = size;
        front = 0;
        rear = -1;
    }
+ T3 i% p$ A3 Y  `& u2 t" T! x: u
    @Override
    public int getMaxSize() {
        return maxSize;
    }

    @Override
8 u- L! X- a" L8 p- E' Q    public void push(Object object) {
) E6 L$ m) |7 L9 f        //如果元素个数已经达到数组的最大个数，则进行扩容
+ y" @% F0 T) t& ~: K0 c5 e3 |        if (elementCount == maxSize) {
+ v8 m5 Q' z' c$ ^            throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
# Y7 k; X' o% o& e5 w% r( d# E        }
        element[++rear] = object;
        if (rear == element.length) {
2 ~6 h  L' i) S: w            rear = -1;
& }# w- E( g+ \/ Z9 n+ b, H        }
        elementCount++;
    }

( m% M3 ]3 j" l% M  ^    @Override
4 `' J8 ?# l) m    public Object pull() {
7 }' o1 Y$ k2 b        if (elementCount == 0) {
            throw new ArrayIndexOutOfBoundsException("队列中无元素");
5 F/ P" e/ i) H' H: j3 q/ d+ I        }
  D% \9 e. P" }; l1 C        Object object = element[front];
" Y  N/ S8 u4 Q) C* _* j* g# y        element[front] = null;
        front++;
, L. ~0 F1 G- v$ P  k( F( h+ s        elementCount--;
        //队列清空，队头队尾恢复初始值
9 Z0 u, _% e/ K2 U# L, J        if (elementCount == 0) {
            front = 0;
            rear = -1;
) g6 T- }1 r) w7 @- X9 Z        }
        return object;
    }

; e; b/ x0 J0 X7 h5 e/ {* f    @Override
    public int getElementCount() {
& ]" W8 W2 i  ~/ g5 `        return elementCount;
# [6 ?$ u6 J. X+ B    }
" t, g1 D5 i1 y2 e
    @Override
! Y2 h8 v/ P( u* I9 n' w    public Object getFront() {
6 p+ @; H* d! N' Y9 z        if (elementCount == 0) {
7 J% P4 G4 L* n4 D: ?5 V0 b( h            System.out.print("队头无元素");
) R; s" [0 u" r8 U            return null;
  Z6 b/ D% V  h7 V4 N3 e6 X0 Z6 W        }
        return element[front];
/ H- Z5 p3 ^; q/ T% w. o7 i5 y    }

0 q  f8 P" a$ y# I# t9 w- F    @Override
    public Object getRear() {
3 u. m2 R+ r' r$ R9 v        if (elementCount == 0) {
            System.out.print("队尾无元素");
  r  o1 g- z( D% y, w3 ~6 g7 F            return null;
" u2 [8 ^' r) U# k, n' M) h3 \        }
& f4 a) k+ t$ J/ v, W4 @. D        return element[rear];
" i6 j: Q8 g. K3 v% Q, `) C* t; r    }
" p9 ~+ t2 W9 |* v% o) Y
    @Override
: o" v0 q" ]" ?, @    public void traverse() {
        if (elementCount == 0) {
            return;
        }
        for (int i = front; i <= rear; i++) {
* B. d1 X5 K9 g6 E# k- G            System.out.print(element + ",");
8 b& @, }5 ?: @5 [( m        }
5 A/ z) ~0 Z6 t$ b        System.out.println();
2 T6 t  N2 I3 S: J    }
}
. ^6 y3 x  c6 n& O' q
: v7 i* j, R. C5 S5 i4 l, F, B
3、队列的测试
public class QueueTest {
    public static void main(String[] args) {
        Queue queue = new QueueImpl();
6 W/ z& H( M1 Y2 j. |4 L
: \9 A% ]- }  H        //获取队列大小
- h6 A* q. X# q  l& Z        System.out.println("队列中最大可放置元素：" + queue.getMaxSize());

: x. C) O0 g7 E        //第一次入队列:压入1-15
* W$ r% L2 R. ~, a        for (int i = 0; i < 16; i++) {
2 g, `- ~) \# Q1 p            queue.push(i);
        }
        System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
' ]' x8 r4 X9 j5 ^        queue.traverse();
        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
) i+ D3 O  A% X
        //第一次出队:取出0-15
        for (int i = 0; i < 16; i++) {
4 X0 y$ y# S5 J; S            queue.pull();
        }
* C" b* s: N! \! p% f3 ~        System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
1 v8 _: h3 I# w        queue.traverse();
. H3 Z2 z, q  g$ R/ `        System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());


        //第二次入队列:压入16，31
* f! F5 `$ z# R9 }1 [        for (int i = 16; i < 32; i++) {
! A. l$ J4 K* W. O0 ~5 u            queue.push(i);
        }
        System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
6 r! C# T/ Z, W( q) M% ~        queue.traverse();

- J0 m+ |6 v  m, U4 |
        //第二次出队:取出16-31
        for (int i = 0; i < 16; i++) {
            queue.pull();
        }
* y. m! X& ]* l; V" F8 K" ?        System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
        queue.traverse();
# }6 F; _" ?7 }/ W5 E
- @$ S9 s. E# u* ]. K        //空队列出队报错
& x. h" u6 U: e" _2 Y' Z6 _        queue.pull();
8 z  G" m$ N3 Y. U
* g9 X, q9 \& v) s    }
}

$ ~) x/ I. ?  A
  S  Q! R  ?7 `% ^# U1 G5 K
4 O* |1 X9 p$ z

) _# V) G* G. z

3 p( l; G6 d  e2 b( q/ I. R3 X
0 ~, x; ^5 X2 A

' E" |2 n7 }& r5 ^/ P



1 x% Q7 a! ~5 U" T; k' h
: z- @. c, `$ z' D  G6 p————————————————
% ~# i# `% w' B4 ?" I2 e, p版权声明：本文为CSDN博主「智慧zhuhuix」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
+ a8 g4 {  X! H/ @4 _6 Q% l原文链接：https://blog.csdn.net/jpgzhu/article/details/105876785
9 n1 L' S; b  I% i4 `- Q; q( E
" y. x" f' G. L  I4 Z8 E4 I& a6 P7 p
" |7 S3 q4 Y! h( D; u