C++ STL

queue / priority_queue

Complete lesson for queue / priority_queue using LEARNCODEGURU’s 6-level learning model — from basics to advanced practice, with C++ OOP and STL where relevant.

Basics — queue / priority_queue

Section: C++ STL. C++ queue & priority_queue — FIFO, heaps, Stack vs Queue, and classic applications.

What is a queue?

A **queue** is **FIFO** — **First In, First Out**.
std::queue is a **container adapter** with a restricted interface.
Insert at the **back**, remove from the **front**.
std::priority_queue is related but serves the **highest priority** next (heap).
Header for both: #include
**Real-life:** ticket line / printer jobs — serve in arrival order.

Idea	Meaning
FIFO	Oldest waiting element leaves first
`push`	Enqueue at the back
`pop`	Dequeue from the front (void)
`front` / `back`	Inspect ends
Adapter	Default base is `deque`

Why use queue / priority_queue?

Queue models fair waiting lines and level-order processing (BFS).
Priority queue models triage / scheduling / best-first search.
Clear APIs prevent accidental mid-container misuse.

Benefit	What you gain
Fair order	FIFO service
Priority order	Always process best next
Simple API	push/pop/front or top
Algo fit	BFS, Dijkstra, top-K, task queues

Differences between Queue and Stack

Both adapters — opposite removal policies.

Feature	Queue	Stack
Order	FIFO	LIFO
Insert	`push` back	`push` top
Remove	`pop` front	`pop` top
Inspect	`front` / `back`	`top`
Classic algo	BFS	DFS / brackets
Real-life	Ticket line	Stack of plates
Header

Differences between queue and priority_queue

Same header family — different “who leaves next”.

Feature	`queue`	`priority_queue`
Order out	Arrival order (FIFO)	Priority / heap order
Inspect	`front()` / `back()`	`top()`
Default base	`deque`	`vector`
Default priority	N/A	Max-heap (largest first)
Min behaviour	N/A	`greater<>` comparator
Classic use	BFS, buffering	Dijkstra, top-K, scheduling

queue — basic operations

push(x) — enqueue at back.
front() / back() — peek (not on empty).
pop() — dequeue front; returns **void**.
empty() / size() — state.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    cout << q.front() << " " << q.back() << "\n"; // 1 3
    q.pop();
    cout << q.front() << "\n"; // 2
    return 0;
}

priority_queue — basic operations

Default **max-heap**: top() is the largest.
Min-heap: priority_queue, greater>.
push / pop / top / empty / size — no front/back.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    priority_queue<int> maxh;
    maxh.push(3); maxh.push(9); maxh.push(1);
    cout << maxh.top() << "\n"; // 9

    priority_queue<int, vector<int>, greater<int>> minh;
    minh.push(3); minh.push(9); minh.push(1);
    cout << minh.top() << "\n"; // 1
    return 0;
}

Queue applications

Use a queue whenever “serve in order of arrival” or “process level by level”.

Application	How the queue helps
BFS (graphs / trees)	Process nodes level-order; enqueue neighbors
Task / job scheduling	Jobs wait in line; worker takes front
Print / IO buffering	Requests handled FIFO
Message / event queues	Events drained in arrival order
Sliding window (with deque)	Maintain window ends; queue-like ends
Multi-source BFS	Seed several starts; expand fairly
Round-robin simulation	Rotate tasks via push/pop
Call-center / ticket systems	Customers served in order
Producer–consumer	Buffer between producers and consumers
Shortest path in unweighted graph	BFS distances via queue

Priority queue applications

Use when “most important / extreme value” must be processed next.

Application	How priority_queue helps
Dijkstra / best-first search	Always expand closest / best node
Top-K elements	Keep K best with a heap
CPU / job scheduling	Highest priority job runs next
Hospital triage	Critical patients first
Huffman coding	Merge two smallest repeatedly
Event simulation	Next event by time key
Median maintenance (two heaps)	Max-heap + min-heap pair
A* search	Priority by f = g + h

Application — BFS with queue

Enqueue start; while not empty, dequeue u, enqueue unseen neighbors.
Gives shortest paths in **unweighted** graphs.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>> g = {{1, 2}, {0, 3}, {0}, {1}};
    vector<bool> seen(4);
    queue<int> q;
    q.push(0);
    seen[0] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (int v : g[u]) if (!seen[v]) {
            seen[v] = true;
            q.push(v);
        }
    }
    cout << "\n";
    return 0;
}

Application — task line

Push jobs as they arrive; workers always front() then pop().

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
    queue<string> jobs;
    jobs.push("print A");
    jobs.push("print B");
    jobs.push("scan C");
    while (!jobs.empty()) {
        cout << "Doing: " << jobs.front() << "\n";
        jobs.pop();
    }
    return 0;
}

Key points to remember

