队列

定义

队列是一种特殊的线性表，遵循先进先出（First In First Out，FIFO）的原则。可以进行入队（在队尾添加元素）和出队（从队首移除元素）操作。

运用情况

1. 任务调度：安排任务按照顺序执行。
2. 排队系统：如银行排队、打印任务排队等。
3. 广度优先搜索：用于保存待扩展的节点。
4. 多线程中的任务队列。
5. 网络通信中的数据包队列。

注意事项

1. 要注意队列的容量限制，避免溢出。
2. 操作队列时要确保队首和队尾指针的正确性。
3. 考虑多线程环境下的同步问题，防止数据竞争。

解题思路

1. 明确问题是否适合用队列来解决，通常涉及顺序处理、排队等场景。
2. 创建队列对象并进行初始化。
3. 按照 FIFO 原则进行入队和出队操作。
4. 在处理过程中注意边界情况和异常情况。
5. 根据具体需求，合理利用队列的特性来实现算法逻辑。

例如，在广度优先搜索中，先将起始节点入队，然后不断取出队首节点并扩展，将新节点入队，如此循环直到找到目标或遍历完所有可能。

Acwing.829模拟队列

题目描述

829. 模拟队列 - AcWing题库

运行代码

#include <iostream>  
#include <deque>  
#include <string>  using namespace std;  deque<int> q; // 队列  void push(int x) {  q.push_back(x); // 在队尾插入元素  
}  void pop() {  if (!q.empty()) {  q.pop_front(); // 从队头弹出元素  }  
}  void emptyOperation() {  if (q.empty()) {  cout << "YES" << endl;  } else {  cout << "NO" << endl;  }  
}  void queryOperation() {  if (!q.empty()) {  cout << q.front() << endl; // 查询队头元素  }  
}  int main() {  int M;  cin >> M;  while (M--) {  string op;  cin >> op;  if (op == "push") {  int x;  cin >> x;  push(x);  } else if (op == "pop") {  pop();  } else if (op == "empty") {  emptyOperation();  } else if (op == "query") {  queryOperation();  }  }  return 0;  
}

代码思路

1. 定义队列：使用C++标准库中的std::deque（双端队列）来存储队列的元素。std::deque提供了在队列两端进行高效插入和删除操作的能力，因此非常适合实现队列。

2. 定义操作函数：

   • push(int x)：向队列的尾部插入一个元素x。这是通过调用deque的push_back成员函数实现的。
   • pop()：从队列的头部删除一个元素。这是通过调用deque的pop_front成员函数实现的。这里假设操作总是合法的，所以没有检查队列是否为空。
   • emptyOperation()：检查队列是否为空，并输出相应的结果。如果队列为空，输出"YES"，否则输出"NO"。
   • queryOperation()：查询队列的头部元素并输出。如果队列不为空，输出头部元素的值。

3. 主函数处理：

   • 读取操作次数M。
   • 使用循环处理M个操作。
   • 对于每个操作，首先读取操作类型（字符串）。
   • 根据操作类型调用相应的操作函数。对于push操作，还需要读取要插入的元素值。

4. 错误处理：在这个实现中，没有显式的错误处理，因为题目描述保证所有操作都是合法的。但在实际应用中，你可能需要添加错误处理来确保输入的有效性。

5. 输出：根据操作类型，emptyOperation和queryOperation函数会输出相应的结果。

改进思路

1. 减少不必要的函数调用：在push和pop操作中，由于我们知道std::deque已经提供了高效的push_back和pop_front成员函数，我们可以直接在main函数中调用这些成员函数，而不是通过额外的函数来封装它们。

2. 避免重复代码：在emptyOperation和queryOperation中，我们都在检查队列是否为空。为了避免重复，我们可以将检查队列是否为空的逻辑放在一个单独的函数中。

3. 输入校验：虽然题目保证输入是合法的，但在实际情况下，我们可能想要添加一些输入校验来确保代码的健壮性。

改进代码

#include <iostream>  
#include <deque>  
#include <string>  using namespace std;  deque<int> q; // 队列  bool isEmpty() {  return q.empty();  
}  void processCommands(int M) {  for (int i = 0; i < M; ++i) {  string op;  cin >> op;  if (op == "push") {  int x;  cin >> x;  q.push_back(x); // 直接在main函数中调用push_back  } else if (op == "pop") {  if (!isEmpty()) { // 检查队列是否为空  q.pop_front(); // 直接在main函数中调用pop_front  }  } else if (op == "empty") {  cout << (isEmpty() ? "YES" : "NO") << endl;  } else if (op == "query") {  if (!isEmpty()) { // 检查队列是否为空  cout << q.front() << endl; // 查询队头元素  }  }  }  
}  int main() {  int M;  cin >> M;  processCommands(M);  return 0;  
}