本文将简单介绍栈和队列的概念，给出它们的 Java 实现以及原理解析。
栈（Stack）
栈是一种线性数据结构，这意味着每个数据节点（元素）都只有一个前驱和一个后继。栈的特点是后进先出（LIFO，Last In First Out），即最后入栈的元素最先出栈。
后进先出：想象一下，你面前有一叠盘子，你每次只能将新的盘子放在最上面，而取盘子时也只能从最上面取你最后放的盘子。
栈被操作的元素不以下标（index）为代表，而是以栈顶（top）为代表。栈顶是栈中最后一个元素，也是唯一一个可以被操作的元素。
栈的基本操作包括：
push：将元素压入栈顶pop：将栈顶元素弹出，同时允许获取该元素的值
一个栈的 push 和 pop 操作示意图 [1]
栈还可以有其他操作，如：
peek：查看栈顶元素show：显示栈中所有元素isEmpty：判断栈是否为空isFull：判断栈是否已满size：获取栈的大小（元素个数）
栈可以使用数组以及其他的数据结构（如 ArrayList、链表等）实现。下面是一个使用数组实现的栈的 Java 代码以及对应的原理解析。
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
class MyStack {
private int[] elements = new int[10];
private int top = 0;
public void push(int element) {
if (!isFull()) {
elements[top] = element;
top++;
} else {
System.out.println("The stack is full. Cannot push any more elements.");
}
}
public int pop() {
if (!isEmpty()) {
top--;
return elements[top];
} else {
System.out.println("The stack is empty. Cannot pop any more elements.");
return -1;
}
}
public void show() {
if (isEmpty()) {
System.out.println("The stack is empty. Cannot show any elements.");
return;
}
for (int i = 0; i < top; i++) {
System.out.print(elements[i] + " ");
}
System.out.println();
}
public void peek() {
if (isEmpty()) {
System.out.println("The stack is empty. Cannot peek any element.");
}
System.out.println("The top element is " + elements[top - 1]);
}
public boolean isEmpty() {
return top == 0;
}
public boolean isFull() {
return top == elements.length;
}
public int size() {
return top;
}
}
public class Main {
public static void main(String[] args) {
}
}
|
但是，在上述代码中，栈的容量是固定的，无法动态调整。但是我们通常希望栈的容量是动态的，即可以根据需要自动扩展或缩小。这时我们有两种方法：
- 使用数组实现栈，当栈满时，创建一个新的更大的数组，将原数组中的元素复制到新数组中，然后将新数组作为栈的存储结构。
- 使用 ArrayList 实现栈。ArrayList 是一个动态数组，可以根据需要自动扩展或缩小。
我们将会使用第二种方法（因为相对简单），下面是一个使用 ArrayList 实现的栈的 Java 代码。
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| package org.qianq;
import java.util.ArrayList;
class MyStackArrayList {
private ArrayList<Integer> elements = new ArrayList<>();
private int top = 0;
public void push(int element) {
elements.add(element);
top++;
}
public int pop() {
if (!isEmpty()) {
top--;
return elements.remove(top);
} else {
System.out.println("The stack is empty. Cannot pop any more elements.");
return -1;
}
}
public void show() {
if (isEmpty()) {
System.out.println("The stack is empty. Cannot show any elements.");
return;
}
for (int i = 0; i < top; i++) {
System.out.print(elements.get(i) + " ");
}
System.out.println();
}
public void peek() {
if (isEmpty()) {
System.out.println("The stack is empty. Cannot peek any element.");
}
System.out.println("The top element is " + elements.get(top - 1));
}
public boolean isEmpty() {
return top == 0;
}
public int size() {
return top;
}
}
public class Main {
public static void main(String[] args) {
}
}
|
你会发现其实两个版本的代码并没有太大区别。这些就是常用的栈的实现方法。
队列（Queue）
队列同样是一种线性数据结构，但它的特点是先进先出（FIFO，First In First Out），即最先入队的元素最先出队（就跟生活中排队一样）。
与栈不同，由于一个队列需要同时操作队首和队尾，因此队列有两个元素表示：队首（front）和队尾（rear）。队首是队列中第一个元素（最早入队的元素），队尾是队列中最后一个元素（最晚入队的元素）。
队列的基本操作包括：
enqueue：将元素入队dequeue：将队首元素出队，同时允许获取该元素的值
队列还可以有其他操作，如：
show：显示队列中所有元素isEmpty：判断队列是否为空isFull：判断队列是否已满
我们仍然从一个使用数组实现的队列开始：
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
| class MyQueue {
private final static int CAPACITY = 10;
private int[] elements = new int[CAPACITY];
int front = 0, rear = -1, current_size = 0;
public void enqueue(int element) {
if (isFull()) {
System.out.println("The queue is full. Cannot enqueue.");
return;
}
rear++;
elements[rear] = element;
current_size++;
}
public int dequeue() {
if (isEmpty()) {
System.out.println("The queue is empty. Cannot dequeue.");
return -1;
}
front++;
current_size--;
return elements[front - 1];
}
public void show() {
for (int i = front; i <= rear; i++) {
System.out.print(elements[i] + " ");
}
System.out.println();
}
public boolean isEmpty() {
return current_size == 0;
}
public boolean isFull() {
return current_size == CAPACITY;
}
}
public class Main {
public static void main(String[] args) {
}
}
|
但是，同样的，这个队列的容量是固定的，无法动态调整。我们虽然一样可以使用 ArrayList 来调整队列的容量，但是这里我们可以实现一个环形队列（Circular Queue）。
环形队列可以被想象成一个首尾相连的环。当任何一个指针到达数组的末尾时，它会回到数组的开头。这样，我们就可以重复利用数组中已经被出队的元素的空间（否则出队的元素所占的空间就会被浪费掉）。
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
| class MyCircularQueue {
private final static int CAPACITY = 10;
private int[] elements = new int[CAPACITY];
int front = 0, rear = -1, current_size = 0;
public void enqueue(int element) {
if (isFull()) {
System.out.println("The queue is full. Cannot enqueue.");
return;
}
rear = (rear + 1) % CAPACITY;
elements[rear] = element;
current_size++;
}
public int dequeue() {
if (isEmpty()) {
System.out.println("The queue is empty. Cannot dequeue.");
return -1;
}
front = (front + 1) % CAPACITY;
current_size--;
return elements[front - 1];
}
public void show() {
for (int i = 0; i < current_size; i++) {
System.out.print(elements[(front + i) % CAPACITY] + " ");
}
System.out.println();
}
public boolean isEmpty() {
return current_size == 0;
}
public boolean isFull() {
return current_size == CAPACITY;
}
}
public class Main {
public static void main(String[] args) {
}
}
|
例题
Coming soon…
![一个栈的 push 和 pop 操作示意图 [1]](https://img.cubik65536.top/LIFO-Stack.svg)
![一个 Queue 在被操作时的示意图 [2]](https://img.cubik65536.top/DataQueue.png)
![一个环形队列的示意图 [3]](https://img.cubik65536.top/CircularQueue.png)
