链式队列
链式队列是用链表实现的队列,需要同时维护队头指针和队尾指针。为了操作方便,通常附设一个头结点。
typedef struct LinkNode {
int data;
struct LinkNode *next;
} LinkNode;
typedef struct {
LinkNode *front; // 队头指针
LinkNode *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;
}
入队(尾插法)
bool EnQueue(LinkQueue &Q, int x) {
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
Q.rear->next = s; // 新结点插入到队尾
Q.rear = s; // 更新队尾指针
return true;
}
出队
bool DeQueue(LinkQueue &Q, int &x) {
if (QueueEmpty(Q)) return false;
LinkNode *p = Q.front->next; // p指向队头元素结点
x = p->data;
Q.front->next = p->next; // 头结点指向新的队头
if (Q.rear == p) { // 如果删除的是最后一个元素
Q.rear = Q.front; // 更新队尾指针指向头结点
}
free(p);
return true;
}
链式队列出队时,需要特别注意删除的是最后一个元素的情况!此时队尾指针rear也需要更新,指向头结点,否则rear会成为悬空指针。
时间复杂度:所有操作均为 。
习题 1
最适合用作链队的链表是( )
A. 带队头指针和队尾指针的循环单链表 B. 带队头指针和队尾指针的非循环单链表 C. 只带队头指针的循环单链表 D. 只带队头指针的非循环单链表
解题思路:
本题考查链队底层链表结构的选择。思路是先把队列的两项操作分别列出,指出各自需要哪个指针才能在常数时间内完成,再判断循环结构是否必要。
详细步骤:
- 队列需要在队尾插入(入队)和在队头删除(出队),两个操作分别在链表的两端。
- 有队头指针才能在 时间内完成出队;有队尾指针才能在 时间内完成入队。
- 非循环单链表已经能够满足两端操作的需要,不需要额外维护循环链接;只带一个指针的链表则无法让另一端操作也达到 。
- 因此最适合的是带队头指针和队尾指针的非循环单链表。
最终答案:
B。
习题 2
简述链式队列的出队操作需要注意什么问题?为什么?
解题思路:
本题考查链式队列出队时的边界处理。思路是区分“队列中还有多个元素”和“队列中只剩最后一个元素”两种情形,说明只有后一种情形才需要同步修改队尾指针,并解释不改会产生的后果。
详细步骤:
- 链式队列通常带头结点,front 指向头结点,rear 指向队尾元素结点;出队操作要注意的是删除最后一个元素时必须同时更新 rear,使其指向头结点。
- 当队列中有多个元素时,出队只需修改头结点的 next 指针,rear 指针不受影响。
- 当队列中只有一个元素时,它既是队头也是队尾:删除后头结点的 next 变为 NULL(队空),但 rear 仍指向已被删除的结点,成为悬空指针。
- 若不更新 rear,后续入队会通过 rear->next 插入新结点,而 rear 指向的内存已被释放,会导致内存错误。
- 因此出队时需判断被删结点是否就是 rear 指向的结点,若是则把 rear 更新为指向头结点(与 front 相同),保证队空时 front 与 rear 都指向头结点。
最终答案:
出队时若删除的是队列中的最后一个元素,需要同时把队尾指针 rear 更新为指向头结点;否则 rear 会成为指向已释放内存的悬空指针,后续入队将导致内存错误。
