This lesson includes an expert video walkthrough — purchase once for a full year of unlimited replays to master every key point 🎬
Queue
Knowledge Summary
Definition of a Queue
A queue is a linear data structure with the first in, first out (FIFO) property.
Elements are inserted at the rear and removed from the front.
Basic Operations
| Operation | Meaning | Time Complexity |
|---|---|---|
push(x) | Enqueue | O(1) |
pop() | Dequeue | O(1) |
front() | View the front element | O(1) |
back() | View the rear element | O(1) |
empty() | Whether the queue is empty | O(1) |
C++ STL Queue
1#include <queue>
2queue<int> q;
3q.push(1);
4q.push(2);
5q.push(3);
6cout << q.front(); // 1
7q.pop();
8cout << q.front(); // 2Variants of Queues
- Deque (
deque): insertion and deletion are allowed at both ends - Priority queue (
priority_queue): elements are removed by priority; essentially implemented with a heap - Circular queue: implemented with an array; the head and tail connect to avoid false overflow
Applications of Queues
- BFS (Breadth-First Search): the core data structure
- Task scheduling: first come, first served
- Buffers: such as print queues