2-4 队列 - 图1

1. 队列的定义

队列，顾名思义，就是一种类似于日常生活中排队的数据结构。假设我们到银行柜台排队办理业务，柜台的服务人员必定先处理队头人员的业务，当有新人排队时，一般都排在队尾。

类似于排队，遵循先进先出，后进后出的数据结构，我们成为队列。

2. 队列的实现

队列可以用链表、数组实现。使用数组实现的队列称为顺序队列，使用链表实现的队列称为链式队列。下面我们一一介绍。

2.1 顺序队列

当我们使用数组实现队列时，首先要考虑的问题是：数组的哪一端作为队头，哪一端作为队尾？
显而易见，应该使用数组头部作为队头，使用数组尾部作为队尾，为什么呢？
若我们采用数组头部作为队尾，那么每次入队时，就必须要进行数据搬移工作，效率非常低下。
虽然将数组头部作为队头也会进行数据搬移工作，但我们可以通过一系列的优化手段，降低其时间复杂度。

  • 我们准备两个指针，表明队头、队尾的位置；
  • 当入队时，队尾指针后移，当出队时，队头指针后移，这样就实现了时间复杂度为2-4 队列 - 图2的入队、出队操作。

那么有同学会问了，这样的话不就会造成一部分内存浪费了吗？事实确实如此，因此我们需要继续优化：

  • 当队尾指针指向数组尾部时，此时若是数组中仍有空闲位置，则将head~tail间的元素搬运到0~（tail-head）位置来，这样就可以继续插入了。

094ba7722eeec46ead58b40c097353c7.webp

接下来我们分析一下时间复杂度：

  • 出队操作因不会触发数据搬移，因此其时间复杂度为2-4 队列 - 图4
  • 入队时，若不涉及数据搬运，则时间复杂度为<最好时间复杂度>
  • 入队时，若不涉及数据搬运，则时间复杂度为2-4 队列 - 图5<最坏时间复杂度>

那么平均时间复杂度呢？
分析整个入队过程，假设数组容量为n，那么在n-1次的时间复杂度为入队操作后，第n次时间复杂度会提升到，此后会一直循环这个过程，直到队满，那么将时间复杂度为的这一次操作均摊到其他n-1次操作后，我们可以得出平均时间复杂度为，也就是最好时间复杂度。

具体代码实现如下：

  1. class CArrayQueue
  2. {
  3. public:
  4.     CArrayQueue(const int &ncount = 10) : m_ncount(ncount)
  5.     {
  6.         if (nullptr != m_strData)
  7.         {
  8.             delete m_strData;
  9.             m_strData = nullptr;
  10.         }
  12.         m_strData = new std::string[ncount];
  13.         if (nullptr == m_strData)
  14.         {
  15.             return;
  16.         }
  17.     }
  19.     ~CArrayQueue()
  20.     {
  21.         if (nullptr != m_strData)
  22.         {
  23.             delete[] m_strData;
  24.             m_strData = nullptr;
  25.         }
  26.     }
  28.     int size()
  29.     {
  30.         return m_ntail - m_nhead;
  31.     }
  33.     bool empty()
  34.     {
  35.         return m_nhead == m_ntail;
  36.     }
  38.     bool full()
  39.     {
  40.         return size() == m_ncount;
  41.     }
  43.     bool enqueue(const std::string &strElem)
  44.     {
  45.         if (full())
  46.         {
  47.             return false;
  48.         }
  50.         if (m_ntail == m_ncount)
  51.         {
  52.             int ntemp  = 0;
  53.             // 执行一次数据搬移操作
  54.             for (int i = m_nhead; i < m_ntail; ++i)
  55.             {
  56.                 m_strData[ntemp++] = m_strData[i];
  57.             }
  59.             m_ntail = m_ntail - m_nhead;
  60.             m_nhead = 0;
  61.         }
  63.         m_strData[m_ntail++] = strElem;
  65.         return true;
  66.     }
  68.     bool dequeue(std::string &strElem)
  69.     {
  70.         if (empty())
  71.         {
  72.             return false;
  73.         }
  75.         strElem = m_strData[m_nhead++];
  77.         return true;
  78.     }
  80.     void print()
  81.     {
  82.         for(int i = m_nhead; i < m_ntail; ++i)
  83.         {
  84.             std::cout << "队列元素_" << i << "内容：" << m_strData[i] << std::endl;
  85.         }
  86.     }
  88. private:
  89.     std::string *m_strData = nullptr; // 队列内容
  90.     int m_ncount = 0;        // 队列容量
  91.     int m_nhead  = 0;        // 队首指针
  92.     int m_ntail  = 0;        // 队尾指针
  93. };

