C++ 队列

在 C++ 中，STL queue 提供了队列数据结构的功能。

队列数据结构遵循 先进先出 (FIFO) 原则，即先添加的元素先被移除。

推荐阅读

• 队列数据结构
• C++ STL

创建 C++ STL 队列

为了在 C++ 中创建队列，我们首先需要包含 queue 头文件。

#include <queue>

导入此文件后，我们可以使用以下语法创建 queue

queue<type> q;

在此，type 表示我们要存储在队列中的 数据类型。例如，

// create a queue of integer data type
queue<int> integer_queue;

// create a queue of string data type
queue<string> string_queue;

C++ 队列方法

在 C++ 中，queue 是一个 类，它提供了各种方法来对队列执行不同的操作。

向队列插入元素

我们使用 push() 方法将元素插入队列的末尾。例如，

#include <iostream>
#include <queue>

using namespace std;

int main() {

  // create a queue of string
  queue<string> animals;

  // push elements into the queue
  animals.push("Cat");
  animals.push("Dog");
  
  cout << "Queue: ";

  // print elements of queue
  // loop until queue is empty
  while(!animals.empty()) {

    // print the element
    cout << animals.front() << ", ";

    // pop element from the queue
    animals.pop();
  }

  cout << endl;
 
  return 0;
}

输出

Queue: Cat, Dog,

在上面的示例中，我们创建了一个名为 animals 的 字符串 队列。在这里，我们使用 push() 方法将元素添加到队列的末尾。

animals.push("Cat");
animals.push("Dog");

我们没有直接打印队列的内容，而是使用了 while 循环和各种队列方法。

while(!animals.empty()) {
  cout << animals.front() << ", ";
  animals.pop();
}

这是因为 STL 队列是 STL 容器适配器，它提供受限的访问，使其行为类似于标准队列数据结构。

因此，我们不能像遍历 向量 或其他 容器 那样遍历队列。

相反，我们在循环中重复打印其 front 然后 pop 元素，直到队列为空。

我们将在接下来的部分中学习 pop()、front() 和 empty()。

从队列中移除元素

我们可以使用 pop() 方法从队列的头部移除一个元素。例如，

#include <iostream>
#include <queue>
using namespace std;

// function prototype for display_queue utility
void display_queue(queue<string> q);

int main() {

  // create a queue of string
  queue<string> animals;

  // push element into the queue
  animals.push("Cat");
  animals.push("Dog");
  animals.push("Fox");
  
  cout << "Initial Queue: ";
  display_queue(animals);
  
  // remove element from queue
  animals.pop();
  
  cout << "Final Queue: ";
  display_queue(animals);
  
  return 0;
}

// utility function to display queue
void display_queue(queue<string> q) {
  while(!q.empty()) {
    cout << q.front() << ", ";
    q.pop();
  }

  cout << endl;
}

输出

Initial Queue: Cat, Dog, Fox, 
Final Queue: Dog, Fox, 

在上面的示例中，我们使用 pop() 方法从队列中移除一个元素。

最初，队列的内容是 "Cat"、"Dog" 和 "Fox"。

// removes front element
animals.pop();

这里的 animals.pop() 移除了队列头部的元素，即最先插入的元素 "Cat"。

因此，最终的队列包含元素 "Dog" 和 "Fox"。

访问队列中的元素

我们可以使用以下方法访问 queue 的元素

• front() - 返回队列头部的元素
• back() - 返回队列尾部的元素

例如，

#include <iostream>
#include <queue>
using namespace std;

int main() {

  // create a queue of int
  queue<int> nums;

  // push element into the queue
  nums.push(1);
  nums.push(2);
  nums.push(3);
  
  // get the element at the front
  int front = nums.front();
  cout << "First element: " << front << endl;
  
  // get the element at the back
  int back = nums.back();
  cout << "Last element: " << back << endl;
  
  return 0;
}

输出

First element: 1
Last element: 3

在上面的示例中，我们使用了 front() 和 back() 方法来获取名为 nums 的整数队列的第一个和最后一个元素。

我们可以使用以下方法获取第一个元素，即队列头部的元素

// returns 1
nums.front()

这里，1 是第一个插入的，所以它在队列头部。

类似地，我们使用以下方法找到最后一个元素，即队列尾部 (back) 的元素

// returns 3
nums.back()

这里，3 是最后一个插入的，所以它在队列尾部。

获取队列的大小

我们使用 size() 方法获取 queue 中的元素数量。例如，

#include <iostream>
#include <queue>
using namespace std;

int main() {

  // create a queue of string
  queue<string> languages;

  // push element into the queue
  languages.push("Python");
  languages.push("C++");
  languages.push("Java");
  
  // get the size of the queue
  int size = languages.size();
  cout << "Size of the queue: " << size;

  return 0;
}

输出

Size of the queue: 3

在上面的示例中，我们创建了一个名为 languages 的字符串队列并向其中添加了三个元素。

然后，我们使用 size() 方法查找队列中的元素数量

// returns 3
languages.size();

由于我们向队列添加了三个元素，所以 languages.size() 返回 3。

检查队列是否为空

我们使用 empty() 方法来检查 queue 是否为空。此方法返回

• 1 (true) - 如果队列为空
• 0 (false) - 如果队列不为空

例如，

#include <iostream>
#include <queue>
using namespace std;

int main() {

  // create a queue of string
  queue<string> languages;
  
  cout << "Is the queue empty? ";

  // check if the queue is empty  
  if (languages.empty()) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

  cout << "Pushing elements..." << endl;

  // push element into the queue
  languages.push("Python");
  languages.push("C++");
 
  cout << "Is the queue empty? ";

  // check if the queue is empty  
  if (languages.empty()) {
    cout << "Yes";
  }
  else {
    cout << "No";
  }

  return 0;
}

输出

Is the queue empty? Yes
Pushing elements...
Is the queue empty? No

在上面的示例中，我们使用了 empty() 方法来确定 queue 是否为空，

if (languages.empty()) {
  cout << "Yes" << endl;
}
else{
  cout << "No" << endl; 
}

最初，队列中没有元素。因此 languages.empty() 返回 true。

然后我们向队列添加元素。

然后我们再次使用 languages.empty() 来确定队列是否为空。这次，它返回 false。

另请阅读

• C++ 优先队列
• C++ 双端队列
• C++ 栈