Stack & Queue
什么是栈(Stack)、队列(Queue)?
在很多的应用中,我们需要维护多个对象的集合。这种操作一般来说都比较简单,例如向集合中添加、删除、更新某个元素,检查是否为空以及遍历整个集合。
栈(Stack),或者可以被称为下压栈。你可以将栈想象成为一堆邮件列表,按照通常的规则,每次新来一封邮件,往往都将其放至于最上方;同理,每次处理(查看)一封邮件,都是查看最新的邮件。
队列(Queue),遵守公平原则,你可以将队列想象成为现实中买票排队,永远保证等待时间最长的人最先出队。
栈(Stack)
栈(Stack),或者可以被称为下压栈。你可以将栈想象成为一堆邮件列表,按照通常的规则,每次新来一封邮件,往往都将其放至于最上方;同理,每次处理(查看)一封邮件,都是查看最新的邮件。
栈遵守后进先出(LIFO; Last In, First Out)原则。无论是从栈中添加亦或是删除操作,都只允许从栈顶进行操作。
如上图,栈内元素的顺序是:0->1->2->3->4
。
一般我们对于栈的基本操作无非以下几种:
- 入栈(push)
- 出栈(pop)
- 获取栈大小(size)
- 是否为空(isEmpty)
我们上面说过,无论是从栈中添加亦或是删除操作,都只允许在栈顶操作。
我们分别来看下分步图解入栈(添加)和出栈(删除)操作。
入栈(Push)
- 目前栈内元素的顺序是
0->1->2->3
- 入栈元素
4
,位置为栈顶 - 入栈后栈内元素为
0->1->2->3->4
出栈(Pop)
- 目前栈内元素的顺序是
0->1->2->3->4
- 出栈栈顶元素,出栈的元素为
4
- 出栈后栈内元素为
0->1->2->3
接下来我们看下代码层面的数组实现,你可以在我的Github找到此代码。
1 | package net.sunzhenyu.miscellaneous.dsa.stack; |
PS:还有一种是使用Node来实现栈,代码在这里
队列(Queue)
队列(Queue),遵守公平原则,你可以将队列想象成为现实中买票排队,永远保证等待时间最长的人最先出队。
队列是一种线性的数据结构,遵守先进先出(FIFI; First In First Out)原则;队列只允许在队首 进行出队操作,且只允许在队尾进行入队操作。
一般来说,队列的操作只有如下几种:
- 入队(enqueue)
- 出队(dequeue)
- 获取队列大小(size)
- 队列是否为空(isEmpty)
我们接下来来看下入队和出队操作的分步图解:
入队(EnQueue)
- 目前队列内元素为
0->1->2->3
- 入队元素
4
到队尾 - 入队后的队列内元素为
0->1->2->3->4
出队(DeQueue)
- 目前队列内元素为
0->1->2->3->4
- 从队首出队一个元素,元素为
0
- 出队后的队列内元素为
1->2->3->4
接下来我们来看下代码层面的数组实现,你也可以在我的Github找到此代码。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
88package net.sunzhenyu.miscellaneous.dsa.queue;
import java.util.Iterator;
public class ArrayQueue<T> implements IQueue<T> {
private Object[] elements;
private int size;
private int head;
private final Integer DEFAULT_CAPACITY = 10;
public ArrayQueue(int initialCapacity) {
if (initialCapacity <= 0) {
elements = new Object[DEFAULT_CAPACITY];
} else {
elements = new Object[initialCapacity];
}
}
public void enqueue(T element) {
ensureCapacity(this.elements.length << 1);
elements[size++] = element;
}
"unchecked") (
public T dequeue() {
if (size == (elements.length >> 4)) {
expandAndShrink(this.elements.length >> 1);
}
T result = (T) elements[head];
elements[head] = null;
if (++head == elements.length) {
head = 0;
}
return result;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private void ensureCapacity(int newCapacity) {
if (newCapacity <= 0) {
throw new IllegalArgumentException("The new capacity cannot smaller and equal than zero");
}
if (size >= elements.length) {
expandAndShrink(newCapacity);
}
}
"all") (
private void expandAndShrink(int newCapacity) {
Object[] newCapacityArray = new Object[newCapacity];
for (int i = 0; i < size; i++) {
newCapacityArray[i] = elements[i];
}
this.elements = newCapacityArray;
}
public Iterator<T> iterator() {
return new ArrayQueueIterator<>();
}
class ArrayQueueIterator<E> implements Iterator<E> {
private int index = head;
public boolean hasNext() {
return index < size;
}
"unchecked") (
public E next() {
return (E) elements[index++];
}
}
}