A vector permits many operations, but a workflow may need a narrower promise. An undo history uses last-in, first-out access. A work queue uses first-in, first-out access. A scheduler selects the highest-priority pending item. Standard container adaptors expose those policies directly so callers do not accidentally perform unrelated sequence mutations.
This guide uses C++17. You will compare stack, queue and priority_queue behavior, then implement a priority comparator with an explicit tie rule. The examples always check emptiness before reading or removing an item. These adaptors are ordinary in-memory containers; they do not themselves provide persistence, cross-thread coordination or distributed delivery guarantees.
A stack exposes last-in, first-out access
Std::stack provides push, top, pop, empty and size through a restricted interface. The most recently pushed value becomes the next value observed at top. Pop removes the value and returns no element, so read or move the top value first if the application needs it.
A stack can fit nested processing or a simple undo history, but “undo” requires an actual reversible-operation design. Merely saving labels does not restore application state. Decide what the stored entry owns and whether removing it should trigger cleanup. When using move-only values, transfer ownership appropriately before pop. Never hold a reference to top after removing that element, because the element's lifetime has ended.
A queue exposes first-in, first-out access
Std::queue provides access to front and back, with push adding at the back and pop removing from the front. This matches ordinary arrival-order processing. A container's FIFO ordering does not guarantee fair scheduling among concurrent producers because the adaptor itself does not coordinate them.
The default underlying storage is deque for stack and queue, but compatible alternate containers can be specified. Do not choose an underlying container that lacks the operations the adaptor needs. Also define a maximum pending count if input can grow without bound. Size is observable, but checking size and pushing are not an atomic multi-thread operation. A bounded concurrent queue needs its own synchronization or a dedicated abstraction.
A priority queue selects by a strict comparator
Std::priority_queue maintains a heap whose top is the highest-priority element under its comparator contract. With the default comparison for integers, the largest integer is on top. A greater comparator can instead put the smallest integer on top. Understand the direction rather than assuming the comparator directly means “comes first.”
The comparator must provide a strict weak ordering. Comparing an item as less than itself or creating cycles breaks the required contract. Avoid comparing with less-than-or-equal. If equal priorities need stable processing order, include a sequence number or another explicit tie key. Priority_queue does not automatically preserve FIFO order among equivalent values.
Heap order is not complete sorted iteration
Priority_queue does not expose ordinary iteration over a sorted sequence. Its guarantee concerns repeated top and pop operations. Push and pop typically perform logarithmic heap adjustment with the usual underlying vector, while top is constant-time. Building or draining a heap has a different workload from sorting once and traversing a result.
You cannot freely change the priority of an item already inside the heap through a mutable top reference. That would invalidate the ordering structure. If a scheduler needs frequent priority updates, choose a design supporting handles, remove-and-reinsert, or versioned entries with stale-entry checks. Keep that policy explicit rather than exposing the underlying vector and changing fields behind the heap's back.
Separate ordering from execution guarantees
Popping a job means it leaves this container. It does not prove the job succeeded, and a process failure can lose an in-memory item. A real worker design may need acknowledgement, retry, persistence and idempotency. These concerns should be layered around the adaptor rather than inferred from its name.
For concurrency, protect the whole check-and-pop operation or use a suitable concurrent queue. Another consumer can empty the queue between an unsynchronized empty check and front access. Tests should cover no values, one value, equal priorities, priority boundaries and repeated insert/remove cycles. Comparator tests should include self-comparison and a few ordered triples to catch obvious direction or transitivity mistakes.
Keep the restricted interface useful
An adaptor is valuable when it prevents operations the feature should not support. Do not immediately expose its underlying container to every caller. A class can wrap the adaptor with meaningful methods such as enqueue, try_take or schedule, adding size limits and validation at one boundary.
If the requirement is arbitrary search, indexed removal or sorted reporting, an adaptor alone may be the wrong primary representation. A scheduler can maintain a separate lookup structure or use another container, but then consistency between structures becomes an invariant. Prefer the simplest structure that satisfies the actual access pattern and ownership rule.
Official references
C++ Stack, Queue and Priority Queue Examples
Each example shows the code, the output it produces and what each part does.
Compare the three access policies
This complete program inserts the same integers and observes each adaptor's next value.
The same storage values produce different access order because the interfaces express different policies. No loop reads an element after pop or accesses an empty adaptor.
#include <iostream>
#include <queue>
#include <stack>
int main() {
std::stack<int> history;
std::queue<int> arrivals;
std::priority_queue<int> priorities;
for (int value : {3, 7, 4}) {
history.push(value);
arrivals.push(value);
priorities.push(value);
}
while (!history.empty()) {
std::cout << "Stack: " << history.top() << '\n';
history.pop();
}
while (!arrivals.empty()) {
std::cout << "Queue: " << arrivals.front() << '\n';
arrivals.pop();
}
while (!priorities.empty()) {
std::cout << "Priority: " << priorities.top() << '\n';
priorities.pop();
}
}Stack: 4
Stack: 7
Stack: 3
Queue: 3
Queue: 7
Queue: 4
Priority: 7
Priority: 4
Priority: 3C++ Stack, Queue and Priority Queue in Real Projects
Worked exercise: deterministic priority ties
The task is to run larger numeric priorities first. Among jobs with the same priority, the smaller ID runs first. The comparator returns true when the left job should have lower heap priority than the right. This complete example uses unique job IDs as its deterministic tie key.
#include <iostream>
#include <queue>
#include <vector>
struct Job {
int priority;
int id;
};
struct LowerPriority {
bool operator()(const Job& left, const Job& right) const {
if (left.priority != right.priority)
return left.priority < right.priority;
return left.id > right.id;
}
};
int main() {
std::priority_queue<Job, std::vector<Job>, LowerPriority> jobs;
jobs.push({20, 2});
jobs.push({10, 3});
jobs.push({20, 1});
while (!jobs.empty()) {
Job next = jobs.top();
jobs.pop();
std::cout << "Job " << next.id
<< " priority " << next.priority << '\n';
}
}Job 1 priority 20
Job 2 priority 20
Job 3 priority 10The value is copied before pop so the output does not use a destroyed element. If arrival order is the required tie rule, store a monotonic sequence value and compare that instead of the job ID.
C++ Stack, Queue and Priority Queue FAQ
Does pop return the removed value?
No. Standard stack, queue and priority_queue pop operations remove an element without returning it. Read or move the exposed value before pop when the application needs it. Do not retain a reference to that element afterward. For move-only ownership, review the adaptor's access type and choose a suitable representation rather than assuming every top operation yields a freely movable value.
Is a priority queue stable for equal priorities?
Not automatically. Equivalent priorities do not guarantee arrival-order processing. Add an explicit sequence or tie identifier when the feature requires deterministic behavior. The comparator must remain a strict weak ordering. A tie rule using less-than-or-equal is invalid because it can consider an item lower than itself and violate the ordering contract.
Can I change a queued job's priority in place?
Not through ordinary priority_queue access without reestablishing the heap's invariants. Top access is constrained, and arbitrary element access is not part of the adaptor. Design updates through remove-and-reinsert, handles supported by another structure, or versioned entries with deliberate stale-entry handling. Changing hidden stored state can make the next selected job incorrect.
Does queue provide safe concurrent processing?
The standard adaptor does not supply thread synchronization. Protect the complete empty-check, access and removal transition, or use a dedicated concurrent abstraction. FIFO order in a single container is separate from durable delivery and exactly-once execution. A process crash, cancellation or failed handler still needs an application-level recovery and ownership policy.
C++ Stack, Queue and Priority Queue Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
Two consumers share a queue. Which design prevents an empty-check race?
C++ Stack, Queue and Priority Queue Quiz
2 questions to check what you learned.
Which value is next after pushing 3, 7 and 4 into a stack?
- 3, because it arrived first.
- 7, because it is largest.
- No value until the stack is sorted.
- 4, because it was pushed last.
What must a priority comparator satisfy?
- A strict weak ordering compatible with the intended priority policy.
- It must return true for equal values.
- It must compare only memory addresses.
- It must preserve FIFO automatically without a tie key.