数据结构-队列

前言

本篇文章介绍队列的基础知识，包括队列的抽象数据类型以及队列的实现。

一、队列及其抽象数据类型

1.1 队列的基本概念

基本定义 限定在表的一端进行插入操作，另一端进行删除操作的线性表
逻辑结构 一种特殊的线性表，一对一关系
存储结构 顺序存储和链式存储，常用顺序存储
运算规则 进行删除操作的一端称为队头，进行插入操作的一端称为队尾，访问结点按照先进先出（FIFO）的原则
队列的插入操作通常称为入队
队列的删除操作通常称为出队
队列的示意图如图1.1所示

图1.1 队列示意图

1.2 队列的抽象数据类型

ADT Queue
{数据对象:D={ai|ai ∈ElemSet,i=1,2,3,...n,n >= 0}数据关系:S={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}约定an为队尾，a1为队头基本操作：	initQueue(&Q)操作结果：构造一个空的队列QdestroyQueue(&Q)初始条件：队列Q已存在操作结果：队列Q被销毁isEmptyQueue(&Q)初始条件：队列Q已存在操作结果：判断队列Q是否为空队列lengthQueue(&Q)初始条件：队列Q已存在操作结果：返回队列Q的长度enQueue(&Q, e)初始条件：队列Q已存在操作结果：插入元素e为队列的队尾元素deQueue(&Q, &e)初始条件：队列Q已存在操作结果：删除队列Q的队头元素，用e返回被删除的元素getElemQueue(Q, &e)初始条件：队列Q已存在且为非空队列操作结果：用e返回队头元素...
}ADT Queue

二、队列的实现

2.1 顺序表示

2.1.1 结构定义

用顺序存储来表示队列时，要分配一块连续的内存空间来存放队列的元素，并用两个指针变量分别表示队头和队尾。
队列的结构定义如下

//顺序队列的定义#define SUCCESS 1
#define ERROR 0
#define OVERFLOW -1
#define MAXQSIZE 100   //队列最大元素个数//队列数据类型定义
typedef char QElemType;//定义队列类型
struct SeqQueue {QElemType* base;  //队列指针int front;        //数据元素下标，假设为队头指针int rear;		  //数据元素下标，假设为队尾指针
};//定义队列类型指针
typedef struct SeqQueue* PSeqQueue;

利用一块连续的存储单元依次存放自队头到到尾的数据元素
base指针指向这块存储单元的起始地址
front表示队头的下标
rear表示队尾的下标
MAXQSIZE表示队列的最大元素个数

图2.1 顺序队列示意图

假设MAXQSIZE=4，顺序队列的动态示意图如图2.2

图2.2 顺序队列的动态示意图

在顺序队列中，同栈一样存在队列溢出问题。
当队列满时，再做入队操作，称为上溢，即对图2.2中的第三个图再做入队操作，会造成上溢；
当队列为空时，再做出队操作，称为下溢，即对图2.2中的第一个和第五个图再做出队操作，会造成下溢

特别地，如果对图2.2中的第五个图进行入队操作，则会造成溢出，而实际上这时队列的前端可能还有可用的空间，因此，这种现象称为假溢出，即front = MAXQSIZE

通常，解决假溢出采用的方法是，把顺序队列从逻辑上看作是一个环形，也称为环形队列，为了在逻辑上形成环形队列，则需要在每次进行入队和出队操作时，对MAXQSIZE进行取余

当环形队列已有MAXQSIZE-1个数据元素时，如果再进行入队操作，则front = rear，与空队列的情况重合，会出现无法判断队列的情况。
为了区分空队列与满队列两种情况的环形队列，一般是牺牲队列的一个结点空间，当队列已有MAXQSIZE-1个数据元素时，则称队列已满的情况。如图2.3所示
空对列：front = rear
满队列: (rear+1)%MAXQSIZE = front

图2.3 环形队列的情况图

2.1.2 基本操作的实现

1. 顺序队列的初始化

   //6.1 队列初始化
   void initSeqQueue(PSeqQueue queue)
   {assert(queue);queue->base = (QElemType*)malloc(sizeof(QElemType) * MAXQSIZE);if (NULL == queue->base){printf("malloc fail!\n");exit(OVERFLOW);}queue->front = 0;queue->rear = 0;
   }
   

