队列_双向队列

一、什么是队列？

队列是一种特殊的线性表，单向队列只能在一端插入数据（后），另一端删除数据（前）；它和栈一样，队列是一种操作受限制的线性表；进行插入操作的称为队尾，进行删除操作的称为队头；队列中的数据被称为元素；没有元素的队列称为空队列。

由于只能一端删除或者插入，所以只有最先进入队列的才能被删除，因此又被称为先进先出（FIFO—first in first out）线性表。

队列分为两种：双向队列和单向队列 

单向队列：只能在一端删除数据，另一端插入数据。

双向队列：两端都可以进行插入数据和删除数据操作。

1、定义
    　队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表

       （1）允许删除的一端称为队头（Front）。
　　（2）允许插入的一端称为队尾（Rear）。
　　（3）当队列中没有元素时称为空队列。
　　（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
    　队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。
　【例】在队列中依次加入元素a1，a2，…，an之后，a1是队头元素，an是队尾元素。退出队列的次序只能是a1，a2，…，an。
 

二、队列的基本逻辑运算

（1）InitQueue（Q）
    　置空队。构造一个空队列Q。

（2）QueueEmpty（Q）
    　判队空。若队列Q为空，则返回真值，否则返回假值。

（3） QueueFull（Q）
    　判队满。若队列Q为满，则返回真值，否则返回假值。
  注意：

    　此操作只适用于队列的顺序存储结构。

（4） EnQueue（Q，x）
    　若队列Q非满，则将元素x插入Q的队尾。此操作简称入队。

（5） DeQueue（Q）
    　若队列Q非空，则删去Q的队头元素，并返回该元素。此操作简称出队。

（6） QueueFront（Q）
    　若队列Q非空，则返回队头元素，但不改变队列Q的状态。

三.循环队列中判断队满与队空

在引用循环队列前，我们需要了解队列是如何线性实现的（下图有错，x=sq[front++]）。 
 
简单地讲，便是当队列为空时，front = rear = 0,每当插入元素尾指针+1，删除元素是头指针+1。但是，我们会发现一个问题，如上面的第四个图，0，1，2三个空间并没有使用。因此，为了占用该空间，我们使用了循环队列来实现。 
循环队列原理图： 
 
我们可以发现，当循环队列属于上图的d1情况时，是无法判断当前状态是队空还是队满。为了达到判断队列状态的目的，可以通过牺牲一个存储空间来实现。 
如上图d2所示， 
队头指针在队尾指针的下一位置时，队满。 Q.front == (Q.rear + 1) % MAXSIZE 因为队头指针可能又重新从0位置开始，而此时队尾指针是MAXSIZE - 1，所以需要求余。 
当队头和队尾指针在同一位置时，队空。 Q.front == Q.rear;

以下是实现的代码：

1. #include <stdio.h>

2. #include <malloc.h>

3. #define MAXSIZE 100 //最大队列长度

4. #define OK 1

5. #define ERROR 0

6. typedef int ElemType;

7. typedef int Status;

8.  

9. typedef struct {

10. ElemType *base; //队列空间

11. int front; //队头指针

12. int rear; //队尾指针，若队尾不为空，则指向队尾元素的下一个位置

13. }SqQueue;

14.  

15. //初始化循环队列

16. Status initQueue(SqQueue &Q) {

17. Q.base = (ElemType *) malloc(MAXSIZE * sizeof(ElemType)); //申请空间

18. Q.front = Q.rear = 0; //队空

19. return OK;

20. }

21.  

22. //入队

23. Status enQueue(SqQueue &Q, ElemType e) {

24. if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR; //队满，无法添加

25. Q.base[Q.rear] = e; //插入元素

26. Q.rear = (Q.rear + 1) % MAXSIZE; //队尾指针+1

27. return OK;

28. }

29.  

30. //出队

31. Status deQueue(SqQueue &Q, ElemType &e) {

32. if (Q.front == Q.rear) return ERROR; //队空，无法删除

33. e = Q.base[Q.front];

34. Q.front = (Q.front + 1) % MAXSIZE; //队头指针+1

35. return OK;

36. }

37.  

38. //返回队列长度

39. Status length(SqQueue &Q) {

40. return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;

41. }

刷题巩固：

Reference:

[1]:https://blog.csdn.net/weixin_42228950/article/details/90209370

[2]:https://www.xuebuyuan.com/1951200.html