数据结构与算法-基础(4)

04、数据结构与算法 - 基础：队列

队列的定义

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。
队列的修改是依先进先出的原则进行的。

队列的基本操作

1．初始化队列 InitQueue(&Q) 将队列Q设置成一个空队列。

2．入队列 EnQueue(&Q,X) 将元素X插入到队尾中，也称“进队” ，“插入”。

3．出队列 OutQueue(&Q,&e) 将队列Q的队头元素删除，并用e返回其值，也称“退队”、“删除”。

4．取队头元素 GetHead(Q,&e) 得到队列Q的队头元素之值，并用e返回其值。 5．判队空 QueueEmpty(Q) 判断队列Q是否为空，若为空返回1，否则返回0。

队列的顺序实现

在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。

#define MaxSize  100
typedef int DataType;
typedef struct{
   DataType data[MaxSize];
   int front,rear;
 }Queue;

顺序队列（ MaxSize=4 ）的几种状态：

1、表示空队列， rear==front==0。（4）A出队后，rear==front==3。再插入元素时，会出现假溢出的情况。

克服假溢出的方法：

1、将队列中的所有元素均向最前端的位置移动；

2、采用循环队列。

循环队列

循环队列的物理存储未发生任何改变，其只是充分利用数组空间，想象将数组的首尾连接起来，形成一个循环队列。

（a）表示空队列， rear==front==0。

（b）元素A入队后， rear==1， front==0。

（c）B，C依次入队后， rear==3， front==0。

（d）A,B,C出队后, front==3 ,rear==3。队列又为空

所以，循环队列为空的判定条件为：front==rear;

基本实现

#include"stdio.h"
#include"stdlib.h"

#define Maxsize 100
typedef int DataType;

typedef struct {
    DataType data[Maxsize];
    int front,rear;
}Queue;

//初始化队列
void InitQueue(Queue *Q)
{
    Q->front=Q->rear=0;
}
//入队
int InQueue(Queue *Q,DataType x)
{
    if((Q->rear+1)%Maxsize==Q->front)
        return 0;
    Q->rear=(Q->rear+1)%Maxsize; //if (Q->rear+1)==Maxsize,Q->rear=0
    Q->data[Q->rear]=x;
    return 1;
}
//判断空队列
int EmptyQueue(Queue *Q)
{
    if(Q->rear==Q->front)
        return 1;
    else
        return 0;
}
//出队
int OutQueue(Queue *Q,DataType *x)
{
    if(EmptyQueue(Q))
        return 0;
    Q->front=(Q->front+1)%Maxsize;
    *x=Q->data[Q->front];
    return 1;
}
//取队头元素
int GetHead(Queue *pQ,DataType *px)
{ 
    if(EmptyQueue(pQ))
      {    printf("\n Queue is free");
            return 0;
      }
      *px=pQ->data[(pQ->front+1)%MaxSize];
          return 1;
}

循环队列中的常用判断语句

1、队列判空条件：rear==front;

2、队列判满条件：(rear+1)%MaxSize==front;

3、入队操作：

第①步，先判断队列是否已满；

第②步，rear=(rear+1)%MaxSize；

第③步：尾指针位置赋值相应元素；

4、出队操作：

第①步，先判断队列是否已空；

第②步，front=(front+1)%MaxSize；

5、计算循环队列中元素的个数：分两种情况讨论，如图所示：

所以：(rear-front+MaxSize)%MaxSize。

队列的链式表示和实现

队列的链式存储结构简称为链队。它实际上是一个同时带有首指针和尾指针的单链表。头指针指向表头结点，而尾指针则指向队尾元素。

链队结构示意图：

链队的数据类型定义如下：

typedef int DataType;
typedef struct qnode{
    DataType data;
    struct qnode *next;
}Qtype;
typedef struct qptr{
    Qtype *front,*rear;
}LinkQueue;
LinkQueue LQ;

链队运算指针变化情况：

c语言实现：

#include"stdio.h"
#include"malloc.h"
typedef int DataType; //定义队列类型
//定义队结点
typedef struct node
{
    DataType data;
    struct node *next;
}qnode; //链队结点类型
 
typedef struct
{
    qnode *front; //定义qnode *类型的指针成员
    qnode *rear;
}LinkQueue;
 
//初始化队
int InitQueue(LinkQueue *Q)
{
    Q->front=Q->rear=(qnode *)malloc(sizeof(qnode)); //申请空间作头结点，头结点不存放数据
    if(!Q->front)  //if Q->front NULL
        return 0;
    Q->front->next=NULL; //使队头结点的指针域为NULL
    return 1;
}
//判断队空
int EmptyQueue(LinkQueue *Q)
{
    if(Q->front==Q->rear)
        return 1;
    else
        return 0;
}
//进队
void InQueue(LinkQueue *Q,DataType x)
{
    qnode *s;
    s=(qnode *)malloc(sizeof(qnode)); //申请一结点空间
    s->data=x;
    s->next=NULL; 
    Q->rear->next=s; //使s结点连上前一个结点
    Q->rear=s;  //尾指针指向结点，即最后一个结点
}
//出队
int OutQueue(LinkQueue *Q,DataType *e)
{
    qnode *q;
    if(EmptyQueue(Q))
        return 0;
    q=Q->front->next; //取头结点地址
    *e=q->data;  //返回头结点数据
    Q->front->next=q->next;  //头结点指针域存原第二结点地址
     if(Q->rear==q)  //if(Q->front->next==NULL) 若队列中只有1个元素，则出队后队列为空
         Q->rear=Q->front; 
     free(q); //释放q指向的结点，即队头结点 
    return 1;
}

View Code

队列的应用：

CPU资源的竞争问题。
服务、排队问题。
迷宫求解。

线性表、栈与队的异同点

相同点：

逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。

不同点：

运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。

用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。