链式队列定义及相关操作的实现
1. 数据元素的表示
typedef struct LinkNode {// 链式队列结点
int data;// 数据域
struct LinkNode* next;// 指针域
}LinkNode;
typedef struct {// 链式队列
LinkNode* front;// 队头指针
LinkNode* rear;// 队尾指针
}LinkQueue;
2. 初始化队列
/* 初始化队列 */
bool InitQueue(LinkQueue& Q) {
LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));// 创建头结点
if (!s) {// 创建头结失败，返回false
return false;
}
Q.front = Q.rear = s;// 队列的头尾指针初始指向头结点
Q.rear->next = NULL;// 初始头结点的指针域为空
return true;
}
3. 判断队空
/* 判队列空 */
bool QueueEmpty(LinkQueue Q) {
return Q.front == Q.rear;// 队列的头尾指针同时指向头结点，队列为空
}
4. 进队操作
/* 进队操作（尾插法） */
bool EnQueue(LinkQueue& Q, int x) {
LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
if (!s) {// 创建新结点失败，返回false
return false;
}
s->data = x;
s->next = Q.rear->next;
Q.rear->next = s;
Q.rear = s;
return true;
}
5. 出队操作
/* 出队操作（头结后删除） */
bool DeQueue(LinkQueue& Q, int &e) {
if (QueueEmpty(Q)) {// 空队列，出队失败，返回false
return false;
}
LinkNode* p = Q.front->next;// p指针指向第一个队列结点（除头结点外）
e = p->data;
Q.front->next = p->next;
if (p == Q.rear) {// 特殊情况:队列中只有一个元素时出队
Q.rear = Q.front;
}
free(p);// 释放该结点的内存空间
return true;
}
6. 读取队首元素
/* 读取队首元素 */
bool GetFront(LinkQueue Q,int &e) {
if (QueueEmpty(Q)) {// 空队列，返回false
return false;
}
e = Q.front->next->data;
return true;
}
7. 打印队列元素
/* 打印队列元素 */
void PrintQueue(LinkQueue Q) {
printf("链式队列(由队首到队尾):");
if (QueueEmpty(Q)) {// 空队列
printf("null\n");
return;
}
LinkNode* p = Q.front->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
8. 验证代码
int main()
{
LinkQueue q;
InitQueue(q);// 初始化队列
PrintQueue(q);
// 进队
for (int i = 1; i <= MaxSize; i++) {
EnQueue(q, i);
}
PrintQueue(q);
// 读取队首元素(队列非空)
int e = 0;
if (GetFront(q, e)) {
printf("读取队首元素成功，队首元素:%d\n", e);
}
// 出队（队列非空）
printf("依次出队:");
while (DeQueue(q, e)) {
printf("%d ", e);
}
printf("\n");
PrintQueue(q);
// 出队（空队列）
if (!DeQueue(q, e)) {
printf("出队失败，空队列\n");
}
// 读取队首元素（空队列）
if (!GetFront(q, e)) {
printf("读取队首元素失败，空队列\n");
}
return 0;
}
原文地址：https://blog.csdn.net/qq_62107003/article/details/137682904
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！