#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef int Status;
typedef int Elemtype;
typedef struct Qnode//链队列结点
{
Elemtype data;
struct Qnode* next;
}Qnode, * QueuePtr;//队列的结点指针
typedef struct//链队列类型
{
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}linkQueue;//链队列
Status InitQueue(linkQueue& Q);//初始化一个带头结点的空队列
Status CreatQueue(linkQueue& Q);//随即输入队列长度和队列整数型数据元素的值，创建一个空对链队列
Status EnQueue(linkQueue& Q, int e);//将一个数插入到队尾（x在程序运行时随即输入）
Status DeQueue(linkQueue& Q);//删除队头元素，并在删除后输出队头元素
Status GetQueue(linkQueue Q);//判断队列是否为空，若不空输出队头元素
Status LenQueue(linkQueue Q);//获得队列的长度
Status PrintQueue(linkQueue Q);//输出队列中的所有元素
int main(void)
{
linkQueue Q;
int x;
int k;
do {
cout << "\n*****链队列相关操作*****";
cout << "\n1.初始化一个带头结点的空队列";
cout << "\n2.随机创建一个非空链队列";
cout << "\n3.将一个数x插入到队尾";
cout << "\n4.将队头元素删除，并输出元素的值";
cout << "\n5.输出队头元素";
cout << "\n6.求栈的长度";
cout << "\n7.输出队列中所有的元素";
cout << "\n0.结束相关操作";
cout << "\n输入想要进行相关操作的序号:";
cin >> k;
switch (k)
{
case 1:
{
if (InitQueue(Q))
cout << "初始化成功。\n" << endl;
else
cout << "初始化失败。\n" << endl;
break;
}
case 2:
{
if (CreatQueue(Q))
{
cout << "创建成功。\n";
}
else
{
cout << "创建失败。\n";
}
break;
}
case 3:
{
cout << "输入想要插入元素的数值x为：";
cin >> x;
if (EnQueue(Q, x)) cout << "插入成功。\n";
else cout << "插入失败。\n";
break;
}
case 4:
{
if (DeQueue(Q)) cout << "删除成功。\n";
else cout << "删除失败。\n";
break;
}
case 5:
{
if (GetQueue(Q)) cout << "输出成功。\n";
else cout << "输出失败。\n";
break;
}
case 6:
{
if (LenQueue(Q)) cout << "长度获取成功。\n";
else cout << "长度获取失败。\n";
break;
}
case 7:
{
if (PrintQueue(Q)) cout << "全部输出成功。\n";
else cout << "全部输出失败。\n";
break;
}
}
} while (k != 0);
return OK;
}
Status InitQueue(linkQueue& Q)
{
Q.front = Q.rear = new Qnode;//生成头结点
Q.front->next = NULL;//头结点指针域置空
return OK;
}
Status CreatQueue(linkQueue& Q)
{
int k = 0;
int t = 0;
QueuePtr p;
cout << "\n队列长度t为:";
cin >> t;
cout << "\n输入正整数值为：";
for (int i = 0; i < t; i++)
{
p = new Qnode;//生成一个新节点，重复使用
cin >> k;
p->data = k;//赋值给结点的数据域
p->next = NULL;//赋值给节点的指针域，每次入队都在队尾
Q.rear->next = p;
Q.rear = p;
}
return OK;
}
Status EnQueue(linkQueue& Q, int e)
{
QueuePtr p;
p = new Qnode;//生成新的节点，用来存放要插入的元素
p->data = e;
p->next = NULL;//插入的元素进入的是该队列的队尾，指针域被赋值为空
Q.rear->next = p;//将该结点插队到原队列队尾的指针域
Q.rear = p;//将尾指针改为插入的指针
return OK;
}
Status DeQueue(linkQueue& Q)
{
if (Q.front == Q.rear) return ERROR;//判断是否为空
QueuePtr p;
p = Q.front->next;//p指向该队列的队头元素，首元节点
int i;
i = p->data;//队头节点的数据域保存
Q.front->next = p->next;//将该队头结点指针域转换为原队列的下一个
if (Q.front == p) Q.rear = Q.front;//最有一个元素被删，队尾指针指向头节点
cout << "删除元素为" << i << endl;
delete p;//释放原队头元素的空间
return OK;
}
Status GetQueue(linkQueue Q)
{
if (Q.front == Q.rear) return ERROR;//判断是否为空
int k = 0;
k = Q.front->next->data;//将队头节点的数据域赋值给k
cout << "输出的队头元素为" << k << endl;
return OK;
}
Status LenQueue(linkQueue Q)
{
int k = 0;
QueuePtr p;
p = Q.front->next;//获取该队列有数据的队头元素
while (p != NULL)//遍历队列
{
k++;
p = p->next;
}
cout << "队列的长度为" << k << endl;
return OK;
}
Status PrintQueue(linkQueue Q)
{
if (Q.front == Q.rear) return ERROR;//判断是否为空
QueuePtr p;
p = Q.front->next;//获取该队列有数据的队头元素
while (p != NULL)
{
cout << p->data << " ";//遍历打印元素
p = p->next;
}
cout << endl;
return OK;
}