?队列是另外一种常用的线性结构，到达这种结构的元素越早，离开该结构的时间也越早，所以队列通常被称为先进先出(FIFO: First In First Out)队列。

1.队列可以看作是插入删除位置操作受限的线性表，它的插入和删除分别在表的两端进行。

2.队列的删除操作只能在队首(front)进行而插入操作只能在队尾(rear)进行，从而保证了队列的先进先出特点。

3.元素从队首删除的操作，称之为出队（deQueue）。

4.元素在队尾位置插入的操作，称为进队（enQueue）。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ??? ? ? ?——By?作者：新晓-故知?整理

1. 队列的抽象数据类型：

队列的抽象数据类型：

Data：?

?Operations:

队列的抽象数据类型:

ADT Queue {

数据对象:?? ??

数据关系:? ? ?

基本操作:

{     (1) InitQueue (&Q)              构造空队列
      (2) DestroyQueue (&Q)           销毁队列
      (3) ClearQueue (&S)             清空队列
      (4) QueueEmpty(S)               判空. 空--TRUE,
      (5) QueueLength(Q)              取队列长度
      (6) GetHead (Q,&e)              队头元素,
      (7) EnQueue (&Q,e)              入队列
      (8) DeQueue (&Q,&e)             出队列
      (9) QueueTraverse(Q,visit())    遍历
}ADT Queue

队列的顺序表示－－用一维数组base[M]

#define M  100         最大队列长度
Typedef struct 
{
   QElemType *base;    初始化的动态分配存储空间
   int  front;         头指针   
   int  rear;          尾指针
}SqQueue;

?front=0 rear=M时：

front=0            
rear=M 时
再入队——真溢出


front≠0
rear=M 时
再入队——假溢出

解决的方法－－循环队列：

base[0]接在base[M-1]之后
若rear+1==M
则令rear=0;

实现：利用“模”运算
入队：
  base[rear]=x;
  rear=(rear+1)%M;
出队：
  x=base[front];
  front=(front+1)%M;

?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?——By?作者：新晓-故知?整理

2. 循环队列:?

#define MAXQSIZE  100       最大队列长度
Typedef struct 
{
   QElemType *base;         初始化的动态分配存储空间
   int  front;              头指针   
   int  rear;               尾指针
}SqQueue;

?循环队列初始化:

Status InitQueue (SqQueue &Q)
{
    Q.base =new QElemType[MAXQSIZE] 
   if(!Q.base) exit(OVERFLOW);
    Q.front=Q.rear=0;
    return OK;
}

?求循环队列的长度:

int  QueueLength (SqQueue Q)
{
    return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;                             
 }

??循环队列入队:

Status EnQueue(SqQueue &Q,QElemType e)
{
    if((Q.rear+1)%MAXQSIZE==Q.front)  return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
     return OK;
}

??循环队列出队：

Status DeQueue (LinkQueue &Q,QElemType &e)
{
   if(Q.front==Q.rear) return ERROR;
   e=Q.base[Q.front];
   Q.front=(Q.front+1)%MAXQSIZE;
   return OK;
}

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? q???????????????????????——By?作者：新晓-故知?整理+创作

3.队列的顺序存储及实现：

a.队列的顺序存储，用一组连续的空间存储队列中的元素及元素间关系。

b.可以使用队首指针Front和队尾指针Rear分别指示队首元素和队尾元素存放的下标地址。

c.让Front指向真正的队首元素，而Rear指向真正存放队尾元素的后一数组单元。这样队空的标志Front=Rear。

d.为了防止大批数据移动，当Rear=maxSize时，如果下标为0的空间未用，让它转回来，即Rear=Rear%MaxSize。形成循环队列。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?——By?作者：新晓-故知?整理+创作

?队列操作中的Rear和Front

?队列操作中的Rear和Front

无论进队、出队，Rear和Front都向前移动，移动到右边界时向左边循环。为了区别队空标志，当队尾还有一个空间时即告队满，浪费了一个空间做代价。

队列空的标志：Rear=Front

队列满的标志：（Rear+1）%maxSize =Front

?进队操作后：Rear= （Rear+1）%maxSize?

?出队操作后：Front= （Front+1）%maxSize?

????????????????????????????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ???????——By?作者：新晓-故知?整理+创作

队列及操作的实现

#include <stdio.h>
#include <stdlib.h>
?
typedef int elemType;
?
typedef struct
{
    int Front, Rear;
    int maxSize;
    elemType *array;
}Queue;

void initialize(Queue *que, int size);     初始化队列元素的存储空间
int isEmpty(Queue *que);                   判断队空否，空返回1，否则为0
int isFull(Queue *que);                    判断队满否，满返回1，否则为0
elemType front(Queue *que);                读取队首元素的值，队首不变
void enQueue(Queue *que, elemType x);      将x进队，成为新的队尾
void deQueue(Queue *que);                  将队首元素出队
void doubleSize(Queue *que);               扩展队队列元素的存储空间为原来的2倍
void clear(Queue *que);                    将队列中所有元素清空，为空的队列
void destroy(Queue *que);                  释放队列元素所占据的动态数组

void initialize(Queue *que, int size)        初始化队列元素的存储空间
{    que->maxSize = size;
    //申请实际的队列存储空间
    que->array = (elemType *)malloc(sizeof(elemType)*size); 
    if (!que->array) exit(1);
    que->Front = que->Rear = 0;
}

int isEmpty(Queue *que)                      判断队空否，空返回1，否则为0
{return que->Front == que->Rear;}
?

int isFull(Queue *que)                       判断队满否，满返回1，否则为0
{return (que->Rear+1)%que->maxSize == que->Front;}


elemType front(Queue *que)                   读取队首元素的值，队首不变
{   if (isEmpty(que)) exit(1);
    return que->array[que->Front];
}


void enQueue(Queue *que, elemType x)          将x进队，成为新的队尾
{   if (isFull(que))  doubleSize(que);
    que->array[que->Rear]=x;
    que->Rear = (que->Rear+1)%que->maxSize;
}

?void deQueue(Queue *que)                     将队首元素出队
{   if (isEmpty(que)) exit(1);
    que->Front = (que->Front+1)%que->maxSize;
}


void clear(Queue *que) //将队列中所有元素清空，为空的队列
{ que->Front = que->Rear = 0;}
?

void destroy(Queue *que)                      释放队列元素所占据的动态数组
{  free(que->array);}


                                                        ——By?作者：新晓-故知?整理+创作

? 算法时间复杂度分析：各种操作的时间复杂度都为O(1)。

4.链式队列：

typedef struct QNode{
   QElemType   data;
   struct Qnode  *next;
}Qnode, *QueuePtr;
typedef struct {
   QueuePtr  front;            队头指针   
   QueuePtr  rear;             队尾指针
}LinkQueue;

?(a) 空队列

?(b) 元素x入队列

(c) 元素y入队列

(d) 元素x出队列

??

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?——By?作者：新晓-故知? 整理+创作?

?链队列初始化:

Status InitQueue (LinkQueue &Q)
{
   Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode)); 
    if(!Q.front) exit(OVERFLOW);
    Q.front->next=NULL;
     return OK;
}

