Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/7.队列.md

7. 队列

概念

队列（Queue） 是一种受限制的线性表，只允许在队尾（rear） 进行插入（入队），在队头（front） 进行删除（出队），遵循先进先出（FIFO, First In First Out） 的原则，类似现实中排队。

从逻辑结构上看，队列也是线性表，元素存在一对一的前驱后继关系，只是操作受限在两端，因此也是操作受限的线性表。

根据存储结构不同，队列分为两种：

1. 循环队列（顺序存储）：用一段连续内存（数组） 存储元素，并用 front、rear 两个指针分别指向队头和队尾。

   • 为避免"假溢出"，通常把数组看作环形，用取模运算 (rear + 1) % MAXSIZE 使指针循环移动。

2. 链队列（链式存储）：用带头结点的单链表实现，队头指针指向头结点的后继，队尾指针指向最后一个结点。

为什么顺序队列会"假溢出"？ 如果用普通数组实现队列，随着元素不断入队出队，front 和 rear 都会向数组尾部移动。当 rear 到达数组末尾时，即使数组前面还有很多空闲空间，也无法再入队，这就是"假溢出"。解决办法是把数组首尾相接形成环形，让 rear 和 front 通过取模运算循环移动，这就是循环队列。取模运算 (i + 1) % MAXSIZE 的意义在于：当指针到达数组末尾时，自动回绕到开头，实现逻辑上的循环。

循环队列判空判满的几种方法：

1. 牺牲一个存储单元：约定 front == rear 为空，(rear + 1) % MAXSIZE == front 为满。数组实际能存放 MAXSIZE-1 个元素。这是最常见的做法。
2. 增设 size 计数器：记录当前元素个数，size == 0 为空，size == MAXSIZE 为满。
3. 增设 tag 标志位：记录最后一次操作是入队还是出队，配合 front == rear 区分空与满。

方法 1 实现简单、是教材主流；方法 2 直观易理解；方法 3 不浪费空间但稍复杂。

适用场景：任务调度、缓冲区（生产者-消费者）、打印队列、广度优先搜索（BFS）、消息队列、操作系统进程就绪队列等。

核心操作

操作	说明
InitQueue 初始化	建立空队列，front = rear = 0
QueueEmpty 判空	判断队列是否为空
QueueFull 判满	判断队列是否已满（循环队列）
EnQueue 入队	在队尾插入一个元素
DeQueue 出队	删除队头元素并返回
GetFront 取队头	读取队头元素但不删除

复杂度分析

操作	循环队列时间复杂度	链队列时间复杂度	空间复杂度
初始化	O(1)	O(1)	O(n) / O(1)
判空/判满	O(1)	O(1)	O(1)
EnQueue 入队	O(1)	O(1)	O(n)
DeQueue 出队	O(1)	O(1)	O(1)
GetFront 取队头	O(1)	O(1)	O(1)

为什么： 队列的操作被严格限制在队头和队尾两端，无论循环队列还是链队列，入队、出队、取队头都只需常数次操作（取模、指针移动、链表头尾操作），不涉及元素移动，因此都是 O(1)。

空间方面：循环队列需要预分配整块连续空间 O(n)，且可能造成少量空间浪费（牺牲一个单元）；链队列按需分配结点，总空间 O(n) 但不会浪费、也不会溢出。

语言实现

C/C++/Java 使用循环数组队列（采用"牺牲一个存储单元"的方法判空判满）；Python 用 collections.deque 实现（双向队列，天然适合做队列），并说明对比。四种实现演示相同的入队、出队、取队头操作。

C

#include <stdio.h>
#include <stdbool.h>

#define MAXSIZE 100   // 实际最多可存 MAXSIZE-1 个元素

typedef struct {
    int data[MAXSIZE];
    int front;        // 队头指针（指向队头元素）
    int rear;         // 队尾指针（指向队尾元素的下一个位置）
} SqQueue;

// 初始化
void InitQueue(SqQueue *q) {
    q->front = 0;
    q->rear = 0;
}

// 判空：front == rear
bool QueueEmpty(SqQueue *q) {
    return q->front == q->rear;
}

// 判满：(rear+1)%MAXSIZE == front，牺牲一个单元
bool QueueFull(SqQueue *q) {
    return (q->rear + 1) % MAXSIZE == q->front;
}

// 入队
bool EnQueue(SqQueue *q, int x) {
    if (QueueFull(q)) {
        printf("队列已满\n");
        return false;
    }
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAXSIZE;   // 取模回绕
    return true;
}

// 出队
bool DeQueue(SqQueue *q, int *x) {
    if (QueueEmpty(q)) {
        printf("队列为空\n");
        return false;
    }
    *x = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE; // 取模回绕
    return true;
}

