队列
队列的基本概念
- 队列是有限个同类型元素的线性序列
- 队列也是一种运算受限的线性表，而且是先进先出的线性表 FIFO
- 新加入的数据元素加入在队尾，出队列的数据元素在队列首部被删除
如下图所示
屏幕快照 2019-04-24 16.49.55.png
队列的基本运算
- 队列初始化
- 队列判空
- 入队
- 出队
- 取队列首元素
- 清空队列
- 销毁队列
- 获取队列长度
队列的两种存储结构
顺序存储
先看一个图：
屏幕快照 2019-04-24 17.24.59.png
从上图看出，随着队列的入队、出队进行，会使整体队列向上移动（也就是向后移动），当队尾指针指向最上端的存储区域时，就不能入队了，再入队会出现溢出，但是实际上队列中还有空余空间；这种现象称为"假溢出"。
解决假溢出的方法：
- 方法一：每次队列出队时，让队列整体向前移动一个位置，这样就保证了队首元素始终在最前边（存储空间的首个元素地址）；但是这样每次都需移动N个元素，平均时间复杂度为O(n)；效率低
- 方法二：当队尾出现溢出时，可判断头指针位置，如果前边有空余位置，则把当前队列整体前移，这样可减少元素的移动次数，可以看做是方法一的优化；
- 方法三：引入循环队列的概念。可以将队列看成首尾相接的循环结构，当队尾指针到队尾后，再从头指针开始；这种方法就不需要移动元素了，这种顺序队列称为循环队列。
循环队列
当使用了循环队列，入队的队尾指针加1操作及出队的队首指针加1操作要做响应的修改，当front==rear时，有可能是空队列，也有可能队列已满，为了区分开，队列最多可容纳maxsize-1个元素。
循环队列 C语言实现
const int maxsize = 10;
typedef struct queue {
int front;
int rear;
int data[maxsize];//数据为int类型
}CycleQueue;
1、队列初始化
CycleQueue *initCycleQueue() {
CycleQueue *queue = (CycleQueue *)malloc(sizeof(CycleQueue));
queue->front = 0;
queue->rear = 0;
return queue;
}
2、 队列判空
int emptyQueue(CycleQueue *queue) {
if (queue->front == queue->rear) {
return 1;
}
return 0;
}
3、入队
int enQueue(CycleQueue *queue,int x) {
if ((queue->rear+1) % maxsize == queue->front) {
printf("队列已满");
return 0;
} else {
queue->rear = (queue->rear+1) % maxsize;
queue->data[queue->rear] = x;
return 1;
}
}
4、出队
int outQueue(CycleQueue *queue) {
if (emptyQueue(queue)) {
printf("队列为空");
return 0;
} else {
queue->front = (queue->front+1) % maxsize;
return 1;
}
}
5、取队列首元素
int getFirst(CycleQueue *queue) {
if (emptyQueue(queue)) {
printf("队列为空");
return -1;
} else {
return queue->data[queue->front+1];
}
}
6、清空队列
void clearQueue(CycleQueue *queue) {
queue->front = 0;
queue->rear = 0;
}
7、销毁队列
void destoryQueue(CycleQueue *queue) {
free(queue);
queue = NULL;
}
8、获取队列长度
int lengthQueue(CycleQueue *queue) {
return (queue->rear-queue->front+maxsize) % maxsize;
}
链队列
1、初始化
LinkQueue *initLinkQueue(void) {
LinkQueue *queue = (LinkQueue *)malloc(sizeof(LinkQueue));
LinkQueueNode *node = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
node->next = NULL;
queue->front = node;//队列头指针指向头结点
queue->rear = node;//队列尾指针指向尾结点
return queue;
}
2、判空
int emptyLinkQueue(LinkQueue *queue) {
if (queue->front == queue->rear) {
return 1;
}
return 0;
}
3、入队
void enLinkQueue(LinkQueue *queue,int x) {
LinkQueueNode *node = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
node->data = x;
node->next = NULL;
queue->rear->next = node;//上个尾结点的下一结点为新加入的结点
queue->rear = node;//重新指向尾结点
}
4、出队
void outLinkQueue(LinkQueue *queue) {
if (emptyLinkQueue(queue)) {
printf("队列为空");
} else {
LinkQueueNode *node = queue->front->next;
queue->front->next = node->next;
if (node->next == NULL) {
queue->rear = queue->front;//无首结点，首尾指向头结点
}
free(node);
}
}
5、获取首元素
int getFirstLinkQueue(LinkQueue *queue) {
if (emptyLinkQueue(queue)) {
printf("队列为空");
return -1;
} else {
LinkQueueNode *node = queue->front->next;
return node->data;
}
}
6、获取队列长度：可添加一个变量 count，这样就不用每次都遍历一遍
int lengthLinkQueue(LinkQueue *queue) {
int k = 0;
if (emptyLinkQueue(queue)) {
return k;
}
LinkQueueNode *node = queue->front->next;
while (node != NULL) {
k++;
node = node->next;
}
return k;
}
7、清空队列
void clearLinkQueue(LinkQueue *queue) {
if (!emptyLinkQueue(queue)) {
LinkQueueNode *p,*q;
p = queue->front->next;
queue->front->next = NULL;//头结点指向null
while (p) {//销毁结点
q = p->next;
free(p);
p = q;
}
queue->rear = queue->front;//都指向头结点
}
}
8、销毁队列
void destoryLinkQueue(LinkQueue *queue) {
while (queue->front) {//销毁内部结点
queue->rear = queue->front->next;
free(queue->front);
queue->front = queue->rear;
}
}
顺序队列与链队列的优缺点
- 顺序队列需要预留出空间，而链队列不需要
- 链队列没有容量限制
- 链队列 除了销毁和清空队列时间复杂度为O(n),其余均为O(1)
- 顺序队列所有操作时间复杂度均为O(1)
- 顺序队列存在假溢出现象，需要使用环形队列来避免
