Queue — The Lunch Line

Real-world analogy

What is it?

A queue is a fundamental data structure that follows the FIFO (First In, First Out) principle. Elements are added at the back and removed from the front, just like a real-world line. Queues are essential for BFS, scheduling, and any problem where order matters. They're the fair counterpart to stacks!

Real-world relevance

Every line you've ever stood in — at the grocery store, amusement park, or cafeteria — is a queue. Your computer uses queues to manage print jobs, network packets, and process scheduling. Music playlists are queues (next song plays first). Even hospitals use priority queues to decide which patients get treated first!

Key points

• What is a Queue? — A queue is a data structure where elements are added at the BACK and removed from the FRONT. It follows the FIFO principle: First In, First Out. Just like a real line of people — the first person who joins the line is the first person to be served.
• Push — Join the Back of the Line — The 'push' operation adds an element to the BACK of the queue. Like a new person joining the end of the lunch line. In C++: myQueue.push(42); adds 42 to the back. Everyone already in line stays in their position.
• Pop — Leave from the Front — The 'pop' operation removes the element at the FRONT of the queue. Like the first person in line getting served and leaving. In C++: myQueue.pop(); removes the front element. The next person in line becomes the new front.
• Front and Back — myQueue.front() shows the element at the front (next to be served). myQueue.back() shows the element at the back (most recently joined). Like being able to see who's first in line and who's last. Always check empty() before using these!
• C++ queue from STL — C++ provides a ready-made queue: queue q; for integers, queue q; for strings. Operations: push(), pop(), front(), back(), empty(), size(). It's included in or .
• Queue vs Stack — Stack = LIFO (Last In, First Out) — like a stack of plates. Queue = FIFO (First In, First Out) — like a line of people. The key difference is WHERE you remove from: stack removes from the TOP (same end as insert), queue removes from the FRONT (opposite end from insert).
• BFS — A Preview — Breadth-First Search (BFS) is a famous algorithm that uses a queue. It explores all neighbors of a node before going deeper, level by level. Imagine you're at a maze intersection — BFS checks ALL paths one step at a time, using a queue to remember which paths to explore next. You'll see more of this in advanced CP!
• Real-World Queues — Print jobs waiting for a printer form a queue. Customers waiting for a customer service call are in a queue. Downloads waiting to start form a queue. Even your computer's CPU schedules tasks using queues! Queues are all about FAIRNESS — first come, first served.
• Processing Events in Order — In competitive programming, queues are great for processing events in the order they happen. Read all events, push them into a queue, then process them one by one from the front. This ensures everything is handled in chronological order.

Code example

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Basic queue operations
    queue<int> q;
    q.push(10);   // Queue: [10]         (front -> back)
    q.push(20);   // Queue: [10, 20]
    q.push(30);   // Queue: [10, 20, 30]
    
    cout << "Front: " << q.front() << "\n";  // 10
    cout << "Back: " << q.back() << "\n";     // 30
    cout << "Size: " << q.size() << "\n";     // 3
    
    q.pop();  // Remove 10. Queue: [20, 30]
    cout << "Front after pop: " << q.front() << "\n";  // 20
    
    // Process a line of customers
    queue<string> customers;
    customers.push("Alice");
    customers.push("Bob");
    customers.push("Charlie");
    
    cout << "\nServing customers:\n";
    while (!customers.empty()) {
        cout << "Now serving: " << customers.front() << "\n";
        customers.pop();
    }
    // Output: Alice, Bob, Charlie (in order!)
    
    // Simulation: Hot Potato game
    // N kids in a circle, pass potato K times, person holding it is out
    int n = 5, k = 3;
    queue<int> circle;
    for (int i = 1; i <= n; i++) circle.push(i);
    
    cout << "\nHot Potato (n=5, k=3):\n";
    while (circle.size() > 1) {
        for (int i = 0; i < k - 1; i++) {
            circle.push(circle.front());  // Pass to the back
            circle.pop();
        }
        cout << "Player " << circle.front() << " is out!\n";
        circle.pop();  // Remove the one holding the potato
    }
    cout << "Winner: Player " << circle.front() << "\n";
    
    return 0;
}

Line-by-line walkthrough

1. 1. #include — includes everything, including the queue library.
2. 2. queue q; — creates an empty queue that holds integers.
3. 3. q.push(10); q.push(20); q.push(30); — adds elements to the BACK of the queue. After these, 10 is at the front and 30 is at the back.
4. 4. q.front() returns 10 (the first element added) and q.back() returns 30 (the last element added). Unlike stack, queue lets you see both ends!
5. 5. q.pop(); — removes the FRONT element (10). Now 20 is at the front. This is the key difference from stack — stack pops from the top (back), queue pops from the front.
6. 6. The customer serving loop: while the queue isn't empty, print the front customer's name and pop them. Since it's FIFO, Alice (first in) gets served first!
7. 7. Hot Potato simulation: we put players 1-5 in a queue. To pass the potato, we move the front person to the back (push front, then pop). After k-1 passes, the person at front is 'out' — we pop them without re-adding.
8. 8. circle.push(circle.front()); circle.pop(); — this moves the front person to the back of the queue, simulating passing the potato around a circle. Clever use of the queue!
9. 9. The loop continues until only 1 player remains — they're the winner!

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    
    for (int i = 0; i < 3; i++) {
        cout << q.back() << " ";
        q.pop();
    }
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Queues Explained (HackerRank)
• Queue in C++ STL (GeeksforGeeks)
• Queue Problems (Codeforces)