queue = FIFO; stack = LIFO; priority_queue = best-first.
pop() returns void — read front/top first.
Never access front/top on an empty adapter.
BFS ↔ queue; Dijkstra / top-K ↔ priority_queue.
Both adapters are in .

Advanced — queue / priority_queue

Application — top-K with priority_queue

To keep the K largest, a **min-heap of size K** is common.
Or push all into a max-heap and pop K times for a simple version.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;
    for (int x : {5, 1, 8, 3, 7}) pq.push(x);
    for (int i = 0; i < 3 && !pq.empty(); ++i) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << "\n"; // 8 7 5
    return 0;
}

Application — Dijkstra idea

Store (distance, node) in a **min** priority_queue.
Always expand the currently closest unsettled node.
Full algorithm needs a graph + distance array — pattern uses PQ.

Underlying containers

queue: needs front, back, push_back, pop_front → deque or list.
priority_queue: needs random-access → vector (default) or deque.

Custom priority

Third template parameter is the comparator.
For pairs, default compares first then second.
Define operator< on a struct or pass a custom compare type.

Design tips

BFS / fair lines → queue; priority scheduling → priority_queue.
Guard every front/top/pop with !empty().
For sliding-window max, prefer deque of indices over plain queue.
Do not confuse priority_queue with a sorted full sequence — only top is visible.

Tricky Interview Points

Q1) What is a queue?

Answer A FIFO structure: insert at the back and remove from the front.

Q2) Queue vs stack?

Answer Queue is FIFO; stack is LIFO.

Q3) Queue vs priority_queue?

Answer queue serves in arrival order; priority_queue always serves the highest-priority element.

Q4) Default priority_queue order?

Answer Max-heap — largest element on top.

Q5) How to make a min-heap priority_queue?

Answer priority_queue<int, vector<int>, greater<int>>.

Q6) Name five queue applications.

Answer BFS, job scheduling, print spooling, message queues, unweighted shortest paths.

Q7) Name four priority_queue applications.

Answer Dijkstra, top-K, CPU scheduling, Huffman coding / event simulation.

Q8) Does pop return the element?

Answer No — void. Use front() or top() first.

Q9) Default underlying container of queue?

Answer deque.

Q10) BFS vs DFS containers?

Answer BFS uses a queue; DFS uses a stack (or recursion).

Q11) Can you iterate a std::queue?

Answer No begin/end — only front/back. Drain by popping if you must visit all.

Q12) Why is BFS shortest for unweighted graphs?

Answer FIFO explores nodes in increasing distance from the source, level by level.

Simple Programs

Basic queue drain

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(10); q.push(20); q.push(30);
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << "\n";
    return 0;
}

BFS traversal

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>> g = {{1, 2}, {3}, {3}, {}};
    vector<bool> seen(4);
    queue<int> q;
    q.push(0); seen[0] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (int v : g[u]) if (!seen[v]) {
            seen[v] = true; q.push(v);
        }
    }
    cout << "\n";
    return 0;
}

Job queue simulation

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
    queue<string> q;
    q.push("email");
    q.push("backup");
    cout << "Next: " << q.front() << "\n";
    q.pop();
    cout << "Next: " << q.front() << "\n";
    return 0;
}

priority_queue descending dump

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;
    for (int x : {4, 1, 7, 3}) pq.push(x);
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << "\n";
    return 0;
}

min-heap priority_queue

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(4); pq.push(1); pq.push(7);
    cout << pq.top() << "\n"; // 1
    return 0;
}

Top-3 with max-heap

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;
    for (int x : {2, 9, 4, 9, 1, 6}) pq.push(x);
    for (int i = 0; i < 3; ++i) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << "\n";
    return 0;
}

Problem Solving Tricks

queue = FIFO; priority_queue = best-first.
Stack vs Queue: LIFO vs FIFO.
pop() is void — front/top first.
BFS ↔ queue; DFS ↔ stack.
Default PQ is max-heap; greater<> for min-heap.
Apps: BFS, scheduling, buffering, Dijkstra, top-K.
Both adapters in .
queue base deque; PQ base vector.
Never front/top on empty.
Priority_queue is not a fully sorted list — only top is visible.
Unweighted shortest path = BFS with queue.
Document what each enqueued item means.

Practice Programs List

Simulate a ticket line with names in a queue.
Implement BFS on a small adjacency list.
Build a print-spooler that drains jobs FIFO.
Dump a priority_queue in descending order.
Create a min-heap and show successive tops.
Extract top-K scores from an array using a heap.
Write Queue vs Stack table in comments (8 rows).
Write queue vs priority_queue table (8 rows).
List 10 queue applications with one-liners.
List 8 priority_queue applications.
Explain why BFS needs a queue, not a stack.
Sketch Dijkstra using a min priority_queue in comments.