2. 顺序队列的销毁

   //6.2 销毁队列
   void destorySeqQueue(PSeqQueue queue)
   {assert(queue);free(queue->base);queue->base = NULL;
   }
   

3. 顺序队列的入队
   step1 判断队列是否为满队列
   step2 入队

   //6.5 入队
   int enSeqQueue(PSeqQueue queue, QElemType e)
   {assert(queue);if ((queue->rear + 1) % MAXQSIZE == queue->front) //判断队满return ERROR;queue->base[queue->rear] = e;queue->rear = (queue->rear + 1) % MAXQSIZE;return SUCCESS;
   }
   

4. 顺序入队的出队
   step1 判断队列是否为空队列
   step2 出队

   //6.6 出队
   int deSeqQueue(PSeqQueue queue, QElemType* e)
   {assert(queue);if (queue->front == queue->rear)//判断队空return ERROR;*e = queue->base[queue->front];queue->front = (queue->front + 1) % MAXQSIZE;return SUCCESS;
   }
   

5. 获取顺序队列的队头元素
   step1 判断队列是否为空队列
   step2 获取队头元素

   //6.7 获取队头元素
   int getQElemSeqQueue(PSeqQueue queue, QElemType* e)
   {assert(queue);if (queue->front == queue->rear)//判断队空return ERROR;*e = queue->base[queue->front];return SUCCESS;
   }
   

2.2 链式表示

2.2.1 结构定义

队列的链接表示就是用一个单链表来表示队列，队列的每个元素对应链表的一个结点，结点的结构与单链表的结构一样。为了强调队头和队尾都是队列的属性，这里对队列增加一层封装，引入LinkQueue结构的定义，这样的存储的队列简称链接队列。

//链接队列的定义
//不带头结点的链表
#define SUCCESS 1
#define ERROR 0
#define OVERFLOW -1//队列数据类型定义
typedef char QElemType;//链接队列结点定义
struct QueueNode;
typedef struct QueueNode* PQueueNode;
struct QueueNode {QElemType data;PQueueNode next;
};//链接队列类型定义
struct LinkQueue {PQueueNode front;	//队头指针PQueueNode rear;		//队尾指针
};
typedef struct LinkQueue LinkQueue;
//指向链接队列类型的指针类型
typedef struct LinkQueue* PLinkQueue;

假设queue是PLinkQueue类型的变量，则图2.4为队列的链接表示

图2.4 队列的链接表示

2.2.2 基本操作的实现

1. 链接队列的初始化

   //7.1 队列初始化
   void initLinkQueue(PLinkQueue queue)
   {assert(queue);queue->front = NULL;queue->rear  = NULL;
   }
   

2. 链接队列的销毁

   //7.2 销毁队列
   void destoryLinkQueue(PLinkQueue queue)
   {assert(queue);PQueueNode p = queue->front;while (p){PQueueNode q = p->next;free(p);p = q;}queue->front = NULL;queue->rear  = NULL;
   }
   

3. 链接队列的入队

   //7.4 入队
   int enLinkQueue(PLinkQueue queue, QElemType e)
   {assert(queue);//创建一个队列结点PQueueNode newNode = (PQueueNode)malloc(sizeof(struct QueueNode));if (NULL == newNode){printf("malloc fail!n");return ERROR;}newNode->data = e;newNode->next = NULL;if (NULL == queue->front)//判断当前队列是否为空queue->front = newNode;elsequeue->rear->next = newNode;queue->rear = newNode;return SUCCESS;
   }
   

4. 链接队列的出队

   //7.5 出队
   int deLinkQueue(PLinkQueue queue, QElemType* e)
   {assert(queue);if (NULL == queue->front)//判断空队列return ERROR;*e = queue->front->data;PQueueNode p = queue->front;queue->front = queue->front->next;free(p);if (NULL == queue->front) //如果出队后，队列为空，为了避免野指针，则将队尾置空queue->rear = NULL;return SUCCESS;
   }
   

5. 获取链接队列的队头元素

   //7.6 获取队头元素
   int getQElemLinkQueue(PLinkQueue queue, QElemType* e)
   {assert(queue);if (NULL == queue->front)  //判断空队列return ERROR;*e = queue->front->data;return SUCCESS;
   }
   

总结

完整代码: https://gitee.com/PYSpring/data-structure/tree/master/queue_code