2.2 链式队列

链式队列采用链表实现，我们使用head、tail两个指针分别记录队头，队尾，当入队时，tail->next=new_node，tail=new_node即可，当出队时，new_node->next=head->next，head=new_node。
下面时整个流程示意图：
c916fe2212f8f543ddf539296444d393.webp
代码如下：

  1. struct SNode
  2. {
  3.     std::string m_strData;
  4.     SNode       *m_next;
  5. };
  7. class CListQueue
  8. {
  9. public:
  10.     CListQueue()
  11.     {
  12.         m_head = new SNode;
  13.         if (nullptr == m_head)
  14.         {
  15.             return;
  16.         }
  18.         m_head->m_next = nullptr;
  19.         m_first = m_last = nullptr;
  20.     }
  22.     ~CListQueue()
  23.     {
  24.         SNode *node = nullptr;
  25.         while (nullptr != m_head->m_next)
  26.         {
  27.             node = m_head;
  28.             m_head = m_head->m_next;
  30.             delete node;
  31.             node = nullptr;
  32.         }
  33.     }
  35.     int size()
  36.     {
  37.         SNode *temp = m_first;
  38.         int nb = 0;
  39.         while (nullptr != temp)
  40.         {
  41.             nb++;
  42.             temp = temp->m_next;
  43.         }
  45.         return nb;
  46.     }
  48.     bool empty()
  49.     {
  50.         return 0 == size();
  51.     }
  53.     bool enqueue(const std::string &strElem)
  54.     {
  55.         SNode *node = new SNode;
  56.         if (nullptr == node)
  57.         {
  58.             return false;
  59.         }
  61.         node->m_strData = strElem;
  62.         node->m_next = nullptr;
  64.         if (0 == size())
  65.         {
  66.             m_first = m_last = node;
  67.             m_head->m_next = node;
  69.             return true;
  70.         }
  72.         m_last->m_next = node;
  73.         m_last = m_last->m_next;
  75.         return true;
  76.     }
  78.     bool dequeue(std::string &strElem)
  79.     {
  80.         if (empty())
  81.         {
  82.             return false;
  83.         }
  85.         strElem = m_first->m_strData;
  87.         SNode *temp = m_first;
  89.         m_first = m_first->m_next;
  90.         m_head->m_next = m_first;
  92.         if (nullptr != temp)
  93.         {
  94.             delete temp;
  95.             temp = nullptr;
  96.         }
  97.     }
  99.     void print()
  100.     {
  101.         SNode *temp = m_first;
  102.         int nb = 0;
  103.         while (nullptr != temp)
  104.         {
  105.             std::cout << "队列内容：" << temp->m_strData << std::endl;
  106.             temp = temp->m_next;
  107.         }
  108.     }
  110. private:
  111.     SNode *m_head;     // 头节点
  112.     SNode *m_first;    // 第一个节点
  113.     SNode *m_last;     // 最后一个节点
  114. };

3. 循环队列