?销毁链队列:

Status DestroyQueue (LinkQueue &Q)
{
   while(Q.front){
      Q.rear=Q.front->next;
      free(Q.front);
      Q.front=Q.rear;   }    
   return OK;
}

?判断链队列是否为空:

Status QueueEmpty (LinkQueue Q)
{
    return (Q.front==Q.rear);                             
 }

?求链队列的队头元素:

Status GetHead (LinkQueue Q, QElemType &e)
{
   if(Q.front==Q.rear) return ERROR;
   e=Q.front->next->data;
   return OK;
}

??链队列入队:
Status EnQueue(LinkQueue &Q,QElemType e)
{
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data=e; p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return OK;
}
?????????????????????????????????????????????????????? ? ? ? ? ? ? ????——By?作者：新晓-故知?整理+创作

?链队列出队：

Status DeQueue (LinkQueue &Q,QElemType &e)
{
   if(Q.front==Q.rear) return ERROR;
   p=Q.front->next;
   e=p->data;
   Q.front->next=p->next;
   if(Q.rear==p) Q.rear=Q.front;
   free(p);
   return OK;
}

用链表存储队列中的元素。其中队首指针 Front指向队首结点，队尾指针Rear指向队尾结点。

?

typedef int elemType;
typedef struct 
{
    elemType data;
    struct Node *next;
} Node;

