int IsemptyQueue(Queue p)
{
if (p.front == p.rear) /* 队首指针和队尾指针重合队列为空 */
{
return Empty;
}
else
{
return NoEmpty;
}
}
出队时队首指针的位置是不变的，队首指针始终指向头节点，出队时头节点的指针域指向出队节点的后一节点，并将出队的节点用free（）函数释放掉，为了方便读者理解下面上图
出队实现代码
Queue DeletNode (Queue p)
{
Node *del;
if (IsemptyQueue(p) == Empty) /* 判断队列是否为空*/
{
printf("队列为空,无法出队 ");
return p;
}
else /* 队列不为空 */
{
if (p.front->next == p.rear) /* 如果出队的节点为最后一个节点 */
{
printf("出队节点的数据为%d----", p.rear->data);
free(p.rear); /* 释放最后一一个节点*/
p.rear = p.front; /* 队首指针和队尾指针都指向头节点 */
p.front->next = NULL;
p.length--;
}
else
{
del = p.front->next;
printf("出队节点的数据为%d----", del->data);
p.front->next = p.front->next->next; /* 使头节点的指针域指向出队节点的下一个节点 */
free(del); /* 释放出队的节点 */
p.length--;
}
return p;
}
}
顺序队列和链式队列首尾指针的比较
1.顺序队列是用数组实现的，首指针在出队的时候移动，尾指针在入队的时候移动，需要考虑队列为空和队列为满的两种情况
2.链式队列是用链表实现的，首指针不移动始终指向头节点，尾指针在入队的时候移动，只考虑队列为空的情况（不用考虑满是因为链表长度在程序运行过程中可以不断增加，只要存储空间够malloc就能申请内存空间来存放节点）
下面附上完整代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Empty 0 /* 队列为空 */
#define NoEmpty 1 /* 队列不为空*/
typedef struct QNode /* 声明链式队列的结点 */
{
int data;
struct QNode *next;
}Node;
typedef struct QueuePoint /* 声明链式队列的首尾指针 */
{
Node *front;
Node *rear;
int length; /* 记录链式队列长度 */
}Queue;
void DisplyNode (Queue p); /* 打印队列 */
Queue init (Queue p); /* 初始化队列 */
Queue AppendNode (Queue p); /* 入队 */
Queue DeletNode (Queue p); /* 出队 */
int IsemptyQueue (Queue p); /* 判断队列是否为空*/
main()
{
int i = 0;
char c;
Queue q; //链式队列首尾指针 和 长度
q.front = q.rear = NULL; /* 首尾指针初始化 */
q.length = 0; /* 链式队列长度初始化 */
q = init(q); /* 初始化队列 */
printf("Do you want to append a new node(Y/N)?");
scanf_s(" %c", &c);
while (c == 'Y' || c == 'y')
{
q = AppendNode(q); /* 入队 */
DisplyNode(q); /* 按先进先出对队列进行打印 */
printf("Do you want to append a new node(Y/N)?");
scanf_s(" %c", &c);
}
printf("Do you want to delete node(Y/N)?");
scanf_s(" %c", &c);
while (c == 'Y' || c == 'y')
{
q = DeletNode(q); /* 出队 */
DisplyNode(q); /* 按先进先出对队列进行打印 */
printf("Do you want to delete node(Y/N)?");
scanf_s(" %c", &c);
}