队列的链式存储结构
标签（空格分隔）： DS 队列 链式存储
1.链队列的结构
//节点结构
typedef struct QNode
{
int data;
struct QNode* next;
}QNode,* QueuePtr;
//队列的链表结构
typedef struct
{
QueuePtr front,rear;//front指向头节点，rear指尾节点
}* LinkQueue;
2.链队列的入队操作
思路：
在链表尾部插入新节点，即尾插法
Status EnQueue(LinkQueue Q, int e)
{
//申请新节点
QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
if(!s)
exit(OVERFLOW);//存储分配失败
//新节点赋值
s->data=e;
s->next=NULL;
//尾插法
Q->rear->next=s;
//rear指向新的尾节点
Q->rear=s;
return OK;
}
3.链队列的出队操作
思路:
1.判断队列是否已空
2.若不空，则将Q->front->next指向的节点即第一个节点出队，用指针e返回其值并释放其空间
3.若出队后队列空了，则将尾指针指向头节点，rear==front
Status DeQueue(LinkQueue Q, int* e)
{
if(Q->front==Q->rear)
return ERROR;
QueuePtr p=Q->front->next;
*e=p->data;
Q->front->next=p->next;
if(p==Q->rear)
Q->rear=Q->front;
free(p);
return OK;
}