1.队列的基本概念
1)队列的定义
队列(Queue)简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队;删除元素称为出队或离队。
?其操作的特性是先进先出.
队头 (Front)。允许删除的一端，又称队首。
队尾(Rear)。允许插入的一端。
空队列。不含任何元素的空表。
2)队列常见的基本操作?
InitQueue(&Q):初始化队列，构造一个空队列 Q。
QueueEmpty(Q):判队列空，若队列Q为空返回true，否则返回false
EnQueue(&Q,x):入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q，&x):出队，若队列Q非空，删除队头元素，并用x返回。
GetHead(Q，&x):读队头元素，若队列Q非空，则将队头元素赋值给 x。
需要注意的是，栈和队列是操作受限的线性表，因此不是任何对线性表的操作都可以作为栈和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。?
2.?队列的顺序存储结构
?1)队列的顺序存储
?#define MaxSize 50
typedef struct{
????????ElemType data[Maxsize];
????????int front,rear;
}SqQueue;
初始时:Q.front=Q.rear=0。
进队操作:队不满时，先送值到队尾元素，再将队尾指针加1。
出队操作:队不空时，先取队头元素值，再将队头指针加 1。
(队头指针front指向队头元素,队尾指针rear指向队尾元素的下一个位置)?
?2)循环队列
将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到 0，这可以利用除法取余运算 (%)来实现。
初始时;Q.front=Q.rear=0
队首指针进1:Q.front=(Q.front+1)%MaxSize
队尾指针进1:Q.rear=(Q.rear+1)%MaxSize
队列长度:(Q.rear + MaxSize - Q.front)%MaxSize
为了区分是队空还是队满的情况，有三种处理方式:
①辆牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法,约定以“队头指针在队尾指针的下一位置作为队满的标志”。
队满条件:(Q.rear+1)%MaxSize==Q.front。
队空条件:Q.front==Q.rear。
队列中元素的个数:(Q,rear - Q.front + MaxSize)%MaxSize。
②类型中增设表示元素个数的数据成员int? size = 0;入队：size++；出队：size- -。这样，队空的条件为 Q.size==0;队满的条件为Q.size==MaxSize。
③类型中增设 tag 数据成员，以区分是队满还是队空。tag 等于 0 时，若因删除导致Q.front==Q.rear，则为队空;tag 等于1时，若因插入导致Q.front==Q.rear，则为队满。
?3）循环队列的操作
(1)初始化
?void InitQueue(SqQueue &Q){
????????Q.rear=Q.front=0;
}
?(2)判队空
?bool isEmpty(SqQueue Q)(
????????if(Q.rear==Q.front)????????????????return true;
? ? ? ? else
? ? ? ? ? ? ? ? return? false;
}
?(3)入队
bool?EnQueue(SqQueue &Q,ElemType x)(
????????if((Q.rear+1)%MaxSize==Q.front) return false;?????????Q.data[Q.rear]=x;
????????Q.rear=(Q.rear+1)%MaxSize;
????????return true;
}
(4)出队?
?bool DeQueue(SqQueue &Q , ElemType &x){
????????if(Q.rear==Q.front) return false;
????????x=Q.data[Q.front];
????????Q.front=(Q.front+l)%MaxSize;
????????return true;
}
?3.队列的链式存储结构
1)队列的链式存储
队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点。
?typedef struct LinkNode{
????????ElemType data;
????????struct LinkNode *next;
)LinkNode;
typedef struct{
????????LinkNode *front,*rear;
}*LinkQueue;
?2)链式队列的基本操作
(1)初始化
void InitQueue(LinkQueue &Q){
????????Q.front=O.rear=(LinkNode*)malloc(sizeof(LinkNode));
????????Q.front->next=NULL;
}
(2)判队空
bool IsEmpty(LinkQueue Q){
????????if(Q.front==Q.rear)
????????????????return true;
????????else
????????????????return false;
}
(3) 入队
void EnQueue(LinkQueue &Q,ElemType x){
????????LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
????????s->data=x;
? ? ? ? s->next=NULL;
? ? ? ? Q.rear->next=s;
? ? ? ? Q.reat=s;
}
(4)出队
bool DeQueue(LinkQueue &Q,ElemType &x){
????????if(Q.front==Q.rear) return false;
????????LinkNode *p=Q.front->next;
????????x=p->data;
????????Q.front->next=p->next;????????if(Q.rear==p)
????????????????Q.rear=Q.front;
????????free(p);
????????return true;}
4.双端队列
?双端队列是指允许两端都可以进行入队和出队操作的队列。