算法笔记p251队列&循环队列

队列

• 队列是一种先进先出的数据结构，总是从队尾加入元素，从队首移除元素，满足先进先出的原则。
• 队列的常用操作包括获取队列内元素的个数（size）、判空（empty）、入队（push）、出队（pop）、取队首元素（get_front）、取队尾元素（get_rear）等。

循环队列

• 循环队列允许队列的头尾相接，形成一个环。
• 用数组实现循环队列，队头指针front指向队列第一个元素，队尾指针rear指向最后一个元素的下一个位置。
• 由于是循环队列，因此队头指针和队尾指针每次移动都需要对数组长度取余，以确保移动到正确的位置上。
  • 后移：rear = （rear + 1）% MaxSize
  • 前移：rear = （rear + MaxSize - 1）% MaxSize

如上图所示，MaxSize = 6，rear当前指向5的位置：

• 后移：rear = （5 + 1）% 6 = 0
• 前移：rear = （5 + 6 - 1）% 6 = 4

循环队列的定义

#include <stdbool.h>

#define MaxSize 1000

typedef int ElemType;

typedef struct Queue {
    ElemType data[MaxSize];
    int front, rear;
} Queue;

初始化

循环队列初始化时，front和rear都指向数组的第一个位置。

void init(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

判空

队尾指针rear和队头指针front指向同一个地方，即队列为空。

bool empty(Queue *q) {
    return q->front == q->rear;
}

判满

队尾指针的下一个位置指向的是队头指针，则队满。（空出一个元素）

bool full(Queue *q) {
    return (q->rear + 1) % MaxSize == q->front;
}

入队

入队先判满。
由于队尾指针指向队列最后一个元素的下一个位置，因此入队时，先把元素存放到rear指向的位置，然后再将rear + 1。

bool push(Queue *q, ElemType value) {
    if (full(q))
        return false;
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MaxSize;
    return true;
}

出队

出队先判空
由于队头指针指向队列第一个元素，因此出队时，先记录front指向位置的元素，然后再将front + 1。

bool pop(Queue *q, ElemType *p) {
    if (empty(q))
        return false;
    *p = q->data[q->front];
    q->front = (q->front + 1) % MaxSize;
    return true;
}

获取队列内元素的个数

队列内元素的个数：（rear + MaxSize - front）% MaxSize

int size(Queue *q) {
    return (q->rear + MaxSize - q->front) % MaxSize;
}

取队首元素

取队首元素先判空。
将front指针所在位置的元素记录下来即可。

bool get_front(Queue *q, ElemType *value) {
    if (empty(q))
        return false;
    *value = q->data[q->front];
    return true;
}

取队尾元素

取队尾元素先判空。
将rear指针所在位置的前一个位置的元素记录下来即可。

bool get_rear(Queue *q, ElemType *value) {
    if (empty(q))
        return false;
    int pos = (q->rear + MaxSize - 1) % MaxSize;
    *value = q->data[pos];
    return true;
}