一、认识队列
队列是一种常见的数据结构，按照先进先出（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;}
};
感谢大家！