栈 和 队列 也是常见的数据结构。Java 里面的方法栈，消息队列 是 栈 和 队列 数据结构的实际应用。
栈
概念
栈(stack) 是一种线性数据结构。可以把栈想像成只有一端开口的圆筒容器。栈的元素只能先进后出(FILO：first int last out)，最早进入的元素存放的位置叫 栈底(bottom)，最后进入的元素的位置叫作 栈顶(top)。
基本操作
栈 的基本操作是 入栈 和 出栈。
入栈
入栈操作(push) 是把新元素放入栈中，只能从栈顶一侧放入元素，新元素的位置将成为新的 栈顶。
出栈
出栈操作(pop) 是把元素从栈中弹出，只有栈顶的元素才允许出栈，出栈元素的前一个元素的位置将成为新的 栈顶。
入栈 和 出栈 只会影响最后一个元素，不涉及其它元数的整体移动，所以无论是数组还是以链表实现，入栈、出栈的时间复杂度都是 Ο(1) 。
队列
概念
队列(queue) 是一种线性结构。可以把队列想像成单行隧道。队列容器有两个端口，一个是出口端，叫作 队头(front)，一个是入口端，叫作 队尾(rear)。队列中的元素只能先入先出(FIFO：first in first out)。
队列 即可用数组实现，也可用链表来实现。用数组实现，为了入队操作的方便，最后入队元素的下一个位置规定为队尾位置。
基本操作
入队
入队(enqueue) 是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将成为新的队尾。
出队
出队(dequeue) 是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将成为新的队头。
数组实现
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
| public class ArrayQueue {
private int maxSize;
private Object[] array;
private int front;
private int rear;
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
array = new Object[this.maxSize];
front = -1;
rear = -1;
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return rear == maxSize - 1;
}
public void add(int e) {
if (isFull()) {
throw new BusinessException("the array queue is full!");
}
rear++;
array[rear] = e;
}
public Object getHead() {
if (isEmpty()) {
throw new RuntimeException("the array queue is empty!");
}
Object result = array[0];
for (int i = 0; i < array.length - 1; i++) {
array[i] = array[i + 1];
}
array[rear] = null;
rear--;
return result;
}
}
|
循环队列
队列元素不断出队，队头空间失去作用浪费掉，队列的容量会越来越小。可以用数组实现的队列可采用循环队列(loop queue) 的方式来维持队列容量的恒定。
在数组不做扩容的前提下，让新元素入队并确定新的队尾位置，利用已出队元素留下的空间，让队尾指针重新指回数组的首（(准确的描述是让队尾指针指向队头元素出队空出的位置）。
循环队列在特理存储上，队尾的位置也可以在队头之前。当再有元素入队时，将其放入数组的首位，队尾指针继承后移即可。
一直到 (队尾下标 + 1) % 数组长度 = 队头下标，代表此队列直的已经满了。
注意：队尾指针指向的位置永远空出 1 位，所以队列最大容量比数组长度小 1 。
循环队列 不但充分利用了数组的空间，还避免了数组元素整体移动的麻烦，入队和出队的时间复杂度也是 Ο(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
68
69
70
71
72
73
74
75
76
77
| package com.datastructure.linkedlist;
public class LoopQueue {
private int[] array;
private int front;
private int rear;
public LoopQueue(int size) {
this.array = new int[size];
}
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 int deQueue() throws Exception {
if (rear == front) {
throw new Exception("队列已空");
}
int deQueueElement = array[front];
front = (front + 1) % array.length;
return deQueueElement;
}
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 {
LoopQueue loopQueue = new LoopQueue(6);
loopQueue.enQueue(1);
loopQueue.enQueue(3);
loopQueue.enQueue(7);
loopQueue.enQueue(2);
loopQueue.enQueue(4);
loopQueue.output();
System.out.println("-----------------------");
loopQueue.deQueue();
loopQueue.output();
loopQueue.deQueue();
loopQueue.deQueue();
loopQueue.deQueue();
loopQueue.output();
}
}
|
双端队列
双端队列数据结构，集合了栈和队列的优点，允许两端都可以进行入队或出队操作，其元素的逻辑仍是线性结构。
双端队列的实现可参考 Java 实现 数据结构-双端队列 。
优先队列
优先队列 遵循的是谁的优先级高，谁先出队。
优先队列不属于线性数据结构的范畴，通常采用堆数据结构来实现。
栈和队列的应用
栈的应用
栈的是先入后出的顺序，通常用于对 “历史” 回溯，即逆流而上追溯 “历史”。
例如 实现递归的逻辑，就可以用栈来代替，因为栈可以回溯方法的调用链。
队列的应用
队列有入队端口和出队端口，出队顺序是先进先出，返队列的入队顺序依次访问。
应用场景如消息队列；在多线程中，争夺锁的等待队列。
