程序员面试题：用数组实现队列，如果是环形队列呢？
By Long Luo
之前我们已经实现了225. 用队列实现栈 和 232. 用栈实现队列 。最近遇到一道手写代码面试题：用数组实现队列。
其实这道题非常之简单，但之前数据结构与算法基础知识不过关，居然没有现场写出来。
队列(Queue)
队列是一个有序列表，遵循FIFO(先入先出)的原则。
队列有头有尾，有容量。
代码如下所示：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// implement the queue use array
public class MyQueue {
int[] array;
int front;
int rear;
int capacity;
public MyQueue(int capacity) {
this.capacity = capacity;
array = new int[capacity];
front = 0;
rear = 0;
}
public void enqueue(int x) {
if (rear == capacity) {
return;
}
array[rear] = x;
rear++;
}
public void dequeue() {
if (front == rear) {
return;
}
for (int i = 0; i < rear - 1; i++) {
array[i] = array[i + 1];
}
array[rear] = 0;
rear--;
}
public int front() {
if (front == rear) {
return -1;
}
return array[front];
}
public boolean empty() {
return front == rear;
}
}
dequeue()也可以优化为 \(O(1)\)，直接让front+1，但front == rear时，可能会出现还有容量的情况，但这里无法体现出来，所以要使用环形队列。
环形队列(Circular Queue)
环形队列是将头和尾是连接起来的，避免资源的浪费，可以循环使用数组空间进行数据存储。
头指针 \(\textit{head}\)：指向当前第一个元素的位置称为头指针。
尾指针 \(\textit{tail}\)：指向当前最后一个元素的下一个位置为尾指针。
当前元素的数量 = \((tail - head + capacity) mod capacity\)
初始状态（空）：\(head == tail\)
满：\((tail + 1) mod capacity == 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67// Circular Queue
public class CircularQueue {
int capacity;
int head;
int tail;
int[] array;
CircularQueue(int capacity) {
if (capacity <= 0) {
return;
}
this.capacity = capacity;
this.head = this.tail = 0;
array = new int[capacity];
}
public boolean empty() {
return head == tail;
}
public boolean isFull() {
return (tail + 1) % capacity == head;
}
public boolean enqueue(int data) {
if (isFull()) {
return false;
}
array[tail] = data;
tail = (tail + 1) % capacity;
return true;
}
public Integer dequeue() {
if (empty()) {
return null;
}
int x = array[head];
head = (head + 1) % capacity;
return x;
}
public void display() {
if (empty()) {
return;
}
for (int i = head; i < head + capacity; i++) {
System.out.printf("array[%d] = %d\n", i % capacity, array[i % capacity]);
}
}
public int size() {
return (tail - head + capacity) % capacity;
}
public Integer peek() {
if (empty()) {
return null;
}
return array[head];
}
}
复杂度分析：
- 时间复杂度：\(O(1)\)。
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