目录

前言

队列(Queue)

概念：

队列抽象数据类型描述

顺序存储

操作

链式存储

前言

上一篇我们讲解了堆栈相关的知识点，今天我们就对队列详细讲讲，并在此文中将其与堆栈进行适当对比，队列最主要的两个操作是什么呢，我们一起往下看吧

队列(Queue)

概念：

具有一定操作约束的线性表，插入和删除操作，只能在一端插入，而在另一端删除

堆栈也是受限的线性表，但它的插入和删除只在一端进行

数据插入：入队列(AddQ)

数据删除：出队列(DeleteQ)

先来先服务，先进先出(FIFO)                       堆栈——先进后出

队列抽象数据类型描述

数据对象集：一个有0个或多个元素的有穷线性表

操作集：长度为MaxSize的队列Q∈Queue，队列元素item∈ElementType

1. Queue CreatQueue(int MaxSize):                生成长度为MaxSize 的空队列
2. int IsFullQ(Queue Q,int MaxSize):                判断队列Q是否已满
3. void AddQ(Queue Q,ElementType item):     将数据元素item插入队列Q中
4. int IsEmptyQ(Queue Q):                               判断队列Q是否为空
5. ElementType DeleteQ(Queue Q):                将队头数据元素从队列中删除并返回

顺序存储

与堆栈一样，顺序存储也可以用数组来实现，队列也可以用数组来存储队列里的元素，，队列顺序存储结构通常由一个 一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成

#define MaxSizeStructQNode{
ElementTypeData[MaxSize];
intrear;
intfront;
};
typedefstructQNode*Queue;

front指向第一个元素前面的位置，rear指向最后一个元素的位置

初始时front==rear，当元素排满每一个位置时，front和rear也相等，这是该怎么区分？为什么会出现这种情况？

根本原因：数组大小只有n种状态，无法对应n+1种情况

解决方法：1.增加额外的标记，如Size或者tag域

                 2.仅使用n-1个数组空间

操作

入队列

voidAddQ(QueuePtrQ, PtrQ,ElementTypeitem)
{
if((PtrQ->rear+1)%MaxSize==PtrQ->front){
printf("队列满");
return;
    }
PtrQ->rear= (PtrQ->rear+1)%MaxSize;
ptrQ->Data[PtrQ->rear] =item;  
}

出队列

ElementTypeDeleteQ(QueuePtrQ)
{
if(PtrQ->front==PtrQ->rear){
printf("队列空");
returnERROR;
    }else {    
PtrQ->front= (PtrQ->front+1)%MaxSize;
returnPtrQ->Data[PtrQ->front];
    }
}

链式存储

队列的链式村粗结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行；队列指针front和rear应分别指向链表的头和尾

structNode{
ElementTypeData;
structNode*Next;
};
structQNode{        //链队列结构structNode*rear;    //指向队尾结点structNode*front;   //指向队头结点};
typedefstructQNode*Queue;
QueuePtrQ;