队列链式存储
头指针指向队头结点，尾指针指向队尾结点。
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode, *LinkPtr;
typedef struct
{
LinkNode *front;
LinkNode *rear;
} LinkQueue;
初始化
通常将链式队列设计成一个带头结点的单链表，可统一插入和删除操作。
void InitQueue(LinkQueue &Q)
{
Q.front = Q.rear = (LinkPtr)malloc(sizeof(LinkNode));//建立头结点
Q.front->next = NULL;
}
判空
Status IsEmpty(LinkQueue Q)
{
if(Q.rear == Q.front)
return TRUE;
return FALSE;
}
入队
不存在队列满且产生溢出的问题
void Enqueue(LinkQueue &Q, ElemType x)
{
LinkPtr s = (LinkPtr)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
Q.rear->next = s;
Q.rear = s;
}
出队
一般出队仅需操作队头指针，但当队列仅有一个元素时，需要同时操作队头和队尾。
Status DeQueue(LinkQueue &Q, ElemType &x)
{
if(Q.rear == Q.front)
return FALSE;
LinkPtr s = Q.front->next;
x = s->data;
Q.front->next = s->next;
if(Q.rear == s) //若原队列中只有一个结点,删除后变空
Q.rear = Q.front;
free(s);
return TRUE;
}
