跳转到内容
VitaLogos
新建笔记

队列

知识概念更新于 编辑本文

「队列 queue」是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。

将队列头部称为**“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”**。

image-20240329234845141

队列常用操作

跳转到“队列常用操作”

不同编程语言的方法名称可能会有所不同。我们在此采用与栈相同的方法命名。

表 5-2 队列操作效率

方法名描述时间复杂度
push()元素入队，即将元素添加至队尾O(1)
pop()队首元素出队O(1)
peek()访问队首元素O(1)

直接使用编程语言中现成的队列类：

/* 初始化队列 */
queue<int> queue;


/* 元素入队 */
queue.push(1);
queue.push(3);
queue.push(2);
queue.push(5);
queue.push(4);


/* 访问队首元素 */
int front = queue.front();


/* 元素出队 */
queue.pop();


/* 获取队列的长度 */
int size = queue.size();


/* 判断队列是否为空 */
bool empty = queue.empty();
from collections import deque


# 初始化队列
# 在 Python 中，我们一般将双向队列类 deque 当作队列使用
# 虽然 queue.Queue() 是纯正的队列类，但不太好用，因此不推荐
que: deque[int] = deque()


# 元素入队
que.append(1)
que.append(3)
que.append(2)
que.append(5)
que.append(4)


# 访问队首元素
front: int = que[0]


# 元素出队
pop: int = que.popleft()


# 获取队列的长度
size: int = len(que)


# 判断队列是否为空
is_empty: bool = len(que) == 0

队列实现&应用

跳转到“队列实现&应用”

为了实现队列，我们需要一种数据结构，可以在一端添加元素，并在另一端删除元素，链表和数组都符合要求。

基于链表的实现
跳转到“基于链表的实现”

我们可以将链表的**“头节点”和“尾节点”分别视为“队首”和“队尾**”，规定队尾仅可添加节点，队首仅可删除节点。

LinkedListQueuepush()pop()
image-20240329235226236image-20240329235241730image-20240329235257713
/* 基于链表实现的队列 */
class LinkedListQueue {
  private:
    ListNode *front, *rear; // 头节点 front ，尾节点 rear
    int queSize;


  public:
    LinkedListQueue() {
        front = nullptr;
        rear = nullptr;
        queSize = 0;
    }


    ~LinkedListQueue() {
        // 遍历链表删除节点，释放内存
        freeMemoryLinkedList(front);
    }


    /* 获取队列的长度 */
    int size() {
        return queSize;
    }


    /* 判断队列是否为空 */
    bool isEmpty() {
        return queSize == 0;
    }


    /* 入队 */
    void push(int num) {
        // 在尾节点后添加 num
        ListNode *node = new ListNode(num);
        // 如果队列为空，则令头、尾节点都指向该节点
        if (front == nullptr) {
            front = node;
            rear = node;
        }
        // 如果队列不为空，则将该节点添加到尾节点后
        else {
            rear->next = node;
            rear = node;
        }
        queSize++;
    }


    /* 出队 */
    int pop() {
        int num = peek();
        // 删除头节点
        ListNode *tmp = front;
        front = front->next;
        // 释放内存
        delete tmp;
        queSize--;
        return num;
    }


    /* 访问队首元素 */
    int peek() {
        if (size() == 0)
            throw out_of_range("队列为空");
        return front->val;
    }


    /* 将链表转化为 Vector 并返回 */
    vector<int> toVector() {
        ListNode *node = front;
        vector<int> res(size());
        for (int i = 0; i < res.size(); i++) {
            res[i] = node->val;
            node = node->next;
        }
        return res;
    }
};
基于数组的实现
跳转到“基于数组的实现”

在数组中删除首元素的时间复杂度为 O(n) ，这会导致出队操作效率较低。然而，我们可以采用以下巧妙方法来避免这个问题。

我们可以使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义 rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置。

基于此设计，数组中包含元素的有效区间为 [front, rear - 1]，各种操作的实现方法如图 5-6 所示。

  • 入队操作：将输入元素赋值给 rear 索引处，并将 size 增加 1 。
  • 出队操作：只需将 front 增加 1 ，并将 size 减少 1 。

可以看到，入队和出队操作都只需进行一次操作，时间复杂度均为 O(1) 。

ArrayQueuepush()pop()
image-20240329235557308image-20240329235612217image-20240329235624674

你可能会发现一个问题：在不断进行入队和出队的过程中，front 和 rear 都在向右移动，当它们到达数组尾部时就无法继续移动了。为了解决此问题，我们可以将数组视为首尾相接的“环形数组”。

对于环形数组，我们需要让 front 或 rear 在越过数组尾部时，直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现，代码如下所示：

/* 基于环形数组实现的队列 */
class ArrayQueue {
  private:
    int *nums;       // 用于存储队列元素的数组
    int front;       // 队首指针，指向队首元素
    int queSize;     // 队列长度
    int queCapacity; // 队列容量


  public:
    ArrayQueue(int capacity) {
        // 初始化数组
        nums = new int[capacity];
        queCapacity = capacity;
        front = queSize = 0;
    }


    ~ArrayQueue() {
        delete[] nums;
    }


    /* 获取队列的容量 */
    int capacity() {
        return queCapacity;
    }


    /* 获取队列的长度 */
    int size() {
        return queSize;
    }


    /* 判断队列是否为空 */
    bool isEmpty() {
        return size() == 0;
    }


    /* 入队 */
    void push(int num) {
        if (queSize == queCapacity) {
            cout << "队列已满" << endl;
            return;
        }
        // 计算队尾指针，指向队尾索引 + 1
        // 通过取余操作实现 rear 越过数组尾部后回到头部
        int rear = (front + queSize) % queCapacity;
        // 将 num 添加至队尾
        nums[rear] = num;
        queSize++;
    }


    /* 出队 */
    int pop() {
        int num = peek();
        // 队首指针向后移动一位，若越过尾部，则返回到数组头部
        front = (front + 1) % queCapacity;
        queSize--;
        return num;
    }


    /* 访问队首元素 */
    int peek() {
        if (isEmpty())
            throw out_of_range("队列为空");
        return nums[front];
    }


    /* 将数组转化为 Vector 并返回 */
    vector<int> toVector() {
        // 仅转换有效长度范围内的列表元素
        vector<int> arr(queSize);
        for (int i = 0, j = front; i < queSize; i++, j++) {
            arr[i] = nums[j % queCapacity];
        }
        return arr;
    }
};
队列典型应用
跳转到“队列典型应用”
  • 淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。
  • 各类待办事项。任何需要实现“先来后到”功能的场景，例如打印机的任务队列、餐厅的出餐队列等，队列在这些场景中可以有效地维护处理顺序。