如何自己实现一个队列

水深无声 2022-02-25 15:38 277阅读 0赞

## 前言 ##

队列是一种先进先出的数据结构，也是常见的数据结构之一。日常生活中的排队买东西就是一种典型的队列，而在购票系统也需要一个队列处理用户的购票请求，当然这里的队列就复杂多了。本文介绍队列的基本概念和实现。

## 队列常见操作 ##

队列最常见的操作是入队和出队，拿排队买东西来说，入队就是新来一个人排在队伍后面，而出队就是一个人已经结账离开。

## 队列基本实现考虑 ##

与实现栈不同，它需要两个指针，一个指向队头（front），一个指向队尾（rear），这样才能方便地进行入队或出队操作，因此队列的实现要比栈难一些。在说明如何实现一个队列之前，先看实现一个队列可能需要注意哪些问题。

假如我们使用数组按照实现栈的方式来实现队列。并且队列中的数据如下：

<table> 
 <thead style="font-size:inherit;color:inherit;line-height:inherit;"> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">0</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">1</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">2</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">3</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">4</th> 
  </tr> 
 </thead> 
 <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">10</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">11</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">12</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">13</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">14</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">front</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">rear</td> 
  </tr> 
 </tbody> 
</table>

这个时候从队头front处删除一个数据，是很容易的。

<table> 
 <thead style="font-size:inherit;color:inherit;line-height:inherit;"> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">0</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">1</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">2</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">3</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">4</th> 
  </tr> 
 </thead> 
 <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">11</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">12</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">13</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">14</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">front</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">rear</td> 
  </tr> 
 </tbody> 
</table>

但是如果要入队一个数据呢？这个时候发现队尾已经没有空间了，为了入队一个元素，必须将所有元素都往队头移动，这似乎很符合我们排队的习惯，前面一个人走了，后面的人都往前一个位置。**但是在数组中，将所有的元素都往队头移动的开销是不容忽略的！**

有人可能已经注意到了，原来删除的地方还有一个空位呢，不如把新的元素加入到这里，然后将尾指针rear指向该处即可。没错，这就相当于**把该数组当成了一个循环数组**，即可以看成数组尾部和头部是连着的。这个时候就变成了下面的情况：

<table> 
 <thead style="font-size:inherit;color:inherit;line-height:inherit;"> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">0</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">1</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">2</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">3</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">4</th> 
  </tr> 
 </thead> 
 <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">15</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">11</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">12</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">13</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">14</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">rear</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">front</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
  </tr> 
 </tbody> 
</table>

此时，队列是满的，rear指向下标0处，而front指向下标1处。如果这个时候删除这五个元素，就变成下面的情况：

<table> 
 <thead style="font-size:inherit;color:inherit;line-height:inherit;"> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">0</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">1</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">2</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">3</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">4</th> 
  </tr> 
 </thead> 
 <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">rear</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">front</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
  </tr> 
 </tbody> 
</table>

我们发现队列为空时，rear指向下标0处，而front指向下标1处，与队列满时是一样的，这样的话，如何区分队列是空还是满呢？

很明显，队列为空时与队列满时元素数量是不一样的，我们可以通过**判断队列中元素的数量是否已达上限，来判断队列是否为空。**

还有一种方法，就是使得**队列满时，不占满整个数组，而保留一个空位。这样的情况下，队列满时，两个指针相隔2**：

<table> 
 <thead style="font-size:inherit;color:inherit;line-height:inherit;"> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">0</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">1</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">2</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">3</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">4</th> 
  </tr> 
 </thead> 
 <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">15</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">12</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">13</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">14</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">rear</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">front</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
  </tr> 
 </tbody> 
</table>

队列空时：

<table> 
 <thead style="font-size:inherit;color:inherit;line-height:inherit;"> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">0</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">1</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">2</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">3</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">4</th> 
  </tr> 
 </thead> 
 <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">rear</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">front</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> 
  </tr> 
 </tbody> 
</table>

两个指针相隔1。那么就可以通过指针的间隔来判断队列是否为空了。

这里就说明了队列实现需要考虑的两个问题：

*  如何高效地将元素入队
 *  如何判断队列为空或队列为满

当然了，如果你使用链表实现队列，那么入队也完全不需要搬移数据。

## 实现 ##

队列的实现有多种方式可以选择，例如：

