数据结构——队列

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.双端队列

?双端队列是指允许两端都可以进行入队和出队操作的队列。