typedef struct 
{
    Node *Front,*Rear;
}linkQueue;

void initialize(linkQueue *que);             初始化为一个空队

int isEmpty(linkQueue *que);                 判断队空否，空返回1，否则为0

int isFull(linkQueue *que);                  判断队满否，满返回1，否则为0

elemType front(linkQueue *que);              读取队首元素的值，队首不变

void enQueue(linkQueue *que, elemType x);    将x进队，成为新的队尾

void deQueue(linkQueue *que);                将队首元素出队

void clear(linkQueue *que);                  将队列中所有元素清空，为空的队列

void destroy(linkQueue *que);                释放队列元素所占据的动态空间


void initialize(linkQueue *que)              初始化为一个空队
{    que->Front = que->Rear = NULL;   }

void initialize(linkQueue *que);             初始化为一个空队

int isEmpty(linkQueue *que);                 判断队空否，空返回1，否则为0

int isFull(linkQueue *que);                  判断队满否，满返回1，否则为0

elemType front(linkQueue *que);              读取队首元素的值，队首不变

void enQueue(linkQueue *que, elemType x);    将x进队，成为新的队尾

void deQueue(linkQueue *que);                将队首元素出队

void clear(linkQueue *que);                  将队列中所有元素清空，为空的队列

void destroy(linkQueue *que);                释放队列元素所占据的动态空间

void initialize(linkQueue *que)              初始化为一个空队
{    que->Front = que->Rear = NULL;   }


void enQueue(linkQueue *que, elemType x)     将x进队，成为新的队尾
{   Node *tmp;
    tmp = (Node *)malloc(sizeof(Node));
    tmp->data = x;
    tmp->next = NULL;
    if (isEmpty(que))     que->Front = que->Rear = tmp;
    else
    {   que->Rear->next = tmp;
        que->Rear = tmp;
    }
}


void deQueue(linkQueue *que)                 将队首元素出队
{   Node *tmp;
    if (isEmpty(que)) exit(1);
   tmp = que->Front;
    que->Front = que->Front->next;
    free(tmp);
}

?
void clear(linkQueue *que)                   将队列中所有元素清空，为空的队列
{   Node *tmp;
    tmp = que->Front;}
while (tmp)
    {   que->Front = que->Front->next;
        free(tmp);
        tmp=que->Front;
    }
  que->Front = que->Rear = NULL;
}
?

void destroy(linkQueue *que)                  释放队列元素所占据的动态空间
{  clear(que); }



                                                      ——By?作者：新晓-故知?整理+创作

5.优先队列

有时要求进入队列中的元素具有优先级，队列中元素优先级越高出队越早，优先级越低出队越晚。

个人手头事务的处理通常采取这样的策略，操作系统中进程的调度、管理也是采用优先队列进行控制的.

元素之间的关系是由元素的优先级决定的，这样一种队列称为优先队列。

????????????????????????????????????????????????????????????? ? ? ??? ?——By?作者：新晓-故知?整理+创作

优先队列有多种实现方式：

采用顺序存储结构实现，是最常用的一种，称顺序优先队列；

其次也可以采用链式结构；

后面章节也有用堆来存储。

?为了避免整个队列的后移，造成空间的浪费，当有元素出队时将队列中最后一个元素移到出队元素所在的存储位置，这样队列始终从0下标开始到某个下标终止，中间不会出现空隙。

因为队列元素始终从0下标开始，所以不需要使用循环。

队空的条件为： Rear = Front;

队满的条件为：Rear = maxSize

????????????????????????????????????????????????????????????????????????——By?作者：新晓-故知?整理+创作

?算法时间复杂度分析：进队O(1), 出队O(n)。

6.另一种策略：

6.1?顺序循环队列：

元素在队列中按照优先数由小到大排列，当元素进队时需要找到合适的插入位置，移动后面的元素，将新进元素插入，时间复杂度为O(n)；当元素出队时只需删除队首元素，为了避免后面元素的移动，可以采用顺序循环队列，时间复杂度为O(1)。

?6.2?链式存储优先队列:

元素优先级最高的结点就是首结点，所以结点出队即删除首结点。O(1)

?进队结点首先要查找插入位置。比较从首结点开始，逐个进行，当找到第一个结点的优先数大于新结点的优先数时，将新结点插入该结点前面。O(n)