C语言数据结构之链队列的基本操作
时间：2022-05-24 09:36:04 | 栏目：C代码 | 点击：次
1.队列的定义
队列 (Queue)是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出(Fist In Fist Out，缩写为FIFO)的特性。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。 假设队列为q=(a1，a2，…，an)，那么a1就是队头元素，an则是队尾元素。队列中的元素是按照a1、a2、…、an的顺序进入的， 退出队列也必须按照同样的次序依次出队，也就是说，只有在a1、a2、…、an-1都离开队列之后，an才能退出队列。
2.队列的表示和实现
链队列可以定义如下：
＃define TRUE 1
＃define FALSE 0
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
（1） 初始化操作
Status InitQueue(LinkQueue &Q)
{
Q.front = Q.rear = (Queueptr) malloc(sizeof(QNode));
if(!Q.front) exit ( OVERFLOW);
Q.front ->next = NULL;
return OK;
}
（2）销毁队列
Status DestroyQueue(LinkQueue &Q)
{
while(Q.front) {
Q.rear = Q.front->next;
free (Q.front);
Q.front = Q.rear;
}
return OK;
}
（3） 入队操作
Status EnQueue (LinkQueue &Q, QelemType e)
{
p= (QueuePtr) malloc(sizeof(QNode));
if (!p) exit ( OVERFLOW);
p->data = e; p->next = NULL;
Q.rear -> next =p;
Q.rear = p;
return OK;
}
（4） 出队操作
Status DeQueue (LinkQueue &Q, QelemType &e)
{
if ( Q.front == Q.rear) return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next =p->next;
if (Q.rear == p) Q.rear = Q.front;
free(p);
return OK;
}
附录完整代码：
#include<iostream>
using namespace std;
#define OK 1
#define FALSE 0
typedef int QElemType;
typedef int Status;
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr font;
QueuePtr near;
}LinkQueue;
Status InitQueue(LinkQueue &Q)
{
Q.font=(QueuePtr)malloc(sizeof(QNode));
if(!Q.font) exit(FALSE);
Q.font->next=NULL;
Q.near=Q.font;
return OK;
}
Status QueueEmpty(LinkQueue Q)
{
if(Q.font->next) return OK;
return FALSE;
}
Status EnQueue(LinkQueue &Q,QElemType e)
{
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
p->data=e;
Q.near->next = p;
Q.near = Q.near->next;
p->next = NULL;
return OK;
}
Status DeQueue(LinkQueue &Q,QElemType &e)
{
if(!Q.font->next) return FALSE;
QueuePtr p;
p=Q.font->next;
e=p->data;
Q.font->next=p->next;
if(Q.near==p) Q.near=Q.font; //当是最后一个元素时，Q.font=NULL,Q.near=Q.font
free(p);
return OK;
}
Status ClearQueue(LinkQueue &Q)
{
QueuePtr p;
p=Q.font->next;
QueuePtr q;
while(p)
{
q=p;
p=p->next;
Q.font->next=p;
free(q);
}
Q.near=Q.font;
return OK;
}
void menu()
{
cout<<"初始化队列:1"<<endl;
cout<<"入队:2"<<endl;
cout<<"出队:3"<<endl;
cout<<"清空队列:4"<<endl;
cout<<"退出:5"<<endl;
}
int main()
{
LinkQueue Q;
while(true)
{
int n;
menu();
scanf("%d",&n);
int e=-1;
switch(n)
{
case 1:
InitQueue(Q);
continue;
case 2:
printf("请输入一个元素");
scanf("%d",&e);
EnQueue(Q,e);
continue;
case 3:
DeQueue(Q,e);
printf("\n出队元素%d\n",e);
continue;
case 4:
ClearQueue(Q);
printf("清空成功\n");
continue;
default:
break;
}
if(n==5)break;
}
}