数据结构（二）队列和栈

Java提供了java.util.Stack类来表示栈数据结构。Stack类是Vector类的子类，它实现了一个标准的后进先出（LIFO）栈。同样也提供了Queue接口，表示一系列按照特定顺序排列的元素，其中最早添加的元素将最先被移除（先进先出，FIFO）。并且Deque（双端队列，Double Ended Queue）扩展了Queue接口，提供了在队列两端进行插入和删除操作的方法。Deque允许在队列的两端进行元素的添加、获取和移除操作，因此可以用来实现栈、队列等数据结构。

但是今天仅仅用最简单的数组完成队列和栈的实现

队列

队列（Queue）是一种常见的线性数据结构，它按照先进先出（First-In-First-Out，FIFO）的原则管理元素。换句话说，最先添加到队列中的元素将首先被移除。队列通常具有两个主要操作：入队（Enqueue）和出队（Dequeue）。入队操作将元素添加到队列的尾部，而出队操作则将队列的头部元素移除并返回。

需求分析

首先作为对数组的封装，容量 capacity 和T[] queue必不可少

其次，目前队列中的元素个数 size 也要记录下来、

最后就是两个指针，一个指向head， 另一个指向tail

public class ArrayQueue {
    private int[] queue; // 用于存储元素的数组
    private int capacity; // 队列的容量
    private int size; // 队列中元素的个数
    private int head; // 队列头部指针
    private int tail; // 队列尾部指针

    // 构造函数，初始化队列
    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        queue = new int[capacity];
        size = 0;
        head = 0;
        tail = -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

作为队列，肯定需要放置元素，取出元素以及其他容器的基本操作。

判断元素个数，是否为空或满

    // 判断队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 判断队列是否已满
    public boolean isFull() {
        return size == capacity;
    }

    // 获取队列中元素的个数
    public int size() {
        return size;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

放置元素

    // 向队列尾部添加元素
    public void enqueue(int element) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        tail = (tail + 1) % capacity;
        queue[tail] = element;
        size++;
    }
1
2
3
4
5
6
7
8
9

获取元素

获取元素有两种选择，

一，获取并移除元素

    // 从队列头部移除元素并返回
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int removed = queue[head];
        head = (head + 1) % capacity;
        size--;
        return removed;
    }
1
2
3
4
5
6
7
8
9
10

二，只获取不移除元素

    // 获取队列头部元素但不移除
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return queue[head];
    }
1
2
3
4
5
6
7

完整代码

public class ArrayQueue {
    private int[] queue; // 用于存储元素的数组
    private int capacity; // 队列的容量
    private int size; // 队列中元素的个数
    private int head; // 队列头部指针
    private int tail; // 队列尾部指针

    // 构造函数，初始化队列
    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        queue = new int[capacity];
        size = 0;
        head = 0;
        tail = -1;
    }

    // 向队列尾部添加元素
    public void enqueue(int element) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        tail = (tail + 1) % capacity;
        queue[tail] = element;
        size++;
    }

    // 从队列头部移除元素并返回
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int removed = queue[head];
        head = (head + 1) % capacity;
        size--;
        return removed;
    }

    // 获取队列头部元素但不移除
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return queue[head];
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 判断队列是否已满
    public boolean isFull() {
        return size == capacity;
    }

    // 获取队列中元素的个数
    public int size() {
        return size;
    }

    public static void main(String[] args) {
        ArrayQueue queue = new ArrayQueue(5);
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        System.out.println("Dequeued: " + queue.dequeue()); // 输出：Dequeued: 1
        System.out.println("Peek: " + queue.peek()); // 输出：Peek: 2
    }
}
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

栈

栈（Stack）是一种常见的线性数据结构，它遵循后进先出（Last-In-First-Out，LIFO）的原则。换句话说，最后添加到栈中的元素将首先被移除。栈通常具有两个主要操作：压入（Push）和弹出（Pop）。压入操作将元素添加到栈顶，而弹出操作则将栈顶的元素移除并返回。

需求分析

其实基本同上，不过栈只需要一个size就够，无需head，tail索引。

public class ArrayStack {

    private int[] array; // 用于存储元素的数组
    private int size; // 栈中元素的个数

    // 构造函数，初始化指定容量的栈
    public ArrayStack(int capacity) {
        array = new int[capacity];
        size = 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11

其余需求也就是这些，和队列基本一致。

• 压入（Push）： 向栈顶添加一个元素。
• 弹出（Pop）： 从栈顶移除一个元素，并返回移除的元素。
• 查看栈顶元素（Peek）： 返回栈顶的元素但不移除。
• 判空（isEmpty）： 检查栈是否为空。
• 获取栈的大小（Size）： 返回栈中元素的个数。

考虑到一端进出，栈可以实现自动扩容。

元素个数，是否为空

    // 判断栈是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 获取栈中元素的个数
    public int size() {
        return size;
    }
1
2
3
4
5
6
7
8
9

取元素

如上，有放回和无放回

    // 弹出栈顶元素并返回
    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        int removed = array[--size];
        array[size] = 0; // 用于清除被移除元素的引用
        if (size > 0 && size == array.length / 4) {
            resize(array.length / 2); // 缩容
        }
        return removed;
    }

    // 获取栈顶元素但不移除
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return array[size - 1];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

resize函数下面会讲。

放置元素

这里我们判断是否已满，满了就扩容

    // 压入元素到栈顶
    public void push(int element) {
        if (size == array.length) {
            resize(2 * array.length); // 扩容
        }
        array[size++] = element;
    }
1
2
3
4
5
6
7

动态扩缩容

resize就是扩（缩）容函，实现如下

    // 调整栈的容量
    private void resize(int newCapacity) {
        int[] newArray = new int[newCapacity];
        for (int i = 0; i < size; i++) {
            newArray[i] = array[i];
        }
        array = newArray;
    }

1
2
3
4
5
6
7
8
9

全部代码

public class ArrayStack {

    private int[] array; // 用于存储元素的数组
    private int size; // 栈中元素的个数


    // 构造函数，初始化指定容量的栈
    public ArrayStack(int capacity) {
        array = new int[capacity];
        size = 0;
    }

    // 压入元素到栈顶
    public void push(int element) {
        if (size == array.length) {
            resize(2 * array.length); // 扩容
        }
        array[size++] = element;
    }

    // 弹出栈顶元素并返回
    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        int removed = array[--size];
        array[size] = 0; // 用于清除被移除元素的引用
        if (size > 0 && size == array.length / 4) {
            resize(array.length / 2); // 缩容
        }
        return removed;
    }

    // 获取栈顶元素但不移除
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return array[size - 1];
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 获取栈中元素的个数
    public int size() {
        return size;
    }

    // 调整栈的容量
    private void resize(int newCapacity) {
        int[] newArray = new int[newCapacity];
        for (int i = 0; i < size; i++) {
            newArray[i] = array[i];
        }
        array = newArray;
    }

    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(10);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("Popped: " + stack.pop()); // 输出：Popped: 3
        System.out.println("Peek: " + stack.peek()); // 输出：Peek: 2
    }
}

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

总结

• 栈和队列都是线性数据结构，但它们的操作顺序和特性不同，适用于不同的应用场景。
• 栈常用于需要后进先出操作的场景，例如函数调用、表达式求值等。
• 队列常用于需要先进先出操作的场景，例如任务调度、消息传递等。
• 栈和队列都可以使用数组或链表来实现，具体选择取决于应用场景和需求。