队列

与栈不同，他就是现实中排队一样，讲究先来后到，即 先进先出。

打个比方，你告诉朋友我们做地铁去西湖，你输入 "s-u-b", 如果按照栈 先入后出后入先出 的方式，朋友会收到 b-u-s, what？有地铁，我们干嘛做两个小时的汽车？？？ 队列就可以让朋友按你输入的顺序依次收到 s-u-b 。

简单的看一下队列，是线性结构，想到什么？非常熟悉的 线性表 ，有两种存储结构，顺序存储和链式存储。
我们今天先讲一讲队列的顺序存储结构——循环队列

先看一种队列

image
假设开辟一个存储大小为5个内存单元的队列

我列举了四种状态 ：空队列，入队，入队到队满，删除只剩一个元素。
先看前三种：当为空队列时，front和rear都指向了同一个元素，判为空；当入队时，rear向后移动，指向新元素，当出队时，front指向下一个元素；当front=0，rear=4时，整队满，操作貌似没有问题。这一切看似完美。

但是，，，如果如下图，出队到只剩最后一个元素，front和rear又都指向了一个同元素，而且仅在队尾，又要认为队列为空？不可能啊，明明最后一块存储单元还有一个元素，而且却不能继续入队新元素，超出了存储范围，如果要继续利用前面出队的空余空间，又该怎么用？

image

如果 我们把队列设计成下面这样：

image

哈哈，循环了。队尾rear指向下一个位置，而不是当前的队尾元素。

• 如图(b)所示，a先入队 b再入队 C再入队 ，rear指向C后面的位置。
• 如图(c)所示，队首元素a出队，front指向下一个队首b，但是此时front=1，而不再是从0开始，一边出队一边入队，那么front的位置就会是0，1，2，3，4，5 然后利用取模运算front = (front+1) % max,front又回到0，然后1。。。。。 使得每次front的位置可以在队尾之后继续回到标号从0的位置继续往后走，周期循环。同理，rear，新增到rear = 5时，也利用取模运算，新的数据从标号为0开始继续入队，实现循环队列。
• 如果队满是什么样，看下图

image
????? rear指向的下一个位置是队首front的b，哇，还是和之前一样，front==rear， 但是我们已经用循环解决当只有最后一块存储单元有元素而不能再继续入队的问题。

无碍,我们可以牺牲一个front前的存储单元，用来保持队尾和队首的距离，来解决最后一个问题：判断队满，(Q.rear+1) % Q.max == Q.front ， 如果条件成立，意味着空的下一个位置就是队首front，此时队已满
image

这就是循环队列的工作流程

循环队列

将上面的过程做一下整理：

1. 当初始化队列为空时，front = rear = 0；
2. 入队，rear+1，指向队尾的下一个存储单元，为了实现循环利用取模运算：rear = (rear+1) % max;
3. 出队，front+1，指向下一个队首，实现循环：front = (front+1) % max;
4. 判断队满，(Q.rear+1) % Q.max == Q.front

定义

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

/* 队列结构 */
typedef struct
{
    ElemType *data;
    int front;  /* 记录队首元素位置 */
    int rear;   /* 记录对尾元素位置 */
    int max;    /* 记录开辟内存空间的大小 */
}SqQueue;

初始化创建队列

/// 初始化创建队列
/// @param Q 队列指针
/// @param n 指定开辟空间大小，一个空间大小是 sizeof(ElemType)
Status InitQueue(SqQueue *Q, int n)
{
    Q->data = malloc(sizeof(ElemType) * n);
    if (Q->data == NULL) return ERROR;
    
    Q->max = n;
    Q->front = Q->rear = 0;
    
    return OK;
}

获得元素个数

/// 获取队列元素个数(包括rear指向的空位置)
/// @param Q 队列
int GetLength(SqQueue Q)
{
    return (Q.rear - Q.front + Q.max) % Q.max;
}

判断是不是空

Status QueueEmpty(SqQueue Q)
{
    if (Q.front == Q.rear) {
        return OK;
    }
    return ERROR;
}

队满

Status QueueFull(SqQueue Q)
{
    if ((Q.rear+1) % Q.max == Q.front)
    {
        return OK;
    }
    else
    {
        return ERROR;
    }
}

获得队首元素

Status GetFront(SqQueue Q, ElemType *e)
{
    if (QueueEmpty(Q) == OK) {
        return ERROR;
    }
    
    *e = Q.data[Q.front];
    return OK;
}

入队

/// 入队操作
/// @param Q 队列
/// @param e 新数据
Status EnQueue(SqQueue *Q, ElemType e)
{
    // 判断队列有没有满
    if (QueueFull(*Q)) return ERROR;
    
    Q->data[Q->rear] = e;
    // 队尾向后移动，取模运算，超出队尾，实现循环继续从队首开始
    Q->rear = (Q->rear+1) % Q->max;
    
    return OK;
}

出队

/// 出队列
/// @param Q 队列
/// @param e 出的元素
Status DeQueue(SqQueue *Q, ElemType *e)
{
    // 判断对了是不是空
    if (QueueEmpty(*Q) == OK) return ERROR;
    
    *e = Q->data[Q->front];
    // 队首位置向后移动一位
    Q->front = (Q->front+1) % Q->max;
    
    return OK;
}

遍历输出

Status QueuePrint(SqQueue *Q)
{
    /* 从队首开时输出，直到对尾 */
    int i = Q->front;
    while (i != Q->rear) {
        printf("%d ",Q->data[i]);
        i = (i+1) % Q->max;
    }
    printf("\n");
    
    return ERROR;
}

测试输出

指定队列最大存储5个单元，方便观看

int main(int argc, const char * argv[]) {
    
    SqQueue queue;
    InitQueue(&queue, 5);
    
    printf("插入数据:");
    for (int i = 0; i < 30; i++) {
        EnQueue(&queue, i);
    }
    QueuePrint(&queue);
    
    int e ;
    
    printf("出队:");
    if (DeQueue(&queue, &e))
    {
        QueuePrint(&queue);
    }
    if (DeQueue(&queue, &e))
    {
        QueuePrint(&queue);
    }
    
    
    int frontE;
    if (GetFront(queue, &frontE)) {
        printf("队头：%d\n",frontE);
    }
    
    printf("插入数据:");
    scanf("%d",&e);
    EnQueue(&queue, e);
    QueuePrint(&queue);
    
    printf("插入数据:");
    scanf("%d",&e);
    EnQueue(&queue, e);
    QueuePrint(&queue);
    
    printf("插入数据:");
    scanf("%d",&e);
    EnQueue(&queue, e);
    QueuePrint(&queue);
    
    printf("插入数据:");
    scanf("%d",&e);
    EnQueue(&queue, e);
    QueuePrint(&queue);
    
    printf("开始清空队列\n");
    ClearQueue(&queue);
    QueuePrint(&queue);
    
    DestoryQueue(&queue);
    
    return 0;
}

image