《数据结构（C语言版）》链队列的实现
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟民 编著
数据结构（C语言版）
以下是本人对该紫皮书第三章栈和队列中链队列的代码实现，即课本3.4.2节队列的链式表示和实现，并处理了非法输入字母等问题。
（貌似专栏把我缩进吃了，懒得加了，另外建议用visual studio编译）
代码如下：
/*带头结点的队列的链式表示和实现*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXQSIZE 100
typedef int Status;
typedef int QElemType;
typedef struct QNode
{
QElemType data;
struct QNode* next;
}QNode, * QueuePtr;
typedef struct
{
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;
Status InitQueue(LinkQueue& Q);//链队列的初始化
Status DestoryQueue(LinkQueue& Q);//销毁队列
Status EnQueue(LinkQueue& Q, QElemType e);//入队
Status DeQueue(LinkQueue& Q, QElemType& e);//出队
Status GetHead(LinkQueue Q, QElemType& e);//获取队头元素
void Menu()
{
printf("***************************\n");
printf("********0：退出系统********\n");
printf("********1：元素入队********\n");
printf("********2：元素出队********\n");
printf("********3：求队头值********\n");
printf("***************************\n");
}
int main()
{
int option;
int value;
LinkQueue MyQueue;
InitQueue(MyQueue);
Menu();
printf("请输入你想使用的功能：");
while (scanf("%d", &option) != EOF)
{
while (getchar() != '\n');
switch (option)
{
case 1:
printf("请输入你想入队的元素：");
while (scanf("%d", &value) != 1)
{
while (getchar() != '\n');
printf("非法输入，请重试\n");
}
if (EnQueue(MyQueue, value))
{
printf("入队成功！\n");
}
else
{
printf("队列的最大长度为%d,队列已满！\n", MAXQSIZE - 1);
}
break;
case 2:
if (DeQueue(MyQueue, value))
{
printf("元素%d出队成功!\n", value);
}
else
{
printf("队空，无元素可出队\n");
}
break;
case 3:
if (GetHead(MyQueue, value))
{
printf("队头元素为%d\n", value);
}
else
{
printf("队空，无队头元素\n");
}
break;
case 0:
printf("感谢使用！\n");
exit(0);
default:
printf("非法输入，请重试\n");
}
Menu();
printf("请输入你想使用的功能：");
}
return 0;
}
Status InitQueue(LinkQueue& Q)//链队列的初始化
{
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q.front)
{
exit(OVERFLOW);
}
Q.front->next = NULL;
return OK;
}
Status DestoryQueue(LinkQueue& Q)//销毁队列
{
while (Q.front)
{
Q.rear = Q.front->next;
free(Q.front);
Q.front = Q.rear;
}
return OK;
}
Status EnQueue(LinkQueue& Q, QElemType e)//入队
{
QNode* p = (QueuePtr)malloc(sizeof(QNode));
if (!p)
{
exit(OVERFLOW);
}
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
Status DeQueue(LinkQueue& Q, QElemType& e)//出队
{
if (Q.front == Q.rear)
{
return ERROR;
}
QNode* p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)//注意这里要考虑到,当队列中最后一个元素被删后，队列尾指针也丢失了，因此需对队尾指针重新复制(指向头结点)
{
Q.rear = Q.front;
}
free(p);
return OK;
}
Status GetHead(LinkQueue Q, QElemType& e)//获取队头元素
{
if (Q.front == Q.rear)
{
return ERROR;
}
e = Q.front->next->data;
}