*  静态数组，容量固定，操作简便，效率高
 *  动态数组，容量可自定义，操作简便，因为涉及内存的申请与释放，因此实现比静态数组稍微复杂一点点
 *  链表，容量理论上只受限于内存，实现也较为复杂
 *  其他

因篇幅有限，本文只选择一种实现进行说明。

本文的代码实现采用了静态数组实现一个队列，并且为了避免数据频繁搬移，使用了前面介绍的循环队列；为了测试队满的情况，将队列的容量设置成了很小的值，另外，也通过保留一个空位的方式来解决队空和队满无法区分的问题。

队列的主要定义或操作解释如下。

*  队列结构定义，定义一个结构体，包含存储队头位置和队尾位以及队列数组
 *  队列初始化，初始时，队尾值为0，队头值为1，两者差值为1
 *  队列是否为空，队尾和队头差值并取模为1时，表明队列为空
 *  队列是否已满，队尾和队头差值取模为2时，表明队列满
 *  入队，入队前检查队列是否已满，如未满，队尾加1取模，并赋值
 *  出队，出队前检查队列是否为空，如不空，则取值，并加1取模

## 代码 ##

完整可运行代码实现如下：

//arrayQueue.c
    #include <stdio.h>
    #include <string.h>
    typedef int ElementType;
    
    /*为测试，将容量值定为较小值5*/
    #define MAX_SIZE 5
    
    /*定义队列结构*/
    typedef struct QueueInfo
    {
         
        int front; //队头位置
        int rear;  //队尾位置
        ElementType queueArr[MAX_SIZE];//队列数组
    }QueueInfo;
    
    #define SUCCESS 0
    #define FAILURE 1
    #define FALSE 0
    #define TRUE 1
    
    /*判断队列是否已满*/
    int queue_is_full(QueueInfo *queue)
    {
        
        if((queue->rear + 2) % MAX_SIZE == queue->front)
        {
        
            printf("queue is full\n");
            return TRUE;
        }
        else         return FALSE;
    }
    /*判断队列是否为满*/
    int queue_is_empty(QueueInfo *queue)
    {
        
        if((queue->rear + 1) % MAX_SIZE == queue->front)
        {
        
            printf("queue is empty\n");
            return TRUE;
        }
        else         return FALSE;
    }
    
    /*出队*/
    int queue_delete(QueueInfo *queue,ElementType *value)
    {
        
        if(queue_is_empty(queue))
            return FAILURE;
    
        *value = queue->queueArr[queue->front];
        printf("get  value from front %d  is %d\n",queue->front,*value);
        queue->front = (queue->front + 1) % MAX_SIZE;
        return SUCCESS;
    }
    
    /*入队*/
    int queue_insert(QueueInfo *queue,ElementType value)
    {
        
        if(queue_is_full(queue))
            return FAILURE;
    
        queue->rear = (queue->rear + 1) % MAX_SIZE;
        queue->queueArr[queue->rear] = value;
        printf("insert %d  to %d\n",value,queue->rear);
        return SUCCESS;
    }
    int main(void)
    {
        
        /*队列初始化*/
        QueueInfo queue;
        memset(&queue,0,sizeof(queue));
        queue.front = 1;
        queue.rear = 0;
    
        /*入队6个数据，最后两个入队失败*/
        queue_insert(&queue,5);
        queue_insert(&queue,4);
        queue_insert(&queue,3);
        queue_insert(&queue,2);
        queue_insert(&queue,1);
        queue_insert(&queue,0);
    
        /*出队6个数据，最后两个出队失败*/
        ElementType a = 0;
        queue_delete(&queue,&a);
        queue_delete(&queue,&a);
        queue_delete(&queue,&a);
        queue_delete(&queue,&a);
        queue_delete(&queue,&a);
        queue_delete(&queue,&a);
        return 0;
    }

编译：

$ gcc  -o arrayQueue arrayQueue.c

运行结果：

insert 5  to 1
    insert 4  to 2
    insert 3  to 3
    insert 2  to 4
    queue is full
    queue is full
    get  value from front 1  is 5
    get  value from front 2  is 4
    get  value from front 3  is 3
    get  value from front 4  is 2
    queue is empty
    queue is empty

## 总结 ##

与《[栈的实现][Link 1]》相比，队列的数组实现相对来说稍微复杂一点，因为它需要考虑队空和对满的区别，以及考虑数据搬移的性能影响，但是从实现本身来看，代码并不复杂。关于队列的动态数组和链表实现可自己尝试。