大家好，我是讯享网，很高兴认识大家。

一、队列的定义

 

线性表：是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n=0时，线性表是一个空表。若用L命名线性表，则其一般表示为L=（a1,a2,...,ai,ai+1,...,an）。

栈：是只允许在一段进行插入或删除操作的线性表。

队列：是只允许在一端进行插入，在另一端删除的线性表。

队头、队尾、空队列

特点：先进先出（FIFO） First in first out

二、队列的基本操作

讯享网

 2.1 队列的定义

#define MaxSize 10//定义队列中元素的最大个数 typedef struct{ ElemType data[MaxSize];//用静态数组存放队列元素 int front,rear;//队头指针和队尾指针 }SqQuene; void testQueue(){ SqQueue Q;//声明一个队列（顺序存储） }//后续操作...

讯享网

 2.2 初始化操作

讯享网void InitQueue(SqQueue &Q){ //初始时，队头、队尾指针指向0 Q.rear=Q.front=0; } void testQueue(){ //声明一个队列（顺序存储） SqQueue Q; InitQueue(Q); //后续操作... }

 判断队列是否为空

bool QueueEmpty(SqQueue Q){ if(Q.rear==Q.front)//队空条件 return true; else return false; }

2.3 入队操作

讯享网bool EnQueue(SqQueue &Q,ElemType x){ if(队列以满) return false;//队满则报错 Q.data[Q.rear]=x;//将x插入队尾 Q.rear=Q.rear+1;//队尾指针后移 return true; }

Q.data[Q.rear]=x——将 x放入队尾指针所指的位置

 Q.rear=Q.rear+1——队尾指针加一，后移

 静态数组存满后，队尾指针是10

 所以队列已满的条件是：rear==MaxSize？？？？

答案不是

 当取出元素时，rear还是等于10，不会变，但这时候队列有空

所以更改代码，采用取余操作Q.rear=(Q.rear+1)%MaxSize，将存储空间从逻辑上变成了“环状”

bool EnQueue(SqQueue &Q,ElemType x){ if(队列以满) return false;//队满则报错 Q.data[Q.rear]=x;//将x插入队尾 Q.rear=(Q.rear+1)%MaxSize;//队尾指针+1取模 return true; }

 因为判断队满的条件是判断rear==front，因此必须牺牲一个单元

 队列已满的条件：队尾指针的在下一个位置是队头，即（Q.rear+1）%MaxSize==Q.front;

讯享网bool EnQueue(SqQueue &Q,ElemType x){ if((Q,rear+1)%MaxSize==Q.front)//判断队满条件 return false;//队满则报错 Q.data[Q.rear]=x;//将x插入队尾 Q.rear=(Q.rear+1)%MaxSize;//队尾指针+1取模 return true; }

队列元素个数：

（rear+MaxSize-front）%MaxSize 

2.4 出队操作

只能让队头元素出队

//出队（删除一个队头元素，并用x返回） bool DeQueue(SeQueue &Q,ElemType &x){ if(Q.rear==Q.front) return false;//队空则报错 x=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; return ture; }

2.5 队列查找

获得队头元素，用x返回

讯享网bool GetHead(SqQueue Q,ElemType &x){ if(Q.rear==Q.front) return false;//队空则报错 x=Q.data[Q.front]; return true; }

其他元素呢？？？

2.6 不浪费内存条件下判断队列已满/已空

方法二：

#define MaxSize 10 typedef struct{ ElemType data[MaxSize]; int front,rear; int size;//队列当前长度 }SqQuene; 

初始化时rear==front==0;size=0;

插入成功：size++

删除成功：size--；

队满条件：size==MaxSize;

队空条件：size==0；

方法三：

讯享网#define MaxSize 10 typedef struct{ ElemType data[MaxSize]; int front,rear; int tag;//最近进行的是删除（0）/插入（1） }SqQuene; 

初始化时，rear=front=0;tag=0;

每次删除操作成功时，都令tag=0；

每次插入操作成功时，都令tag=1；

只有删除操作才可能导致队空，因此队空条件为：front==rear&&tag==0；

同理，队满条件为：front==rear&&tag==1；

2.7 rear指针指向队尾元素情况

判空：

（Q.rear+1）%MaxSize==Q,front

判满：

（Q.rear+1）%MaxSize==Q,front

两种方法：

1.牺牲一个存储单元：

rear与front隔了两个单元，队满、隔了 一个单元，队空

2.增加辅助变量

size、tag

三、链式存储实现队列

3.1 队列的链式实现

typedef struct LinNode{//链式队列结点 ElemType data; struct LinkNode *next; }LinkNode; typedef struct{//链式队列 LinkNode *front,*rear;//队列的队头和队尾指针 }LinkQueue;

 3.2 初始化

带头结点

讯享网typedef struct LinkNode{ ELEMtype data; struct LinkNode *next; }LinkNode; typedef struct{ LinkNode *front,*rear; }LinkQueue; //初始化队列 void InitQueue(LinkQueue &Q){ //初始时 front、rer都指向头结点 Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); Q.front->next=NULL;//判空操作 } void testLinkQueue(){ LinkQueue Q;//声明一个队列 InitQueue(Q);//初始化一个队列 //后续操作.... }

其他判空操作：

bool IsEmpty(LinkQueue Q){ if(Q.front==Q.rear) return true; else return false; }

不带头结点

 3.3 入队操作

带头结点

讯享网void EnQueue(LinkQueue &Q,ElemType x){ LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode)); s->data=x; s->next=NULL; Q.rear->next=s;//新结点插入rear之后 Q.rear=s;//修改表尾指针 } 

元素都是队尾插入，所以s的next指针为空 

 不带头结点

 3.4 出队操作

带头结点

bool DeQueue(LinkQueue &Q,ElemType &x){ if(Q.front==Q.rear) return false;//空队 LinkNode *p=Q.front->next; x=p->data;//用变量x返回队头元素 Q.front->next=p->next;//修改头结点的next指针 if(Q.rear==p)//此次是最后一个结点出队 Q.rear=Q.front;//修改rear指针 free(p);//释放结点空间 return true; }

不带头结点

四、双端队列

只允许从两端插入、两端删除的线性表 

 若只使用其中一端插入、删除操作，则效果等同于栈