队列
队列(Queue)是有限个同类型数据元素的线性序列,是一种 先进先出 的线性表,新加入的数据元素插在队列尾端,出队列的数据元素在队列首部被删除。
队列的顺序实现
// 顺序队列的类型定义
const int Maxsize = 20;
typedef struct seqqueue
{
DataType data[Maxsize];
int front, rear; // front 指向队列首元素的前一个单元,rear 指向实际的队列尾元素单元。
} SeqQue;
SeqQue SQ;
// 入队列操作
SQ.rear = SQ.rear + 1;
SQ.data[SQ.rear] = x;
// 出队列操作
SQ.front = SQ.front + 1;
// 循环队列的类型定义
typedef struct cycqueue
{
DataType data[Maxsize];
int front,rear;
} CycQue;
CycQue CQ; // 循环队列解决了“假上溢”问题
// 循环队列的入队列操作
CQ.rear = (CQ.rear + 1) % Maxsize;
CQ.data[CQ.rear] = x;
// 出队列操作
CQ.front = (CQ.front + 1) % Maxsize;
// 队列满条件:为了区分队列空条件,队列少用一个元素空间,当只剩下一个单元时就认为队列满,此时,队列尾指针只差一步将追上队列首指针。
((CQ.rear + 1) % Maxsize == CQ.front) 成立
// 队列空条件
(CQ.rear == CQ.front) 成立
// 队列的初始化
void InitQueue(CycQue *CQ)
{
CQ->front = 0;
CQ->rear = 0;
}
// 判队列空
int EmptyQueue(CycQue *CQ)
{
// 队列为空,返回 1
if (CQ->rear == CQ->front)
return 1;
else
return 0;
}
// 入队列
int EnQueue(CycQue *CQ, DataType x)
{
if ((CQ->rear + 1) % Maxsize == CQ->front) {
error("队列满");
return 0;
} else {
CQ->rear = (CQ->rear + 1) % Maxsize;
CQ->data[CQ->rear] = x;
return 1;
}
}
// 出队列
int OutQueue(CycQue *CQ)
{
if (EmptyQueue(CQ)) {
error("队列空");
return 0;
} else {
CQ->front = (CQ->front + 1) % Maxsize;
return 1;
}
}
// 取队列首元素
DataType GetHear(CycQue *CQ)
{
if (EmptyQueue(CQ))
return NULLData; // 返回空数据标志
else
return CQ->data[(CQ->front + 1) % Maxsize];
}
队列的链接实现
// 链队列的类型定义
typedef struct LinkQueueNode
{
DataType data;
struct LinkQueueNode *next;
} LkQueNode;
typedef struct LkQueue
{
LkQueNode *front, *rear; // 队列头指针和尾指针。头指针指向链表的头结点,头结点的 next 域指向队列首结点,尾指针指向队列尾结点,即单链表的最后一个结点。
} LkQue;
LkQue LQ;
// 队列的初始化
void InitQueue(LkQue *LQ)
{
LkQueNode *temp;
temp = (LkQueNode *)malloc(sizeof(LkQueNode)); // 生成队列的头结点
LQ->front = temp; // 队列头指针指向队列头结点
LQ->rear = temp; // 队列尾指针指向队列尾结点
(LQ->front)->next = NULL;
}
// 判队列空
int EmptyQueue(LkQue *LQ)
{
if (LQ->rear == LQ->front)
return 1;
else
return 0;
}
// 入队列
void EnQueue(LkQue *LQ, DataType x)
{
LkQueNode *temp;
temp = (LkQueNode *)malloc(sizeof(LkQueNode));
temp->data = x;
temp->next = NULL;
(LQ->rear)->next = temp; // 新结点入队列
LQ->rear = temp; // 置新的队列尾结点
}
// 出队列
int OutQueue(LkQue *LQ)
{
LkQueNode *temp;
if (EmptyQueue(LQ)) {
error("队列空");
return 0;
} else {
temp = (LQ->front)->next; // 使 temp 指向队列的首结点
(LQ->front)->next = temp->next; // 修改头结点的指针域指向新的首结点
if (temp->next == NULL) {
LQ->rear = LQ->front; // 无首结点时,front 和 rear 都指向头结点
}
free(temp);
return 1;
}
}
// 取队列首元素
DataType GetHead(LkQue *LQ)
{
LkQueNode *temp;
if (EmptyQueue(LQ)) {
return NULLData;
} else {
temp = (LQ->front)->next;
return temp->data; // 返回队列首结点元素,即头结点的指针域指向的结点
}
}