// 取队头
bool GetFront(SqQueue *q, int *x) {
    if (QueueEmpty(q)) {
        printf("队列为空\n");
        return false;
    }
    *x = q->data[q->front];
    return true;
}

int main() {
    SqQueue q;
    InitQueue(&q);
    int x;

    // 入队 1 2 3
    EnQueue(&q, 1);
    EnQueue(&q, 2);
    EnQueue(&q, 3);

    GetFront(&q, &x);
    printf("队头元素: %d\n", x);   // 1

    // 出队，直到队空
    while (!QueueEmpty(&q)) {
        DeQueue(&q, &x);
        printf("出队: %d\n", x);    // 1 2 3
    }
    return 0;
}

C++

#include <iostream>
using namespace std;

const int MAXSIZE = 100;   // 实际最多可存 MAXSIZE-1 个元素

// 循环队列，采用"牺牲一个存储单元"判空判满
template <typename T>
class SqQueue {
private:
    T data[MAXSIZE];
    int front;   // 队头
    int rear;    // 队尾
public:
    SqQueue() { front = 0; rear = 0; }

    bool empty() const { return front == rear; }

    bool full() const { return (rear + 1) % MAXSIZE == front; }

    // 入队
    bool enqueue(const T &x) {
        if (full()) return false;
        data[rear] = x;
        rear = (rear + 1) % MAXSIZE;   // 取模回绕
        return true;
    }

    // 出队
    bool dequeue(T &x) {
        if (empty()) return false;
        x = data[front];
        front = (front + 1) % MAXSIZE; // 取模回绕
        return true;
    }

    // 取队头
    bool front(T &x) const {
        if (empty()) return false;
        x = data[front];
        return true;
    }
};

int main() {
    SqQueue<int> q;
    int x;

    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);

    q.front(x);
    cout << "队头元素: " << x << endl;   // 1

    while (!q.empty()) {
        q.dequeue(x);
        cout << "出队: " << x << endl;     // 1 2 3
    }
    return 0;
}

Java

// 循环队列，采用"牺牲一个存储单元"判空判满
public class SqQueue<T> {
    private static final int MAXSIZE = 100;  // 实际最多可存 MAXSIZE-1 个元素
    private Object[] data;
    private int front;   // 队头
    private int rear;    // 队尾

    public SqQueue() {
        data = new Object[MAXSIZE];
        front = 0;
        rear = 0;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (rear + 1) % MAXSIZE == front;
    }

    // 入队
    public boolean enqueue(T x) {
        if (isFull()) return false;
        data[rear] = x;
        rear = (rear + 1) % MAXSIZE;   // 取模回绕
        return true;
    }

    // 出队
    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) throw new RuntimeException("队列为空");
        T x = (T) data[front];
        front = (front + 1) % MAXSIZE; // 取模回绕
        return x;
    }

    // 取队头
    @SuppressWarnings("unchecked")
    public T getFront() {
        if (isEmpty()) throw new RuntimeException("队列为空");
        return (T) data[front];
    }

    public static void main(String[] args) {
        SqQueue<Integer> q = new SqQueue<>();
        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);

        System.out.println("队头元素: " + q.getFront());   // 1

        while (!q.isEmpty()) {
            System.out.println("出队: " + q.dequeue());     // 1 2 3
        }
    }
}

Python

Python 推荐使用标准库 collections.deque（双端队列），它是用双向链表实现的，两端的插入删除都是 O(1)，非常高效。它既可以当队列用（popleft 出队），也可以当栈用。

from collections import deque


class Queue:
    """基于 deque 的队列封装"""

    def __init__(self):
        self.data = deque()

    def is_empty(self):
        return len(self.data) == 0

    def enqueue(self, x):
        """入队：从队尾添加"""
        self.data.append(x)

    def dequeue(self):
        """出队：从队头弹出"""
        if self.is_empty():
            raise IndexError("队列为空")
        return self.data.popleft()

    def get_front(self):
        """取队头"""
        if self.is_empty():
            raise IndexError("队列为空")
        return self.data[0]

    def __len__(self):
        return len(self.data)

    def __str__(self):
        return f"Queue({list(self.data)})"


if __name__ == "__main__":
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)

    print("队头元素:", q.get_front())   # 1
    print("队列长度:", len(q))

    while not q.is_empty():
        print("出队:", q.dequeue())     # 1 2 3

说明：上面的 Python 实现用 deque，比手写循环数组更简洁、更 Pythonic。若想体验循环队列的取模逻辑，也可以仿照 C/Java 用一个列表和 front、rear 指针实现循环数组队列，逻辑完全相同，这里不再重复。