上述的顺序队列虽然经过优化之后，效率已经可以了，但是在某些情况下时间复杂度还是退化为2-4 队列 - 图7。那么我们如何继续优化呢？
我们注意到，时间复杂度退化为2-4 队列 - 图8的时候，恰好是搬运数据的时候，那么我们如何避免数据搬运呢？
答案就是我们将数组头部与尾部连接起来，这样就可以省去数据搬运的过程。
具体结构如下图所示：
58ba37bb4102b87d66dffe7148b0f990.webp
看上图可知，当队尾指针达到数组末尾时，并不会增长到8，而是会变为0，这样数据就可以继续入队，我们也通过这一方法成功的避免了数据搬移工作。
循环队列的原理看起来很简单，但是其代码实现很复杂，首先我们需要明确，如何判断队满还是队空？还是依赖于head=tail这一条件判断吗？显示不是！！因为我们发现当队满或队空是都会满足这一条件。因此需要做一些取舍：

  • 采用head=tail 这一条件作为循环队列为空的判定条件
  • 牺牲一个存储单元，当满足(tail + 1) % count = head时，判定循环队列满。

3d81a44f8c42b3ceee55605f9aeedcec.webp
经过上述分析可知，队尾、队头指针可能会由8变为0，那么如何实现这一过程呢？我们仅需要对自增后的指针取模即可，即tail=(tail+1)%ncount head=(head+1)%ncount，同理，计算循环队列元素个数的公式为：size=(tail - head + ncount) % ncount。

代码如下：

  1. class CLoopQueue
  2. {
  3. public:
  4.     CLoopQueue(const int &ncount = 10) : m_ncount(ncount)
  5.     {
  6.         if (nullptr != m_strData)
  7.         {
  8.             delete m_strData;
  9.             m_strData = nullptr;
  10.         }
  12.         m_strData = new std::string[ncount];
  13.         if (nullptr == m_strData)
  14.         {
  15.             return;
  16.         }
  17.     }
  19.     ~CLoopQueue()
  20.     {
  21.         if (nullptr != m_strData)
  22.         {
  23.             delete[] m_strData;
  24.             m_strData = nullptr;
  25.         }
  26.     }
  28.     int size()
  29.     {
  30.         return (m_ntail - m_nhead + m_ncount) % m_ncount;
  31.     }
  33.     bool empty()
  34.     {
  35.         return m_nhead == m_ntail;
  36.     }
  38.     bool full()
  39.     {
  40.         return (m_ntail + 1) % m_ncount == m_nhead;
  41.     }
  43.     bool enqueue(const std::string &strElem)
  44.     {
  45.         if (full())
  46.         {
  47.             return false;
  48.         }
  50.         m_strData[m_ntail] = strElem;
  51.         m_ntail = (m_ntail + 1) % m_ncount;
  53.         return true;
  54.     }
  56.     bool dequeue(std::string &strElem)
  57.     {
  58.         if (empty())
  59.         {
  60.             return false;
  61.         }
  63.         strElem = m_strData[m_nhead];
  64.         m_nhead = (m_nhead + 1) % m_ncount;
  66.         return true;
  67.     }
  69.     void print()
  70.     {
  71.         if (m_nhead < m_ntail)
  72.         {
  73.             for(int i = m_nhead; i < m_ntail; ++i)
  74.             {
  75.                 std::cout << "队列元素_" << i << "内容：" << m_strData[i] << std::endl;
  76.             }
  77.         }
  78.         else
  79.         {
  80.             for(int i = m_nhead; i < m_nhead + m_ncount; ++i)
  81.             {
  82.                 std::cout << "队列元素_" << i % m_ncount << "内容：" << m_strData[i % m_ncount] << std::endl;
  83.             }
  84.         }
  85.     }
  87. private:
  88.     std::string *m_strData = nullptr; // 队列内容
  89.     int m_ncount = 0;        // 队列容量
  90.     int m_nhead  = 0;        // 队首指针
  91.     int m_ntail  = 0;        // 队尾指针
  92. };