队列

需熟练掌握队列的定义、操作和实现方式，尤其是循环队列。

定义

队列是一种遵循先入先出 (FIFO, First In First Out) 原则的线性数据结构。元素在队尾添加，在队首删除。

Back
Front
Enqueue
Dequeue

基本操作

  • enqueue(element): 将元素添加到队列的尾部。
  • dequeue(): 从队列的头部移除并返回元素。如果队列为空，此操作可能会返回特定的值或引发错误。
  • front() 或 peek(): 返回队首的元素但不移除它。
  • isEmpty(): 判断队列是否为空。
  • size(): 返回队列中元素的数量。

实现

顺序队列

顺序队列通常是指使用固定大小的数组来存储队列中的元素。在顺序队列中，通常有两个指标：一个是队头（front），另一个是队尾（rear）。当插入（入队）或删除（出队）元素时，这两个指标会移动。

front
rear
front
a
b
c
d
e
rear
front
e
rear
空队
5个元素入队
出队4次
再出队一次
会出现
“假溢出”

顺序队列有一个明显的问题：随着时间的推移，队列中的元素可能向数组的末尾移动，即使队列并不满，也可能无法再插入新的元素，因为队尾已经达到了数组的末尾。这种现象称为"假溢出"。

循环队列

为了解决上述问题，可以使用循环队列（也称为环形队列）。循环队列是顺序队列的一个变种，它把数组视为一个循环的结构。当队尾指标达到数组的最后一个位置并且还需要进一步移动时，它会回到数组的起始位置。

0
1
2
3
4
front
rear
0
1
2
3
4
a
b
c
d
front
rear
队空
入队4个元素，队满

需要注意的是，在循环队列中需要牺牲一个存储单元以区分队空和队满的情况。

  • 当 front == rear 时，队列为空
  • 当 (rear + 1) % size == front 时，队列为满
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front, rear;
} CircularQueue;

// 初始化队列
void initQueue(CircularQueue* q) {
    q->front = q->rear = 0;
}
// 入队操作
bool enqueue(CircularQueue* q, int value) {
    if (isFull(q)) return false;
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return true;
}
// 出队操作
bool dequeue(CircularQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return true;
}
// 获取队首元素
bool front(CircularQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->data[q->front];
    return true;
}

// 获取队尾元素
bool rear(CircularQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->data[(q->rear - 1 + MAX_SIZE) % MAX_SIZE];
    return true;
}
// 判断队列是否为空
bool isEmpty(CircularQueue* q) {
    return q->front == q->rear;
}

// 判断队列是否满
bool isFull(CircularQueue* q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

链式队列

链式队列是使用链表结构来实现的队列。它充分利用了链表的动态性质，允许队列在运行时动态地增长或缩小。链式队列通常有两个指针：一个指向队头，另一个指向队尾。

链式队列通常使用一个简单的单链表来实现，但与普通的单链表不同的是，链式队列有两个指针：一个指向链表的头部（队头），另一个指向链表的尾部（队尾）。

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* front, *rear;
} LinkedQueue;

// 初始化队列
void initLinkedQueue(LinkedQueue* q) {
    q->front = q->rear = NULL;
}
// 入队操作
void enqueueLinked(LinkedQueue* q, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    if(isEmptyLinked(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}
// 出队操作
bool dequeueLinked(LinkedQueue* q, int* value) {
    if (isEmptyLinked(q)) return false;
    Node* temp = q->front;
    *value = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;  // 当队列中最后一个元素被出队后
    free(temp);
    return true;
}
// 获取队首元素
bool frontLinked(LinkedQueue* q, int* value) {
    if (isEmptyLinked(q)) return false;
    *value = q->front->data;
    return true;
}
// 判断队列是否为空
bool isEmptyLinked(LinkedQueue* q) {
    return q->front == NULL && q->rear == NULL;
}