《数据结构》--队列【各种实现，算法推荐】

一、认识队列

队列是一种常见的数据结构，按照先进先出（FIFO，First In First Out）的原则排列数据。也就是说，最早进入队列的元素最先被移除。队列主要支持两种基本操作：

入队（enqueue）：将元素添加到队列的尾部。

出队（dequeue）：从队列的头部移除并返回元素。

队列的其他操作：

创建队列：初始化一个空队列。

查看队列头部元素：返回但不移除队列的头部元素（通常称为“peek”或“front”）。

判断队列是否为空：检查队列中是否还有元素。

获取队列大小：返回队列中元素的数量。

1.顺序队列

顺序队列即用顺序结构存储，数组实现：

#include <iostream>  class Queue {  
private:  int* arr;  int front;  int rear;  int capacity;  
public:  Queue(int size) {  arr = new int[size];  capacity = size;  front = 0;  rear = -1;  }  ~Queue() {  delete[] arr;  }  void enqueue(int item) {  if (rear == capacity - 1) {  std::cout << "Queue is full!" << std::endl;  return;  }  arr[++rear] = item;  }  int dequeue() {  if (is_empty()) {  std::cout << "Queue is empty!" << std::endl;  return -1; // 或抛出异常  }  return arr[front++];  }  int peek() {  if (is_empty()) {  std::cout << "Queue is empty!" << std::endl;  return -1; // 或抛出异常  }  return arr[front];  }  bool is_empty() const {  return front > rear;  }  int size() const {  return rear - front + 1;  }  
};  int main() {  Queue q(5);  q.enqueue(10);  q.enqueue(20);  q.enqueue(30);  std::cout << "Front element: " << q.peek() << std::endl; // 输出 10  std::cout << "Dequeued element: " << q.dequeue() << std::endl; // 输出 10  std::cout << "Queue size: " << q.size() << std::endl; // 输出 2  return 0;  
}

2.链式队列

链式队列即用链式存储，用链表实现：

#include <iostream>  class Node {  
public:  int data;  Node* next;  Node(int value) : data(value), next(nullptr) {}  
};  class Queue {  
private:  Node* front;  Node* rear;  int size;  
public:  Queue() : front(nullptr), rear(nullptr), size(0) {}  ~Queue() {  while (!is_empty()) {  dequeue();  }  }  void enqueue(int item) {  Node* newNode = new Node(item);  if (rear) {  rear->next = newNode;  }  rear = newNode;  if (!front) {  front = rear;  }  size++;  }  int dequeue() {  if (is_empty()) {  std::cout << "Queue is empty!" << std::endl;  return -1; // 或抛出异常  }  Node* temp = front;  int value = front->data;  front = front->next;  delete temp;  if (!front) {  rear = nullptr; // 队列变空  }  size--;  return value;  }  int peek() {  if (is_empty()) {  std::cout << "Queue is empty!" << std::endl;  return -1; // 或抛出异常  }  return front->data;  }  bool is_empty() const {  return size == 0;  }  int get_size() const {  return size;  }  
};  int main() {  Queue q;  q.enqueue(10);  q.enqueue(20);  q.enqueue(30);  std::cout << "Front element: " << q.peek() << std::endl; // 输出 10  std::cout << "Dequeued element: " << q.dequeue() << std::endl; // 输出 10  std::cout << "Queue size: " << q.get_size() << std::endl; // 输出 2  return 0;  
}

 二、双端队列

1.顺序双端队列

#include <iostream>  class Deque {  
private:  int* arr;  int front;  int rear;  int capacity;  
public:  Deque(int size) {  arr = new int[size];  capacity = size;  front = -1;  rear = 0;  }  ~Deque() {  delete[] arr;  }  void insertFront(int item) {  if (is_full()) {  std::cout << "Deque is full!" << std::endl;  return;  }  if (is_empty()) {  front = 0;  rear = 0;  } else {  front = (front - 1 + capacity) % capacity; // 循环移动前指针  }  arr[front] = item;  }  void insertRear(int item) {  if (is_full()) {  std::cout << "Deque is full!" << std::endl;  return;  }  if (is_empty()) {  front = 0;  rear = 0;  } else {  rear = (rear + 1) % capacity; // 循环移动后指针  }  arr[rear] = item;  }  int deleteFront() {  if (is_empty()) {  std::cout << "Deque is empty!" << std::endl;  return -1; // 或抛出异常  }  int item = arr[front];  if (front == rear) { // 仅有一个元素  front = -1;  rear = 0;  } else {  front = (front + 1) % capacity; // 循环移动前指针  }  return item;  }  int deleteRear() {  if (is_empty()) {  std::cout << "Deque is empty!" << std::endl;  return -1; // 或抛出异常  }  int item = arr[rear];  if (front == rear) { // 仅有一个元素  front = -1;  rear = 0;  } else {  rear = (rear - 1 + capacity) % capacity; // 循环移动后指针  }  return item;  }  int getFront() const {  if (is_empty()) {  std::cout << "Deque is empty!" << std::endl;  return -1; // 或抛出异常  }  return arr[front];  }  int getRear() const {  if (is_empty()) {  std::cout << "Deque is empty!" << std::endl;  return -1; // 或抛出异常  }  return arr[rear];  }  bool is_empty() const {  return front == -1;  }  bool is_full() const {  return (rear + 1) % capacity == front;  }  
};  int main() {  Deque dq(5);  dq.insertRear(10);  dq.insertRear(20);  dq.insertFront(5);  dq.insertFront(0);  std::cout << "Front element: " << dq.getFront() << std::endl; // 输出 0  std::cout << "Rear element: " << dq.getRear() << std::endl;   // 输出 20  dq.deleteFront(); // 删除 0  dq.deleteRear();  // 删除 20  std::cout << "Front element after deletions: " << dq.getFront() << std::endl; // 输出 5  return 0;  
}

2.链式双端队列

双端队列的链式存储，采用双向链表来实现模拟：

#include <iostream>  class Node {  
public:  int data;  Node* next;  Node* prev;  Node(int value) : data(value), next(nullptr), prev(nullptr) {}  
};  class Deque {  
private:  Node* front;  Node* rear;  
public:  Deque() : front(nullptr), rear(nullptr) {}  ~Deque() {  while (!is_empty()) {  deleteFront();  }  }  void insertFront(int item) {  Node* newNode = new Node(item);  if (is_empty()) {  front = rear = newNode;  } else {  newNode->next = front;  front->prev = newNode;  front = newNode;  }  }  void insertRear(int item) {  Node* newNode = new Node(item);  if (is_empty()) {  front = rear = newNode;  } else {  rear->next = newNode;  newNode->prev = rear;  rear = newNode;  }  }  int deleteFront() {  if (is_empty()) {  std::cout << "Deque is empty!" << std::endl;  return -1; // 或抛出异常  }  Node* temp = front;  int value = front->data;  front = front->next;  if (front) {  front->prev = nullptr;  } else {  rear = nullptr; // 如果队列变空  }  delete temp;  return value;  }  int deleteRear() {  if (is_empty()) {  std::cout << "Deque is empty!" << std::endl;  return -1; // 或抛出异常  }  Node* temp = rear;  int value = rear->data;  rear = rear->prev;  if (rear) {  rear->next = nullptr;  } else {  front = nullptr; // 如果队列变空  }  delete temp;  return value;  }  int getFront() const {  if (is_empty()) {  std::cout << "Deque is empty!" << std::endl;  return -1; // 或抛出异常  }  return front->data;  }  int getRear() const {  if (is_empty()) {  std::cout << "Deque is empty!" << std::endl;  return -1; // 或抛出异常  }  return rear->data;  }  bool is_empty() const {  return front == nullptr;  }  
};  int main() {  Deque dq;  dq.insertRear(10);  dq.insertRear(20);  dq.insertFront(5);  dq.insertFront(0);  std::cout << "Front element: " << dq.getFront() << std::endl; // 输出 0  std::cout << "Rear element: " << dq.getRear() << std::endl;   // 输出 20  dq.deleteFront(); // 删除 0  dq.deleteRear();  // 删除 20  std::cout << "Front element after deletions: " << dq.getFront() << std::endl; // 输出 5  return 0;  
}

三、循环队列

1.顺序循环队列

#include <iostream>  class CircularQueue {  
private:  int* arr;        // 存储队列元素的数组  int front;      // 队列头指针  int rear;       // 队列尾指针  int capacity;   // 队列的最大容量  int count;      // 当前队列中的元素数量  public:  CircularQueue(int size) {  arr = new int[size];  capacity = size;  front = 0;  rear = -1;  count = 0;  }  ~CircularQueue() {  delete[] arr;  }  // 入队操作  void enqueue(int item) {  if (is_full()) {  std::cout << "Queue is full!" << std::endl;  return;  }  rear = (rear + 1) % capacity; // 循环移动尾指针  arr[rear] = item;  count++;  }  // 出队操作  int dequeue() {  if (is_empty()) {  std::cout << "Queue is empty!" << std::endl;  return -1; // 或抛出异常  }  int item = arr[front];  front = (front + 1) % capacity; // 循环移动头指针  count--;  return item;  }  // 获取队头元素  int peek() const {  if (is_empty()) {  std::cout << "Queue is empty!" << std::endl;  return -1; // 或抛出异常  }  return arr[front];  }  // 检查队列是否为空  bool is_empty() const {  return count == 0;  }  // 检查队列是否已满  bool is_full() const {  return count == capacity;  }  // 获取当前队列大小  int size() const {  return count;  }  
};  int main() {  CircularQueue cq(5); // 创建一个容量为5的循环队列  cq.enqueue(10);  cq.enqueue(20);  cq.enqueue(30);  cq.enqueue(40);  cq.enqueue(50);  std::cout << "Front element: " << cq.peek() << std::endl; // 输出 10  std::cout << "Dequeued: " << cq.dequeue() << std::endl; // 输出 10  std::cout << "Front element after dequeue: " << cq.peek() << std::endl; // 输出 20  cq.enqueue(60); // 尝试入队一个新元素  std::cout << "Front element after enqueue: " << cq.peek() << std::endl; // 输出 20  return 0;  
}

2.链式循环队列

 采用循环链表的方式来实现循环队列

#include <iostream>  class Node {  
public:  int data;  Node* next;  Node(int value) : data(value), next(nullptr) {}  
};  class CircularQueue {  
private:  Node* front; // 队列头指针  Node* rear;  // 队列尾指针  int count;   // 当前队列中的元素数量  public:  CircularQueue() : front(nullptr), rear(nullptr), count(0) {}  ~CircularQueue() {  while (!is_empty()) {  dequeue();  }  }  // 入队操作  void enqueue(int item) {  Node* newNode = new Node(item);  if (is_empty()) {  front = rear = newNode;  rear->next = front; // 形成循环  } else {  rear->next = newNode;  rear = newNode;  rear->next = front; // 形成循环  }  count++;  }  // 出队操作  int dequeue() {  if (is_empty()) {  std::cout << "Queue is empty!" << std::endl;  return -1; // 或抛出异常  }  int item = front->data;  Node* temp = front;  if (front == rear) { // 只有一个元素  front = rear = nullptr;  } else {  front = front->next;  rear->next = front; // 更新尾指针  }  delete temp;  count--;  return item;  }  // 获取队头元素  int peek() const {  if (is_empty()) {  std::cout << "Queue is empty!" << std::endl;  return -1; // 或抛出异常  }  return front->data;  }  // 检查队列是否为空  bool is_empty() const {  return count == 0;  }  // 获取当前队列大小  int size() const {  return count;  }  
};  int main() {  CircularQueue cq; // 创建一个循环队列  cq.enqueue(10);  cq.enqueue(20);  cq.enqueue(30);  std::cout << "Front element: " << cq.peek() << std::endl; // 输出 10  std::cout << "Dequeued: " << cq.dequeue() << std::endl; // 输出 10  std::cout << "Front element after dequeue: " << cq.peek() << std::endl; // 输出 20  cq.enqueue(40); // 尝试入队一个新元素  std::cout << "Front element after enqueue: " << cq.peek() << std::endl; // 输出 20  return 0;  
}

四、算法专题

队列是一种重要的数据结构，广泛应用于计算机科学的各个领域。理解队列的基本概念、操作和实现方式对于学习数据结构和算法非常重要。

1.队列的应用场景

任务调度：操作系统中的进程调度。

打印队列：管理打印任务的顺序。

广度优先搜索（BFS）：图算法中的节点访问顺序。

消息队列：在分布式系统中传递消息。

2.队列的相关算法 

循环队列：通过循环数组或链表实现，避免了空间浪费。

优先队列：每个元素都有一个优先级，出队时优先级高的元素先被移除。

阻塞队列：在多线程环境中使用，支持线程安全的入队和出队操作。

3.算法题推荐

模拟队列：232. 用栈实现队列 - 力扣（LeetCode）

class MyQueue {stack<int> v;
public:MyQueue() {}void push(int x) {v.push(x);}int pop() {if(empty())return NULL;stack<int> ts;while (!v.empty()) {ts.push(v.top());v.pop();}int ans = ts.top();ts.pop();while (!ts.empty()) {v.push(ts.top());ts.pop();}return ans;}int peek() {if(empty())return NULL;stack<int> ts = v;while (ts.size() != 1) {ts.pop();}//就剩栈底了return ts.top();}bool empty() {return v.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

239. 滑动窗口最大值 - 力扣（LeetCode）双端队列：239. 滑动窗口最大值 - 力扣（LeetCode）

class Solution {
public://时间复杂度：O((n-k)*k)vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> ret;if (nums.size() == 0)return ret;deque<int> q; //存储位置for (int i = 0; i < nums.size(); i++) {while (!q.empty() && nums[i] > nums[q.back()]) {q.pop_back();}q.push_back(i);if (k == i - q.front()) q.pop_front();//超出长度if (i >= k - 1) ret.push_back(nums[q.front()]);}return ret;}
};

 优先队列(堆)：23. 合并 K 个升序链表 - 力扣（LeetCode）

class Solution {
public:struct Status {int val;ListNode *ptr;bool operator < (const Status &rhs) const {return val > rhs.val;}};priority_queue <Status> q;ListNode* mergeKLists(vector<ListNode*>& lists) {for (auto node: lists) {if (node) q.push({node->val, node});}ListNode head, *tail = &head;while (!q.empty()) {auto f = q.top(); q.pop();tail->next = f.ptr; tail = tail->next;if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});}return head.next;}
};

---

感谢大家！