栈和队列java实现

栈和队列都是动态集合，且在其上进行DELETE操作所移除的元素是预先设定的。在栈中，被删除的是最近插入的元素：栈实现的是一种后进先出（last-in，first-out，LIFO） 策略。在队列中，被删去的总是在队列中存在时间最长的那个元素：队列实现的是一种先进先出（first-in，first-out，FIFO） 策略。

栈

可以用一个数组A[1…n]来实现一个最多可容纳n个元素的栈。同时，需要有一个top属性，指向数组最新插入的元素，即栈顶元素。栈中包含的元素为S[1…top]，其中S[1]是栈底元素。栈的示意图如下：

基于java数组简单实现的栈，代码如下：

/**
 * 数据结构-栈
 */
public class MyStack {
    /**
     * 栈顶指针
     */
    private int top;

    /**
     * 保存栈中数据的数组，默认初始容量为10
     */
    private int[] data;

    public MyStack() {
        this.data = new int[10];
    }

    public MyStack(int cap) {
        this.data = new int[cap];
    }

    /**
     * 判断栈是否为空
     *
     * @return 是否为空
     */
    public boolean isEmpty() {
        return this.top == 0;
    }

    /**
     * 入栈操作
     *
     * @param num 入栈的元素
     */
    public void push(int num) {
        // 保存数据的数组已满，需要扩容
        if (this.top == this.data.length - 1) {
            throw new Error("stack is full!");
        }
        this.top++;
        this.data[this.top] = num;
    }

    /**
     * 弹出栈顶元素
     *
     * @return 栈顶元素
     */
    public int pop() {
        if (isEmpty()) {
            throw new Error("stack is under flow!");
        }
        this.top--;
        return this.data[this.top + 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

队列

队列有队头(head)和队尾(tail)。head属性指向队头元素，tail属性指向下一个新元素将要插入的位置。基于数组实现的队列，示意图如下：

基于java数组简单实现的队列，代码如下：

/**
 * 数据结构-队列
 */
public class MyQueue {
    /**
     * 队头，指向队列的第一个元素
     */
    private int head = 0;

    /**
     * 队尾，指向下一个新元素将要插入的位置
     */
    private int tail = 0;

    /**
     * 队列中的元素个数
     */
    private int size = 0;

    /**
     * 数据
     */
    private final int[] data;

    public MyQueue() {
        this.data = new int[10];
    }

    public MyQueue(int cap) {
        data = new int[cap];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 入队操作
     *
     * @param num 将要入队的元素
     */
    public void enQueue(int num) {
        if (size == data.length) {
            throw new Error("queue is full!");
        }
        data[tail] = num;
        size++;
        if (tail == data.length - 1) {
            tail = 0;
        } else {
            tail++;
        }
    }

    /**
     * 出队操作
     *
     * @return 队头元素
     */
    public int deQueue() {
        if (size == 0) {
            throw new Error("queue is empty!");
        }
        int x = data[head];
        size--;
        if (head == data.length - 1) {
            head = 0;
        } else {
            head++;
        }
        return x;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73