队列(Queue)：具有一定操作约束的线性表
插入和删除操作：只能在一端插入，而在另一端删除
队列的顺序存储实现
1. 定义
> 队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成
#define MaxSize <存储数据元素的最大个数>
struct QNode {
ElementType Data[MaxSize];
int rear;
int front;
};
typedef struct QNode* Queue;
2. 循环队列入队
void AddQ(Queue PtrQ, ElementType item) {
if ((PtrQ->rear + 1) % MaxSize == PtrQ->front) {
printf("队列满");
return;
}
PtrQ->rear = (PtrQ->rear + 1) % MaxSize;
PtrQ->Data[PtrQ->rear] = item;
}
3. 循环队列出队
ElementType DeleteQ(Queue PtrQ) {
if (PtrQ->front == PtrQ->rear) {
printf("队列空");
return ERROR;
}
else {
PtrQ->front = (PtrQ->front + 1) % MaxSize;
return PtrQ->Data[PtrQ->front];
}
}
队列的链式存储实现
1. 定义
struct Node {
ElementType Data;
struct Node* Next;
};
struct QNode {
struct Node* rear; //指向队尾节点
struct Node* front; //指向队头节点
};
typedef struct QNode* Queue;
2. 不带头结点的链式队列出队
ElementType DeleteQ(Queue PtrQ) {
struct Node* FrontCell;
ElementType FrontElem;
if (PtrQ->front == NULL) {
printf("队列空");
return ERROR;
}
FrontCell = PtrQ->front;
if (PtrQ->front == PtrQ->rear)
PtrQ->front = NULL;
else
PtrQ->front = FrontCell->Next;
FrontElem = FrontCell->Data;
free(FrontCell);
return FrontElem;
}
