#include <iostream>
using namespace std;typedef char ElemType;// 链队的节点结构
typedef struct QNode {ElemType data; // 节点存储的元素struct QNode *next; // 指向下一个节点的指针
} QNode;// 链队的结构体（包含队头、队尾指针）
typedef struct {QNode *front; // 队头指针（指向队头节点）QNode *rear; // 队尾指针（指向队尾节点）
} LinkQueue;
// （1）初始化链队
void InitQueue(LinkQueue &q) {q.front = q.rear = NULL; // 队头、队尾指针初始化为空
}
// （2）判断链队是否非空
bool IsNotEmpty(LinkQueue q) {return q.front != NULL; // 队头指针非空则队列非空
}
// （3）入队（元素e插入队尾）
bool EnQueue(LinkQueue &q, ElemType e) {// 创建新节点QNode *newNode = new QNode;if (newNode == NULL) { // 内存分配失败cout << "内存不足，无法入队！" << endl;return false;}newNode->data = e;newNode->next = NULL;if (q.front == NULL) { // 队列为空时，新节点既是队头也是队尾q.front = q.rear = newNode;} else { // 队列非空时，新节点链接到队尾，更新队尾指针q.rear->next = newNode;q.rear = newNode;}return true;
}
// （4）出队（队头元素出队，存入e）
bool DeQueue(LinkQueue &q, ElemType &e) {if (q.front == NULL) { // 队列为空cout << "队列为空，无法出队！" << endl;return false;}QNode *temp = q.front; // 临时保存队头节点e = temp->data; // 取出队头元素q.front = q.front->next; // 队头指针后移if (q.front == NULL) { // 若出队后队列为空，队尾指针也置空q.rear = NULL;}delete temp; // 释放原队头节点return true;
}
// （5）输出队列序列
void PrintQueue(LinkQueue q) {if (q.front == NULL) {cout << "队列为空！" << endl;return;}QNode *p = q.front;cout << "队列序列：";while (p != NULL) { // 从队头遍历到队尾cout << p->data << " ";p = p->next;}cout << endl;
}
// （6）释放链队
void DestroyQueue(LinkQueue &q) {QNode *p = q.front;while (p != NULL) { // 遍历所有节点，逐个释放QNode *temp = p;p = p->next;delete temp;}q.front = q.rear = NULL; // 队头、队尾指针置空cout << "队列已释放！" << endl;
}
// exp3-4.cpp
int main() {LinkQueue q;ElemType e;// （1）初始化链队InitQueue(q);cout << "（1）链队初始化完成" << endl;// （2）判断链队是否非空if (IsNotEmpty(q)) {cout << "（2）当前队列是非空队列" << endl;} else {cout << "（2）当前队列是空队列" << endl;}// （3）依次入队元素a、b、cEnQueue(q, 'a');EnQueue(q, 'b');EnQueue(q, 'c');cout << "（3）元素a、b、c入队完成" << endl;PrintQueue(q);// （4）出队一个元素，输出该元素if (DeQueue(q, e)) {cout << "（4）出队的元素是：" << e << endl;}PrintQueue(q);// （5）依次入队元素d、e、fEnQueue(q, 'd');EnQueue(q, 'e');EnQueue(q, 'f');cout << "（5）元素d、e、f入队完成" << endl;PrintQueue(q);// （6）输出队列序列cout << "（6）";PrintQueue(q);// （7）释放队列DestroyQueue(q);return 0;
}
