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

发表于 2021-06-20 更新于 2025-05-03 分类于 Data Structures and Algorithms Waline：阅读次数：本文字数： 2.3k 阅读时长 ≈ 2 分钟

By Long Luo

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

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

队列(Queue)

队列是一个有序列表，遵循FIFO(先入先出)的原则。

队列有头有尾，有容量。

代码如下所示：

// 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)

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

头指针 $head$ ：指向当前第一个元素的位置称为头指针。
尾指针 $tail$ ：指向当前最后一个元素的下一个位置为尾指针。
当前元素的数量 = $(t a i l - h e a d + c a p a c i t y) m o d c a p a c i t y$
初始状态（空）： $h e a d == t a i l$
满： $(t a i l + 1) m o d c a p a c i t y == h e a d$

代码如下所示：

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

队列(Queue)

环形队列(Circular Queue)

复杂度分析：

预览: