[数据结构与算法]数据结构---3.队列

数据结构—3.队列

一、队列的理解

1. 队列的特点：生活中都有过排队取快递的经历，当我们去排队的时候，往往我们是最后一个，但我们的后面一定会有人来，成为最后一个。前面排队的也肯定是比我先离开的，最前面的离开后，他后面的又变成了队列的头，业务都是最前面的人先办理的。抽象出来的话，队列一定是有一个头和尾的，而且一开始头和尾是同一个，其次就是先进入队列的人先出去，这里与栈不同。

2. 图示
   

3. 函数实现

   1、入队列：队列的尾自增，依次往后。

   2、出队列：队列的头自增，依次往后。

   3、判断队列是否为空：头 == 尾？

/*
 * @name 队列的实现
 * @Date 2021年11月21日
 * @Author 机器人工程师sgk
*/

#include <stdio.h>

#define SIZE 512

char queue[SIZE];
int head, tail = 0;//队列的两个关键要素，头和尾。

void enqueue(char c);
char dequeue(void);
int is_empty(void);

int main(void)
{


        return 0;
}

/*
 * @name enqueue
 * @brief 入队列。
 * @param char 型数据
 * @retval None
*/
void enqueue(char c)
{
        queue[tail++] = c;//不断有元素入队列，表现形式是队列的尾在不断增加。
}

/*
 * @name dequeue
 * @brief 出队列
 * @param None
 * @retval char 型数据。
*/
char dequeue(void)
{ 
       return queue[head++];//出队列，队列的头不断增加。
}

/*
 * @name is_empty 
 * @brief 判断队列是否为空。
 * @param None
 * @retval int型数据类型
*/
int is_empty(void)
{
        return head == tail;
}

以上代码基本实现的队列的操作。但是，如果此时我们的队列是有限个数，在不断入队列和出队列的过程中，队列尾超出了队列的最大长度，换言之就是溢出了，但是，此时，之前出队列的位置还是空着的，这种情况怎么办？

4. 假溢出

   

如图所示：

为了改进这种情况，我们提出了循环队列的概念。

5. 循环队列

   1、当队列数据存储到队列的尾时，如果前面有空的位置，队列尾可以继续到队列开始的地方继续存储。

   2、如果此时存储过程中，又遇到了Head = Tail的情况，说明队列存储满了。但是，开始时用来判断队列是否为空也是这个条件。所以改进的方法是：浪费一个存储空间用来判断，当Tail + 1 == Head，说明队列存储满了。

   在之前的代码基础上添加判断队列是否满了的判断函数。

   /*
    * @name is_full 
    * @brief 判断队列是否存满了。
    * @param None
    * @retval int型数据类型
   */
   int is_full(void)
   {
           return tail + 1 == head;
   }
   

   6. 环形队列的提出

      1、

      

   如果，当我的tail到了最后一个存储空间，标号为：7，此时，tail + 1 = 8，tail ！= head（此时head == 0），如何解决这个问题，这里直接拿出解决方法。一个不大于最大值的数，其+1后对最大值取余运算后还是其本身 。比如这里的最大值就是存储空间的最大容量为8，（tail + 1）% 8 = 0。问题解决！

   更新后的程序如下：

   /*
    * @name 队列的实现
    * @Date 2021年11月21日
    * @Author 机器人工程师sgk
   */
   
   #include <stdio.h>
   
   #define SIZE 512
   
   char queue[SIZE];
   int head, tail = 0;//队列的两个关键要素，头和尾。
   
   void enqueue(char c);
   char dequeue(void);
   int is_empty(void);
   int is_full(void);
   
   int main(void)
   {
           int i;
           char temp = 'A';
   
           if(!is_full())
           {
                   for(i = 0; i < 5; i++)
                   {
                           enqueue(temp);
                           temp++;
                   }
           }
   
           while(!is_empty())
           {
                   printf("%c\n", dequeue());
           }
   
           return 0;
   }
   
   /*
    * @name enqueue
    * @brief 入队列。
    * @param char 型数据
    * @retval None
   */
   void enqueue(char c)
   {
           if(!is_full())
                   queue[tail++] = c;//不断有元素入队列，表现形式是队列的尾在不断增加。
           tail = (tail + 1) % SIZE;//更新尾的方式也变了，因为在环形队列中嘛，这个很有必要。
   }
   
   /*
    * @name dequeue
    * @brief 出队列
    * @param None
    * @retval char 型数据。
   */
   char dequeue(void)
   {
           char ch;
           if(!is_empty())
                   ch = queue[head++];
           return ch;//出队列，队列的头不断增加。
   }
   
   /*
    * @name is_empty 
    * @brief 判断队列是否为空。
    * @param None
    * @retval int型数据类型
   */
   int is_empty(void)
   {
           return head == tail;
   }
   
   /*
    * @name is_full 
    * @brief 判断队列是否存满了。
    * @param None
    * @retval int型数据类型
   */
   int is_full(void)
   {
           return ((tail + 1) % SIZE) == head;
   }
   

   运行结果：

   sgk@sgk-VirtualBox:~/C_Study/DataStructure$ gcc queue.c && ./a.out
   A
   B
   C
   D
   E