|
1.队列既可以用链表实现，也可以用顺序表实现。跟栈相反的是，栈一般用顺序表来实现，而队列我们常用链表来实现，称为链队列，它是后入前出(头结点进，尾结点出)，头结点不存元素
实现代码：
typedef struct QNode//定义队列的链表结点
{
ElemType data;
struct QNode *next;
}QNode,*QueuePrt;
typedef struct
{
QueuePrt front,rear;//队头，尾指针
}LinkQueue;
代码思路：队列数据结构的定义和链表是一样的，然后再定义一个队列头尾指针。
2.创建一个队列要完成两个任务：一是在内存中创建一个头结点，二是将队列的头指针和尾指针都指向这个生成的头结点，因为此时是空队列
实现代码：
initQueue(LinkQueue *q)
{
q->front=q->rear=(QueuePtr)malloc(sizeof(QNode));
if(!q->front)
exit(0);
q->front->next = NULL;
}
代码思路：用malloc函数新开一个内存空间，然后头指针和尾指针都等于它，尾指针下一个为空
3.入队列操作
insertQueue(LinkQueue *q,ElemType e)
{
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if(p==NULL)
exit(0);
p->data = e;
p-next = NULL;
q->rear->next = p;
q->rear = p;
}
代码思路：新建一个结点，把为结点的下一个给它就行。
4.出队列操作是将队列中的第一个元素移出，队头指针不发生变化，改变头结点的next指针即可。
代码实现：
deleteQueue(LinkQueue *q,ElemType e)
{
QNode p;
if(q->front == q->rear)
{
return;
}
p = q->front->next;
e = p->data;
q->front->next = p->next;
if(q->rear==p)
{
q->front = q->rear;
}
free§;
}
代码思路：链队列是先入先出，所以删除的话应该是从头结点的下一个删除，因为头结点只是个标识，下一个才是链表第一个结点。所以新建一个结点对象，把第一个结点给新建的结点，值也给它，然后让头结点的下一个等于第一个结点的下一个，然后free就行。注意，如果把队列中只剩一个结点的情况也得判断下。
5.销毁一个队列：由于链队列建立在内存的动态区，因此当一个队列不再有用时应当把它及时销毁掉，以免过多占用内存空间。
代码实现：
destoryQueue(LinkQueue *q)
{
while(q->front)
{
if(q->rear==q->front->next)
{
free(q->front);
q->front = q->rear;
}
}
}
代码思路：当尾结点的指针等于头结点指针的下一个时，删除尾结点指针就行，就算是队列销毁了，有人会问头指针等于尾指针不行吗，当然，两个相等是队列为空，而不是销毁队列。
|