Using std::stack, std::queue, and std::priority_queue in C++

The C++ Standard Library provides stack, queue, and priority_queue to easily work with different linear data structures. These structures follow three classic models: LIFO (Last-In First-Out), FIFO (First-In First-Out), and priority-based ordering. This article explains how each structure works, their use cases, and example implementations.

1) What is stack? (LIFO Structure)

std::stack works according to the LIFO (Last-In First-Out) principle. Only the top element can be accessed, added, or removed.

• push() → adds an element to the top
• pop() → removes the top element
• top() → returns the top element
• empty() → checks if the stack is empty
• size() → number of elements

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

int main() {
    stack<int> st;

    st.push(10);
    st.push(20);
    st.push(30);

    cout << "Top: " << st.top() << endl; // 30

    st.pop(); // removes 30

    cout << "Top: " << st.top() << endl; // 20
}

Use Cases: undo operations, parenthesis matching, call stack simulation.

2) What is queue? (FIFO Structure)

std::queue follows the FIFO principle: the first inserted element is the first removed.

• push() → adds an element to the back
• front() → returns the first element
• back() → returns the last element
• pop() → removes the first element
• empty(), size()

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

int main() {
    queue<string> q;

    q.push("John");
    q.push("Emily");
    q.push("Michael");

    cout << "Front: " << q.front() << endl; // John
    cout << "Back: " << q.back() << endl;   // Michael

    q.pop(); // removes John

    cout << "Front: " << q.front() << endl; // Emily
}

Use Cases: task pipelines, job queues, messaging systems.

3) What is priority_queue?

std::priority_queue is a priority-based queue that sorts elements automatically. By default, it behaves as a max-heap: the largest element is always at the top.

• push() → insert into the queue
• top() → returns the highest-priority element
• pop() → removes the highest-priority element
• size(), empty()

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

int main() {
    priority_queue<int> pq;

    pq.push(50);
    pq.push(10);
    pq.push(80);
    pq.push(20);

    cout << "Top: " << pq.top() << endl; // 80

    pq.pop(); // removes 80

    cout << "Top: " << pq.top() << endl; // 50
}

Use Cases: Dijkstra’s algorithm, CPU scheduling, sorting tasks by priority.

4) Using priority_queue as a Min-Heap

By default, priority_queue is a max-heap. To create a min-heap, use greater<>.

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

int main() {
    priority_queue<int, vector<int>, greater<int>> minpq;

    minpq.push(40);
    minpq.push(10);
    minpq.push(30);

    cout << "Top: " << minpq.top() << endl; // 10
}

5) Practical Examples

a) Parenthesis Matching using stack

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

bool check(string s) {
    stack<char> st;

    for (char c : s) {
        if (c == '(') st.push(c);
        else if (c == ')') {
            if (st.empty()) return false;
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    cout << check("((a+b)*(c-d))"); // 1
}

b) Bank queue simulation using queue

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

int main() {
    queue<string> customers;

    customers.push("John");
    customers.push("Emily");
    customers.push("David");

    while (!customers.empty()) {
        cout << "Serving: " << customers.front() << endl;
        customers.pop();
    }
}

c) Task prioritization using priority_queue

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

int main() {
    priority_queue<pair<int,string>> tasks;

    tasks.push({3, "Low priority"});
    tasks.push({10, "High priority"});
    tasks.push({5, "Medium priority"});

    while (!tasks.empty()) {
        cout << "Task: " << tasks.top().second << endl;
        tasks.pop();
    }
}

6) When should you use each structure?

• stack: undo features, expression parsing, call stacks
• queue: scheduling, job pipelines, message queues
• priority_queue: priority-based work, algorithms, processing tasks

Choosing the correct data structure improves both performance and code clarity.

7) TL;DR

Related Articles