1. 环形队列
用数组实现一个容量固定的环形队列，需要实现队列的入队，出队，返回元素个数，判空，判断队列是否满等操作。（假设队列只存放整数）。即需要实现如下接口：
1
2
3
4
5
6
7
8
9
10
11
12
| public interface RingQueue {
void enqueue(int value);
int poll();
boolean isEmpty();
boolean isFull();
int size();
}
|
1.1. 使用一个size变量记录当前队列的元素个数
队列有队头和队尾，我们需要一个头指针head和尾指针rear记录队列的头和尾，还需要一个size变量记录队列中的元素个数。头指针head始终指向队列中的第一个元素的位置，尾指针rear始终指向队列中最后一个元素的下一个位置。
当元素需要入队列的时候，只需在rear位置处放入元素，然后rear前进一个位置；
当元素需要出队列的时候，只需返回head位置的元素，然后head前进一个位置；
那怎么判断队列的空和满呢？当size等于0的时候，队列空，size等于数组长度的时候，队列满。如下图所示：
根据上述逻辑可以实现如下代码：
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
| public class ArrayRingQueue1 implements RingQueue {
private int size, rear, head;
private int[] queue;
public ArrayRingQueue1(int capacity) {
queue = new int[capacity];
}
@Override
public void enqueue(int value) {
queue[rear] = value;
rear = next(rear);
++size;
}
@Override
public int poll() {
int v = queue[head];
head = next(head);
--size;
return v;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == queue.length;
}
@Override
public int size() {
return size;
}
private int next(int index) {
if(index == queue.length - 1) return 0;
else return index + 1;
}
}
|
1.2. 不使用size变量
当有size的时候，可以使用size和数组的长度关系判断队列是否为空，是否满，不使用size变量，如何实现呢？直觉告诉我们，当rear指针“追上”head指针的时候，队列为满，那此时队列是否为满的条件是否可以定为head == rear呢？不可以！因为read == head的时候，队列还有可能为空。那么怎么解决这个问题？如下图所示：
于是我们可以写出如下代码：
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
| public class ArrayRingQueue2 implements RingQueue {
private int rear, head;
private int[] queue;
public ArrayRingQueue1(int capacity) {
queue = new int[capacity + 1];
}
@Override
public void enqueue(int value) {
queue[rear] = value;
rear = next(rear);
}
@Override
public int poll() {
int v = queue[head];
head = next(head);
return v;
}
@Override
public boolean isEmpty() {
return head == rear;
}
@Override
public boolean isFull() {
return next(rear) == head;
}
@Override
public int size() {
return rear - head + (rear < head ? queue.length : 0);
}
private int next(int index) {
if(index == queue.length - 1) return 0;
else return index + 1;
}
}
|
2. 最小栈
设计一个栈，可以返回当前栈的最小值，要求时间空间复杂度尽可能的低。我们可以使用两个栈来实现，一个是数据栈，一个是最小值栈，数据栈用来存储数据，而最小值栈用来存储当前数据栈中的最小值，每次数据栈数据发生变化的时候，都要在最小值栈存储当前的最小值。一开始两个栈都是空的。
当数据栈push一个元素的时候，需要把当前元素和最小值栈的栈顶元素对比，如果没有栈顶，或者当前元素小于栈顶，那么把当前元素也压入最小值栈，否则把最小值栈的栈顶再次压入最小值栈。
当数据栈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
| import java.util.Stack;
public class MinStack {
private Stack<Integer> data, min;
public MinStack() {
data = new Stack<>();
min = new Stack<>();
}
public void push(int value) {
data.push(value);
if(min.isEmpty() || min.peek() > value) min.push(value);
else min.push(min.peek());
}
public int pop() {
int ans = data.pop();
min.pop();
return ans;
}
public int getMin() {
return min.peek();
}
}
|
3. 用栈实现队列
因为队列是先进先出，栈是后进先出，因此我们需要使用两个栈，当需要入队列的时候，把数据压入其中一个栈中，当需要出队列的时候，先把栈中的数据倒出，压入另外一个栈，在从另外一个栈弹出。这样就保证了入队列和出队列的顺序。如下图所示：
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| import java.util.Stack;
public class QueueUsingStack {
private Stack<Integer> data, help;
public QueueUsingStack() {
data = new Stack<>();
help = new Stack<>();
}
public void enqueue(int value) {
data.push(value);
}
public int poll() {
if(help.isEmpty()) {
while(!data.isEmpty) help.push(data.pop());
}
return help.pop();
}
}
|
4. 用队列实现栈
可以使用两个队列，一个数据队列，一个辅助队列，当压入数据的时候，把数据压入数据队列，当弹出栈顶数据的时候，需要把之前的所有元素都出队列到辅助队列中，然后返回当前元素。然后辅助队列和数据队列的引用交换。如下图所示：
代码如下：
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
| import java.util.LinkedList;
import java.util.Queue;
public class StackUsingQueue {
private Queue<Integer> data, help;
public StackUsingQueue() {
data = new LinkedList<>();
help = new LinkedList<>();
}
public void push(int value) {
data.offer(value);
}
public int pop() {
while(data.size() > 1) help.offer(data.poll());
int ans = data.poll();
Queue<Integer> t = data;
data = help;
help = t;
return ans;
}
}
|
可以只用一个队列实现栈吗？可以的！一个队列既是数据队列，又是辅助队列。如下图所示：
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| import java.util.LinkedList;
import java.util.Queue;
public class StackUsingSingleQueue {
private Queue<Integer> data;
public StackUsingQueue() {
data = new LinkedList<>();
}
public void push(int value) {
data.offer(value);
}
public int pop() {
int size = data.size();
if(size > 1) {
for(int i = 0; i < size - 1; ++i) data.offer(data.poll());
}
return data.poll();
}
}
|
