队列的基本操作

定义

队列是只允许在一端（队尾）插入，另一端（队头）删除的线性表。

• FIFO：先进先出（First In First Out）
• 队头（Front）：允许删除的一端
• 队尾（Rear）：允许插入的一端

一、顺序队列（循环队列）

问题：假溢出

普通顺序队列中，front 和 rear 不断后移，即使前面有空位也无法使用。

解决：循环队列

将数组首尾相连，形成逻辑上的环。

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int front;  // 队头指针
    int rear;   // 队尾指针
} SqQueue;

初始化

void InitQueue(SqQueue *Q) {
    Q->front = 0;
    Q->rear = 0;
}

判空

bool QueueEmpty(SqQueue Q) {
    return (Q.front == Q.rear);
}

入队

bool EnQueue(SqQueue *Q, ElemType x) {
    if ((Q->rear + 1) % MaxSize == Q->front)  // 队满
        return false;
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MaxSize;
    return true;
}

出队

bool DeQueue(SqQueue *Q, ElemType *x) {
    if (Q->front == Q->rear)  // 队空
        return false;
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MaxSize;
    return true;
}

队列长度

int QueueLength(SqQueue Q) {
    return (Q.rear - Q.front + MaxSize) % MaxSize;
}

判满方法（三种）

方法 1：牺牲一个存储单元

• 队满：$ (rear + 1) \% MaxSize == front $
• 队空：$ front == rear $
• 元素个数：$(rear - front + MaxSize) \% MaxSize$
• 可用空间：$MaxSize - 1$

方法 2：增加 size 变量

typedef struct {
    ElemType data[MaxSize];
    int front, rear, size;
} SqQueue;
// 队空：size == 0
// 队满：size == MaxSize

方法 3：增加 tag 变量

typedef struct {
    ElemType data[MaxSize];
    int front, rear, tag;
} SqQueue;
// 最近操作：tag=1 为入队，tag=0 为出队
// 队空：front == rear 且 tag == 0
// 队满：front == rear 且 tag == 1

二、链队列

typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode;

typedef struct {
    LinkNode *front, *rear;  // 队头队尾指针
} LinkQueue;

初始化（带头结点）

void InitQueue(LinkQueue *Q) {
    Q->front = Q->rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q->front->next = NULL;
}

判空

bool QueueEmpty(LinkQueue Q) {
    return (Q.front == Q.rear);
}

入队（尾插法）

void EnQueue(LinkQueue *Q, ElemType x) {
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q->rear->next = s;
    Q->rear = s;
}

出队

bool DeQueue(LinkQueue *Q, ElemType *x) {
    if (Q->front == Q->rear) return false;
    LinkNode *p = Q->front->next;
    *x = p->data;
    Q->front->next = p->next;
    if (Q->rear == p)  // 若只有一个元素
        Q->rear = Q->front;
    free(p);
    return true;
}

销毁

void DestroyQueue(LinkQueue *Q) {
    while (Q->front != NULL) {
        LinkNode *p = Q->front;
        Q->front = Q->front->next;
        free(p);
    }
}