程序员面试题:用数组实现队列,如果是环形队列呢?

By Long Luo

之前我们已经实现了225. 用队列实现栈232. 用栈实现队列 。最近遇到一道手写代码面试题:用数组实现队列。

其实这道题非常之简单,但之前数据结构与算法基础知识不过关,居然没有现场写出来。

队列(Queue)

队列是一个有序列表,遵循先入先出的原则。

队列有头有尾,有容量。

代码如下所示:

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)O(1),直接让front+1,但front == rear时,可能会出现还有容量的情况,但这里无法体现出来,所以要使用环形队列

环形队列(Circular Queue)

环形队列是将头和尾是连接起来的,避免资源的浪费,可以循环使用数组空间进行数据存储。

  • 头指针head\textit{head}:指向当前第一个元素的位置称为头指针。

  • 尾指针tail\textit{tail}:指向当前最后一个元素的下一个位置为尾指针。

  • 当前元素的数量 = (tailhead+capacity)%capacity(tail - head + capacity) \% capacity

  • 初始状态(空):head==tailhead == tail

  • 满:(tail+1)%capacity==head(tail + 1) \% 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)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. 😉😃💗