# 一、队列的抽象数据类型描述
类型名：队列（Queue）
数据对象集：一个有 0 个或多个元素的有穷线性表
操作集：长度为 MaxSize 的堆栈 Q∈Queue, 队列元素 item∈ElementType
1. 生成长度为 MaxSize 的空队列
Queue CreatQueue (int MaxSize);
2. 判断队列 Q 是否已满
bool IsFullQ (Queue Q, int MaxSize);
3. 将数据元素 item 插入队列 Q 中
bool AddQ (Queue Q, ElementType item);
4. 判断队列 Q 是否已空
bool IsEmptyQ (Queue Q);
5. 删除并返回队首元素
ElementType DeleteQ (Queue Q);
# 二、队列的顺序存储实现
# 1. 定义
队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量 front 以及一个记录队列尾元素位置的变量 rear 组成。
形成的数组搬过来，变成一个环，便为循环队列。
为了判断队列的空与满，循环队列仅使用 n-1 个数组空间
![]()
定义代码如下
| typedef struct QNode *Queue; |
| struct QNode { |
| ElementType Data[MaxSize]; |
| int rear; |
| int front; |
| int MaxSize; |
| |
| }; |
# 2. 操作
# (1) 创建循环队列 (CreateQueue)
| Queue CreateQueue( int MaxSize ) { |
| Queue Q = (Queue)malloc(sizeof(struct QNode)); |
| Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType)); |
| Q->front = Q->rear = 0; |
| Q->MaxSize = MaxSize; |
| return Q; |
| } |
# (2) 判断队列是否已满 (IsFull)
| bool IsFull( Queue PtrQ ) { |
| return ((PtrQ->rear+1) % PtrQ->MaxSize == PtrQ->front); |
| } |
# (3) 入队列 (AddQ)
入队时要判断队列是否已满
| bool AddQ(Queue PtrQ, ElementType item) { |
| if ( IsFull(PtrQ) ) { |
| printf("队列满"); |
| return false; |
| } else { |
| PtrQ->rear = (PtrQ->rear+1) % PtrQ->MaxSize; |
| |
| PtrQ->Data[PtrQ->rear] = item; |
| return true; |
| } |
| } |
# (4) 判断队列是否已空 (IsEmpty)
| bool IsEmpty(Queue PtrQ) { |
| return ( PtrQ->front == PtrQ->rear ); |
| } |
# (5) 出队列 (DeleteQ)
出队时判断当前队列是否为空
| ElementType DeleteQ(Queue PtrQ) { |
| if(IsEmpty(PtrQ)) { |
| printf("队列空"); |
| return false; |
| } else { |
| PtrQ->front = (PtrQ->front+1) % PtrQ->MaxSize; |
| return PtrQ->Data[PtrQ->front]; |
| } |
| } |
# 三、队列的链式存储实现
# 1. 定义
队列的链式存储结构也可以用一个单链表实现，插入和删除操作分别在链表的两头进行。队列指针 front 应该指向链表头
![在这里插入图片描述]()
| struct Node { |
| ElementType Data; |
| struct Node * Next; |
| } |
| struct QNode { |
| struct Node *rear; |
| struct Node *front; |
| }; |
| typedef struct QNode *Queue; |
| Queue PtrQ; |
# 2. 操作
# (1) 不带头结点的链式队列初始化（ CreateQueue）
| Queue CreateQueue() { |
| Queue Q; |
| Q = (Queue)malloc(sizeof(struct QNode)); |
| Q->front = Q->rear = NULL; |
| return Q; |
| } |
# (2) 不带头结点的链式队列入队操作
| bool AddQ(Queue PtrQ, ElementType item) { |
| struct Node *RearCell = PtrQ->rear; |
| struct Node *Temp = (struct Node *) malloc(sizeof(struct Node)); |
| Tmp->Data = X; |
| Tmp->Next = NULL; |
| if ( PtrQ->front == NULL ) { |
| PtrQ->rear = PtrQ->front = Tmp; |
| } else { |
| RearCell->Next = Tmp; |
| PtrQ->rear = Tmp; |
| } |
| return true; |
| } |
# (3) 不带头结点的链式队列出队操作
| 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 = PtrQ->rear = NULL; |
| else |
| PtrQ->front = FrontCell->Next; |
| FrontElem = FrontCell->Data; |
| free(FrontCell); |
| return FrontElem; |
| } |
