Queue
What is a Queue?
A queue is a linear data structure that follows the FIFO (First In, First Out) principle — the first element added is the first one removed. Think of a queue at a ticket counter: the person who arrives first gets served first.
- enqueue(x) — add element to rear — O(1)
- dequeue() — remove and return front element — O(1)
- front() / peek() — view front element — O(1)
- isEmpty() — check if queue is empty — O(1)
Types of Queues
| Type | Description | Use Case |
|---|---|---|
| Simple Queue | Basic FIFO | Task scheduling, print queue |
| Circular Queue | Rear wraps to front | CPU scheduling, buffering |
| Deque (Double-ended) | Insert/delete from both ends | Sliding window problems |
| Priority Queue | Elements served by priority | Dijkstra, hospital triage |
#include <iostream>
#include <queue>
using namespace std;
int main() {
// Simple Queue
queue<int> q;
q.push(10); q.push(20); q.push(30); // enqueue
cout << "Front: " << q.front() << endl; // 10
cout << "Back: " << q.back() << endl; // 30
q.pop(); // dequeue
cout << "After dequeue, front: " << q.front() << endl; // 20
// Priority Queue (max-heap by default)
priority_queue<int> pq;
pq.push(3); pq.push(1); pq.push(4); pq.push(1); pq.push(5);
cout << "Max priority: " << pq.top() << endl; // 5
while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); }
cout << endl; // 5 4 3 1 1
// Min-heap
priority_queue<int, vector<int>, greater<int>> minPQ;
minPQ.push(3); minPQ.push(1); minPQ.push(4);
cout << "Min: " << minPQ.top() << endl; // 1
// Deque
deque<int> dq;
dq.push_front(1); dq.push_back(2); dq.push_front(0);
// 0 1 2
for (int x : dq) cout << x << " ";
cout << endl;
return 0;
}import java.util.*;
public class QueueDemo {
public static void main(String[] args) {
// Simple Queue (LinkedList implements Queue)
Queue<Integer> q = new LinkedList<>();
q.offer(10); q.offer(20); q.offer(30); // enqueue
System.out.println("Front: " + q.peek()); // 10
q.poll(); // dequeue
System.out.println("After dequeue: " + q.peek()); // 20
// Priority Queue (min-heap by default in Java)
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3); pq.offer(1); pq.offer(4); pq.offer(5);
System.out.println("Min: " + pq.peek()); // 1
while (!pq.isEmpty()) System.out.print(pq.poll() + " ");
System.out.println(); // 1 3 4 5
// Max-heap
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
maxPQ.offer(3); maxPQ.offer(1); maxPQ.offer(5);
System.out.println("Max: " + maxPQ.peek()); // 5
// Deque
Deque<Integer> dq = new ArrayDeque<>();
dq.offerFirst(1); dq.offerLast(2); dq.offerFirst(0);
System.out.println(dq); // [0, 1, 2]
}
}from collections import deque
import heapq
# Simple Queue using deque (efficient O(1) both ends)
q = deque()
q.append(10) # enqueue to right
q.append(20)
q.append(30)
print("Front:", q[0]) # 10
q.popleft() # dequeue from left
print("After dequeue:", q[0]) # 20
# Priority Queue using heapq (min-heap)
pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 4)
heapq.heappush(pq, 5)
print("Min:", pq[0]) # 1
print("Pop:", heapq.heappop(pq)) # 1
# Max-heap (negate values)
max_pq = []
for x in [3, 1, 4, 5]:
heapq.heappush(max_pq, -x)
print("Max:", -max_pq[0]) # 5
# Deque — double-ended queue
dq = deque()
dq.appendleft(1) # add to front
dq.append(2) # add to back
dq.appendleft(0)
print(list(dq)) # [0, 1, 2]
dq.popleft() # remove from front
dq.pop() # remove from back
# Application: BFS using queue
from collections import defaultdict
def bfs(graph, start):
visited = set([start])
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order// Queue using array (simple but O(n) dequeue)
class Queue {
constructor() { this.items = []; }
enqueue(x) { this.items.push(x); }
dequeue() { return this.items.shift(); } // O(n) — use linked list for O(1)
front() { return this.items[0]; }
isEmpty() { return this.items.length === 0; }
size() { return this.items.length; }
}
const q = new Queue();
q.enqueue(10); q.enqueue(20); q.enqueue(30);
console.log("Front:", q.front()); // 10
q.dequeue();
console.log("After dequeue:", q.front()); // 20
// Efficient Queue using two pointers
class EfficientQueue {
constructor() { this.items = {}; this.head = 0; this.tail = 0; }
enqueue(x) { this.items[this.tail++] = x; }
dequeue() { const val = this.items[this.head]; delete this.items[this.head++]; return val; }
front() { return this.items[this.head]; }
isEmpty() { return this.head === this.tail; }
size() { return this.tail - this.head; }
}
// Priority Queue (min-heap)
class MinHeap {
constructor() { this.heap = []; }
push(val) {
this.heap.push(val);
this._bubbleUp(this.heap.length - 1);
}
pop() {
const min = this.heap[0];
const last = this.heap.pop();
if (this.heap.length) { this.heap[0] = last; this._sinkDown(0); }
return min;
}
peek() { return this.heap[0]; }
_bubbleUp(i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.heap[parent] <= this.heap[i]) break;
[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
i = parent;
}
}
_sinkDown(i) {
const n = this.heap.length;
while (true) {
let min = i, l = 2*i+1, r = 2*i+2;
if (l < n && this.heap[l] < this.heap[min]) min = l;
if (r < n && this.heap[r] < this.heap[min]) min = r;
if (min === i) break;
[this.heap[min], this.heap[i]] = [this.heap[i], this.heap[min]];
i = min;
}
}
}
const pq = new MinHeap();
[3,1,4,1,5].forEach(x => pq.push(x));
console.log("Min:", pq.peek()); // 1