数据结构与算法10-循环队列(顺序存储)

队列

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

相关定义

• 队列：它是一种操作受限的线性表，其限制在表的一端进行插入，另一端进行删除。
• 对尾、对头：可进行插入的一端称为队尾（rear）,可进行删除的一端称为队头（front）
• 入队、出队：向队中插入元素叫入队，新元素进入之后就称为新的队尾元素。从队中删除元素叫出队，元素出队后，其后继结点元素就称为新的队头元素。

队列的两种存储结构，顺序存储和链式存储。 我们今天先讲一讲队列的顺序存储结构——循环队列

为什么要有循环队列的设计 - 假溢出

image.png

假设开辟一个存储大小为5个内存单元的队列
我列举了四种状态 ：空队列，入队，入队到队满，删除只剩一个元素。
先看前三种：当为空队列时，front和rear都指向了同一个元素，判为空；当入队时，rear向后移动，指向新元素，当出队时，front指向下一个元素；当front=0，rear=4时，整队满，操作貌似没有问题。这一切看似完美。
但是，，，如果如下图，出队到只剩最后一个元素，front和rear又都指向了一个同元素，而且仅在队尾，又要认为队列为空？不可能啊，明明最后一块存储单元还有一个元素，而且却不能继续入队新元素，超出了存储范围，如果要继续利用前面出队的空余空间，又该怎么用？

image.png

因此需要设计成循环结构来解决这个问题

image.png

• 如图(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.png

rear指向的下一个位置是队首front的b，还是和之前一样，front==rear， 但是我们已经用循环解决当只有最后一块存储单元有元素而不能再继续入队的问题。
无碍,我们可以牺牲一个front前的存储单元，用来保持队尾和队首的距离，来解决最后一个问题：判断队满，(Q.rear+1) % Q.max == Q.front ， 如果条件成立，意味着空的下一个位置就是队首front，此时队已满

image.png

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

循环队列

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

• 当初始化队列为空时，front = rear = 0；
• 入队，rear+1，指向队尾的下一个存储单元，为了实现循环利用取模运算：rear = (rear+1) % max;
• 出队，front+1，指向下一个队首，实现循环：front = (front+1) % max;
• 判断队满，(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;
}