程序员面试题：用数组实现队列，如果是环形队列呢？

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 2 分钟

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. 😉😃💗