数据结构----队列

一、队列

1）队列定义

        队列(Queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 允许插入的端是队尾，允许删除的端是队头。队列是一个先进先出(FIFO)的线性表，相应 的也有顺序存储和链式存储两种方式。

2）循环队列

        顺序存储就是用数组实现，比如有一个ｎ个元素的队列，数组下标0的一端是队 头，入队操作就是通过数组下标一个个顺序追加，不需要移动元素，但是如果删除 队头元素，后面的元素就要往前移动，对应的时间复杂度就是O(n)，性能自然不 高。

        为了提高出队的性能，就有了循环队列，需要有两个指针，front指向队头，rear指 向对尾元素的下一个位置，元素出队时front往后移动，如果到了对尾则转到头部， 同理入队时rear后移，如果到了对尾则转到头部，这样通过下标front出队时，就不 需要移动元素了。

         同时规定，当队列为空时，front和rear相等，那么队列什么时候判断为满呢？按照 循环操作rear依次后移，然后再从头开始，也是出现rear和front相等时，队列满。

        这样跟队列空的情况就相同了，为了区分这种情况，规定数组还有一个空闲单元 时，就表示队列已满， （也就是队头指针在队尾指针的下一位置时，队满。） 因为rear 可能在front后面，也可能循环到front前面，所以队列满的条件就变成了 (rear+1)%maxsize == front 。 对于队列的元素个数计算为：(rear -front+maxsize)%maxsize。

3）用数组实现的顺序存储循环队列

4)   链式队列

        循环队列要事先申请好空间，整个过程都不能释放，而且要有固定的长度，如果长度事先无法估计，这种方式显然不够灵活；所以就引入了链式存储队列，其实就是 线性表的单链表，只是它只能对尾进，队头出。并且规定队头指针指向链队列的头结点，对尾指针指向终端节点，当队列为空时，front和rear都指向头结点。(尾插头删)

        入队操作，就是在链表尾部插入结点；出队操作就是头结点的后继结点出队，然后将头结点的后继后移。如果最后除了头结点外，只剩一个元素了，就把rear也指向头结点。

二、队列的操作步骤

1.构建静态数组队列结构

1)建立结构体

2)初始化队列

3)入队

4)出队

5)遍历

#include<stdio.h>
#include <stdlib.h>
#include  <string.h>
#include<stdbool.h>
#include<assert.h>//静态数组构建队列结构
#define SIZE  5
typedef  int ele_type;typedef struct queue
{ele_type arr[SIZE];int front;int real;
}  Queue;//初始化队列
void init(Queue* que)
{assert(que);memset(que->arr, 0, sizeof(ele_type) * SIZE);que->front = 0;que->real = 0;
}//插入元素--入队
bool  push_queue(Queue* que, ele_type val)
{assert(que);if ((que->real + 1) % SIZE == que->front)return false;que->arr[que->real] = val;que->real++;que->real = que->real % SIZE;return true;}//删除元素--出队
bool  pop_queue(Queue* que, ele_type* rtval)
{assert(que);if (que->front == que->real)return false;*rtval = que->arr[que->front++];que->front = que->front % SIZE;return true;}//遍历队列
void print_queue(Queue* que)
{if (que->front == que->real)return;if (que->front < que->real){for (int i = que->front; i < que->real; i++){printf("%d\n", que->arr[i]);}}else{for (int i = que->front; i < SIZE; i++){printf("%d\n", que->arr[i]);}for (int i = 0; i < que->real; i++){printf("%d\n", que->arr[i]);}}}//获取数组长度
int get_queue_size(Queue* que)
{return ((que->real - que->front + SIZE) % SIZE);}//清空数组
void Clear_queue(Queue* que)
{que->front = que->real = 0;}int main()
{Queue q;init(&q);push_queue(&q, 11);push_queue(&q, 12);push_queue(&q, 13);push_queue(&q, 14);ele_type temp;pop_queue(&q, &temp);printf("temp=%d\n", temp);pop_queue(&q, &temp);printf("temp=%d\n", temp);pop_queue(&q, &temp);printf("temp=%d\n", temp);push_queue(&q, 15);push_queue(&q, 16);printf("===================\n");print_queue(&q);printf("ele num=%d\n", get_queue_size(&q));return 0;
}

运行结果:

2.构建链表队列结构

1)建立结构体

2)初始化队列

3)入队

4)出队

5)遍历

#include<stdio.h>
#include <stdlib.h>
#include  <string.h>
#include<stdbool.h>
#include<assert.h>//静态数组构建队列结构
#define SIZE  5
typedef  int ele_type;typedef struct queue
{ele_type arr[SIZE];int front;int real;
}  Queue;//初始化队列
void init(Queue* que)
{assert(que);memset(que->arr, 0, sizeof(ele_type) * SIZE);que->front = 0;que->real = 0;
}//插入元素--入队
bool  push_queue(Queue* que, ele_type val)
{assert(que);if ((que->real + 1) % SIZE == que->front)return false;que->arr[que->real] = val;que->real++;que->real = que->real % SIZE;return true;}//删除元素--出队
bool  pop_queue(Queue* que, ele_type* rtval)
{assert(que);if (que->front == que->real)return false;*rtval = que->arr[que->front++];que->front = que->front % SIZE;return true;}//遍历队列
void print_queue(Queue* que)
{if (que->front == que->real)return;if (que->front < que->real){for (int i = que->front; i < que->real; i++){printf("%d\n", que->arr[i]);}}else{for (int i = que->front; i < SIZE; i++){printf("%d\n", que->arr[i]);}for (int i = 0; i < que->real; i++){printf("%d\n", que->arr[i]);}}}//获取数组长度
int get_queue_size(Queue* que)
{return ((que->real - que->front + SIZE) % SIZE);}//清空数组
void Clear_queue(Queue* que)
{que->front = que->real = 0;}int main()
{Queue q;init(&q);push_queue(&q, 11);push_queue(&q, 12);push_queue(&q, 13);push_queue(&q, 14);ele_type temp;pop_queue(&q, &temp);printf("temp=%d\n", temp);pop_queue(&q, &temp);printf("temp=%d\n", temp);pop_queue(&q, &temp);printf("temp=%d\n", temp);push_queue(&q, 15);push_queue(&q, 16);printf("===================\n");print_queue(&q);printf("ele num=%d\n", get_queue_size(&q));return 0;
}

运行结果: