栈和队列是十分基础的数据结构，分别实现了 FILO 和 FIFO 两种数据处理方式。
栈 (Stack)
栈(Stack)是一种线性的数据结构，栈中的元素遵循先入后出(FILO，First In Last Out)的原则。最早进入栈的元素位置称为栈底，最后进入站的元素位置成为栈顶。
操作栈
入栈 (push)
入栈(push)是将一个新的元素放入栈中，新元素的位置称为栈顶。
出栈 (pop)
出栈(pop)是将栈顶的元素从栈中弹出，原栈顶前一个元素位置成为新的栈顶。
代码实现
使用数组实现栈的代码如下：
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
| import java.util.Arrays;
public class MyArrayStack {
private int[] arr;
private int size;
public MyArrayStack(int length) {
arr = new int[length];
}
public void push(int data) {
if (size >= arr.length) arr = Arrays.copyOf(arr, 2 * arr.length);
arr[size] = data;
size++;
}
public void pop() {
arr[size - 1] = 0;
size--;
}
public void output() {
System.out.println(Arrays.toString(arr));
}
public static void main(String[] args) {
final var stack = new MyArrayStack(6);
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
stack.output();
stack.pop();
stack.output();
}
}
|
使用链表实现栈的代码如下：
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
| public class MyLinkedStack {
private Node head;
private Node last;
private int size;
public void push(int data) {
final var newNode = new Node(data);
if (size == 0) {
head = newNode;
} else {
newNode.prev = last;
last.next = newNode;
}
last = newNode;
size++;
}
public void pop() {
final var prevNode = last.prev;
prevNode.next = null;
last = prevNode;
size--;
}
public void output() {
var temp = this.head;
for (int i = 0; i < size; i++) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
private static class Node {
Node prev;
int data;
Node next;
Node(int data) {
this.data = data;
}
}
public static void main(String[] args) {
final var stack = new MyLinkedStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
stack.output();
stack.pop();
stack.output();
}
}
|
进行入栈、出栈操作的时间复杂度均为O(1)。
队列 (Queue)
队列(Queue)也是一种线性数据结构，队列中的元素遵循先入先出(FIFO，First In First Out)的原则。队列的出口端称为队头，入口端称为队尾。
操作队列
入队 (enqueue)
入队(enqueue)是将新的元素放入队列中，新元素下一个位置成为新的队尾。
出队 (dequeue)
出队(dequeue)是将队头的元素移出队列，出队元素的后一个元素成为新的队头。
代码实现
使用数组与链表实现队列的方式有所不同。
数组实现
在不考虑扩容的情况下，队列的容量(capacity)是有限的，不断出队会使得队头前的空间逐渐失去作用。此时我们可以使用循环队列来保证队列容量的恒定，即使用已经出队的空间，来存放新的元素。
当(队尾下标 + 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
| public class MyArrayQueue {
private int[] array;
private int front;
private int rear;
public MyArrayQueue(int capacity) {
this.array = new int[capacity];
}
public void enQueue(int element) throws Exception {
if ((rear + 1) % array.length == front)
throw new Exception("队列已满");
array[rear] = element;
rear = (rear + 1) % array.length;
}
public void deQueue() throws Exception {
if (rear == front) throw new Exception("队列已空");
front = (front + 1) % array.length;
}
public void output() {
for (int i = front; i != rear; i = (i + 1) % array.length) {
System.out.println(array[i]);
}
}
public static void main(String[] args) throws Exception {
final var queue = new MyArrayQueue(5);
queue.enQueue(1);
queue.enQueue(2);
queue.enQueue(3);
queue.enQueue(4);
queue.deQueue();
queue.deQueue();
queue.enQueue(5);
queue.enQueue(6);
queue.output();
}
}
|
循环队列的意义在于，其不仅充分利用了数组的空间，还避免了数组元素移动带来的性能损失。其入队与出队的时间复杂度为O(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
59
60
61
62
63
64
65
66
67
| public class MyLinkedQueue {
private Node head;
private Node last;
private int size;
public void enQueue(int data) {
final var newNode = new Node(data);
if (size == 0) {
head = newNode;
} else {
last.next = newNode;
newNode.prev = last;
}
last = newNode;
size++;
}
public void deQueue() {
final var nextNode = head.next;
nextNode.prev = null;
head = nextNode;
size--;
}
public void output() {
var temp = head;
for (int i = 0; i < size; i++) {
System.out.println(temp.data);
temp = temp.next;
}
}
private static class Node {
Node prev;
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
public static void main(String[] args) {
final var queue = new MyLinkedQueue();
queue.enQueue(1);
queue.enQueue(2);
queue.enQueue(3);
queue.enQueue(4);
queue.deQueue();
queue.deQueue();
queue.enQueue(5);
queue.enQueue(6);
queue.output();
}
}
|
参考资料