# Understanding Queue in C++: Complete Beginner's Guide > Learn the Queue data structure in C++ from scratch. Understand the FIFO (First-In, First-Out) principle, core Queue operations (enqueue, dequeue, front, rear, empty, size), std::queue in C++ STL, real-world examples, and time complexity. - Canonical URL: https://shafinchowdhury.dev/posts//understanding-queue-in-cpp/ - Author: Shafin Chowdhury (https://shafinchowdhury.dev/about/) - Published: 2026-11-13T04:00:00.000Z - Updated: 2026-11-13T04:00:00.000Z - Reading Time: 10 min read - Tags: cpp, data-structures, queue, stl, beginners --- > **Part of the Queue Series:** This article is **Step 1** of our [Queue in C++: Complete Beginner-to-Advanced Guide](/topics/queue/). --- ## 1. What Is a Queue? A **Queue** is a fundamental linear data structure that stores a collection of elements in sequential chronological order. Unlike an [array](/posts/cpp-arrays/), which allows random access to any index (`arr[2]`), or a [Stack](/posts/understanding-stack-in-cpp/), which restricts both insertion and removal to a single top end, a Queue operates with **two distinct ends**: 1. **Rear (Back / Tail):** The entry end where new elements are inserted. 2. **Front (Head):** The exit end where existing elements are inspected and removed. ```text ENQUEUE (Insert at Rear) DEQUEUE (Remove from Front) | ^ v | +-----+-----+-----+-----+ | 40 | 30 | 20 | 10 | +-----+-----+-----+-----+ ^ ^ REAR FRONT (Newest Item) (Oldest Item) ``` ### Abstract Data Type (ADT) vs. Concrete Implementation Just like a Stack, a Queue is first and foremost an **Abstract Data Type (ADT)**—a contract of behavior: - **The Rulebook (ADT):** Any container where the earliest inserted item is always the first item removed behaves as a Queue. - **The Engine Under the Hood:** In C++, you can build a Queue using a [fixed-size array](/posts/queue-using-array-in-cpp/), a dynamic [`std::vector`](/posts/queue-using-vector-in-cpp/), a pointer-based [singly linked list](/posts/queue-using-linked-list-in-cpp/), or the C++ STL container adapter `std::queue`. --- ## 2. Understanding the FIFO Principle (First-In, First-Out) A Queue is governed by the **FIFO** principle, which stands for **First-In, First-Out**: - **First-In:** The element that arrives first is placed at the **Front** of the queue. - **First-Out:** Because elements leave exclusively from the Front, that earliest element is the very first one to be removed. > **Contrast with Stack:** While a [Stack](/posts/understanding-stack-in-cpp/) follows **LIFO (Last-In, First-Out)**—serving the newest arrival first—a Queue is completely fair: items are processed in the exact order they arrived. For a detailed comparison, check out [Queue vs Stack in C++](/posts/queue-vs-stack-in-cpp/). ```text Arrival Order: 10 arrives 1st -> 20 arrives 2nd -> 30 arrives 3rd FRONT (Exit) REAR (Entry) +------+ +------+ +------+ <--| 10 | <--| 20 | <--| 30 | <-- New elements join here +------+ +------+ +------+ Served 1st Served 2nd Served 3rd ``` If we insert `10`, then `20`, and then `30` into a Queue, `10` sits at the Front and `30` sits at the Rear. When we remove elements one by one, they exit in the exact same order: `10`, then `20`, and finally `30`. --- ## 3. How a Queue Works Internally Internally, a Queue needs three pieces of state: 1. **A storage container** (an array, vector, deque, or linked-list nodes) to hold the elements. 2. **A `front` tracker** (index or pointer) identifying the oldest element waiting to be removed. 3. **A `rear` tracker** (index or pointer) identifying the newest element most recently inserted. Let's trace how `front` and `rear` move as elements enter and leave a Queue: ```text Step 1: Empty Queue [ ] (Both Front and Rear indicate empty) Step 2: enqueue(10) +----+ | 10 | +----+ ^ FRONT & REAR (10 is both the oldest and newest element) Step 3: enqueue(20) +----+----+ | 10 | 20 | +----+----+ ^ ^ FRONT REAR Step 4: enqueue(30) +----+----+----+ | 10 | 20 | 30 | +----+----+----+ ^ ^ FRONT REAR Step 5: dequeue() -> Removes 10 from FRONT +----+----+ | 20 | 30 | +----+----+ ^ ^ FRONT REAR ``` Notice that **no middle element is ever accessed or shifted** during standard Queue operations—insertions only touch `rear`, and removals only touch `front`. --- ## 4. Fundamental Queue Operations Every Queue implementation revolves around six core operations. Note that textbook terminology (`enqueue`, `dequeue`, `rear`) and C++ STL terminology (`push`, `pop`, `back`) refer to the exact same concepts: | Conceptual Name | C++ STL (`std::queue`) | Description | | :----------------------- | :--------------------- | :------------------------------------------------------------------ | | **`enqueue(x)`** | `q.push(x)` | Inserts element `x` at the **Rear** (back) of the queue. | | **`dequeue()`** | `q.pop()` | Removes the element currently at the **Front** of the queue. | | **`front()` / `peek()`** | `q.front()` | Returns the element at the **Front** without removing it. | | **`rear()`** | `q.back()` | Returns the element at the **Rear** without removing it. | | **`empty()`** | `q.empty()` | Returns `true` if the queue contains 0 elements, otherwise `false`. | | **`size()`** | `q.size()` | Returns the total number of elements currently in the queue. | Let's examine each operation closely: ### 1. Enqueue (`push(element)`) Adds a new element to the **Rear** of the queue. In a fixed-size array queue, attempting to enqueue when the queue is full causes **Queue Overflow**. ```cpp q.push(10); // 10 joins at the rear (and is also at the front) q.push(20); // 20 joins behind 10 at the rear ``` ### 2. Dequeue (`pop()`) Removes the oldest element from the **Front** of the queue. Attempting to dequeue from an empty queue causes **Queue Underflow**. ```cpp q.pop(); // Removes 10 from the front; 20 now becomes the new front ``` ### 3. Front (`front()`) Inspects the value sitting at the **Front** of the queue without removing it. ```cpp int firstInLine = q.front(); // Reads the oldest element safely ``` ### 4. Rear (`back()`) Inspects the value sitting at the **Rear** of the queue without removing it. ```cpp int lastInLine = q.back(); // Reads the most recently added element ``` ### 5. Empty (`empty()`) Checks whether the queue has zero elements. Always verify `!q.empty()` before calling `front()`, `back()`, or `pop()`. ```cpp if (!q.empty()) { cout << "Next to be served: " << q.front() << endl; } ``` ### 6. Size (`size()`) Returns the count of active elements currently waiting in the queue. ```cpp cout << "Queue length: " << q.size() << endl; ``` --- ## 5. Introduction to `std::queue` in C++ STL For everyday development and competitive programming, C++ provides `std::queue` inside the `` header. Like `std::stack`, `std::queue` is a **container adapter**. By default, it wraps `std::deque` (a double-ended queue stored in chunked memory blocks) because `std::deque` supports $O(1)$ insertion at the back (`push_back`) and $O(1)$ removal from the front (`pop_front`). ### Basic C++ Example Using `std::queue` ```cpp #include #include using namespace std; int main() { // 1. Declare a queue of integers queue line; // 2. Enqueue elements at the rear using push() line.push(10); line.push(20); line.push(30); // 3. Inspect size, front, and rear (back) cout << "Queue size: " << line.size() << endl; cout << "Front element (oldest): " << line.front() << endl; cout << "Rear element (newest): " << line.back() << endl; cout << "---" << endl; // 4. Dequeue one element from the front using pop() line.pop(); cout << "Front element after one pop(): " << line.front() << endl; cout << "---" << endl; // 5. Process and empty the queue in FIFO order cout << "Processing remaining elements in FIFO order:" << endl; while (!line.empty()) { cout << "Serving: " << line.front() << endl; line.pop(); } if (line.empty()) { cout << "The queue is now completely empty." << endl; } return 0; } ``` ### Output ```text Queue size: 3 Front element (oldest): 10 Rear element (newest): 30 --- Front element after one pop(): 20 --- Processing remaining elements in FIFO order: Serving: 20 Serving: 30 The queue is now completely empty. ``` --- ## 6. Practical Example: Task Scheduler Simulation Let's look at a second practical example using `queue` to simulate a CPU print/task spooler that processes tasks in the exact order they were submitted: ```cpp #include #include #include using namespace std; int main() { queue taskQueue; // Tasks arrive in chronological order taskQueue.push("1. Compile main.cpp"); taskQueue.push("2. Run unit tests"); taskQueue.push("3. Build production bundle"); taskQueue.push("4. Deploy to server"); cout << "Total pending tasks: " << taskQueue.size() << endl; cout << "First task to execute: " << taskQueue.front() << endl; cout << "Last task in line: " << taskQueue.back() << endl; cout << "--- Executing Tasks ---" << endl; int step = 1; while (!taskQueue.empty()) { cout << "[Step " << step << "] Completed -> " << taskQueue.front() << endl; taskQueue.pop(); step++; } return 0; } ``` ### Output ```text Total pending tasks: 4 First task to execute: 1. Compile main.cpp Last task in line: 4. Deploy to server --- Executing Tasks --- [Step 1] Completed -> 1. Compile main.cpp [Step 2] Completed -> 2. Run unit tests [Step 3] Completed -> 3. Build production bundle [Step 4] Completed -> 4. Deploy to server ``` --- ## 7. Queue Implementation Approaches in C++ Depending on your requirements, there are four primary ways to work with a Queue in C++: | Implementation Method | Underlying Storage | Dequeue Speed | Best Used When | | :----------------------------------------------------------------------- | :-------------------------------- | :----------------------------------------------: | :----------------------------------------------------------------------------------------------------- | | **1. C++ STL (`std::queue`)** | `std::deque` (by default) | $O(1)$ | Writing production C++ code or solving competitive programming problems quickly. | | **2. [Queue Using Array](/posts/queue-using-array-in-cpp/)** | Fixed-size array (`int arr[MAX]`) | $O(1)$ | Learning `front` and `rear` index mechanics, linear queues, and Circular Queues. | | **3. [Queue Using Vector](/posts/queue-using-vector-in-cpp/)** | Dynamic array (`std::vector`) | $O(n)$ with `erase()` / $O(1)$ with offset index | Understanding why removing from the front of a contiguous vector costs $O(n)$ and how to optimize it. | | **4. [Queue Using Linked List](/posts/queue-using-linked-list-in-cpp/)** | Heap-allocated `Node` chain | $O(1)$ | Mastering pointers (`front` and `rear`), dynamic memory (`new`/`delete`), and unbounded $O(1)$ queues. | --- ## 8. Time and Space Complexity of Queue Operations In a properly implemented Queue (such as `std::queue`, a Circular Array Queue, or a Linked-List Queue), every core operation touches **only the `front` or `rear` boundary** and never loops through the elements in between: | Operation | Time Complexity | Explanation | | :--------------------------- | :-------------: | :--------------------------------------------------------------- | | **`enqueue(x)` / `push(x)`** | **$O(1)$** | Inserts one element directly at the `rear` position. | | **`dequeue()` / `pop()`** | **$O(1)$** | Removes one element directly from the `front` position. | | **`front()` / `peek()`** | **$O(1)$** | Reads the element at the `front` position in a single step. | | **`rear()` / `back()`** | **$O(1)$** | Reads the element at the `rear` position in a single step. | | **`empty()`** | **$O(1)$** | Compares the element counter or boundary pointers against empty. | | **`size()`** | **$O(1)$** | Returns the maintained count of elements. | - **Space Complexity:** **$O(n)$**, where $n$ is the number of elements stored in the queue. --- ## 9. Real-World Examples of a Queue Queues mirror how fair waiting lines work in both everyday life and computer systems: ### Everyday Physical Examples 1. **A Ticket Counter Waiting Line:** The first customer to join the line stands at the front of the window, gets their ticket first, and leaves first. New arrivals must join at the back of the line. 2. **Vehicles in a Single-Lane Drive-Thru or Toll Booth:** Cars enter the lane from the rear and exit through the booth at the front in strict arrival order. ### Computer Science & Systems Engineering Examples 1. **CPU & Operating System Task Scheduling:** When multiple processes request CPU time at the same priority level, the OS places them into a **Ready Queue** so each process gets executed in fair FIFO order. 2. **Breadth-First Search (BFS):** Graph and tree algorithms use a Queue to explore nodes level by level—visiting all distance-1 neighbors before distance-2 neighbors. (We solve classic BFS problems in [Step 5: Most Famous Queue Problems](/posts/top-5-queue-problems-in-cpp/)!) 3. **Printer Spooler Queue:** If you send five PDF documents to an office printer, they are buffered in a print queue so Document 1 finishes printing before Document 2 starts. 4. **Web Server Request Handling & Message Queues:** High-traffic web servers place incoming HTTP requests into a request queue so worker threads can process them sequentially without dropping traffic during spikes. 5. **I/O Buffer Management:** Keyboard keystrokes, network packets, and audio/video streaming buffers store incoming bytes in a FIFO ring buffer so data is read in the exact order it was transmitted. --- ## 10. Advantages and Disadvantages of a Queue ### Advantages - **Guaranteed Fairness (Chronological Order):** Every item is processed in the exact order it arrived—no starvation of older tasks. - **Constant-Time $O(1)$ Operations:** Enqueueing at the rear and dequeueing from the front both run in $O(1)$ time. - **Essential for Level-by-Level Exploration:** Enables Breadth-First Search (BFS) and shortest-path algorithms on unweighted graphs. ### Disadvantages - **No Random Access:** You cannot inspect or modify elements in the middle of a queue (`q[2]` is invalid). - **Searching Takes $O(n)$ Time:** Finding a specific value requires dequeueing elements one by one from the front. --- ## 11. Frequently Asked Questions (FAQ) ### Why does `std::queue::pop()` return `void` instead of the removed element? Just like `std::stack::pop()`, C++ separates reading the front element (`q.front()`) from removing it (`q.pop()`) for **exception safety** and zero-overhead performance. If you don't need the removed value, `q.pop()` avoids constructing a copy; if you do need it, call `q.front()` right before `q.pop()`. ### Why does `std::queue` wrap `std::deque` by default instead of `std::vector`? Because a Queue removes elements from the **front**. Removing the first element of a `std::vector` (`erase(begin())`) forces all remaining elements to shift left in $O(n)$ time. `std::deque` supports $O(1)$ removal from the front (`pop_front()`) and $O(1)$ insertion at the back (`push_back()`), making it ideal for `std::queue`. ### Can I iterate over a `std::queue` with a range-based `for` loop? No. `std::queue` intentionally hides iterators to enforce strict FIFO access at the front and rear boundaries. If you need both queue operations and random-access iteration, use `std::deque` directly. --- ## Summary - A **Queue** is a linear data structure governed by the **FIFO (First-In, First-Out)** principle. - New elements enter at the **Rear** (`enqueue` / `push`), and oldest elements leave from the **Front** (`dequeue` / `pop`). - You can inspect both ends in $O(1)$ time using `front()` and `rear()` (`back()` in STL). - All six core Queue operations run in **$O(1)$ constant time**. - For everyday C++ coding, include `` and use `std::queue`. --- ## Continue Learning in the Queue Series Now that you understand how a Queue works conceptually and with `std::queue`, let's build our own Queue from scratch using a fixed-size C++ array! - **Topic Hub:** [Queue in C++: Complete Beginner-to-Advanced Guide](/topics/queue/) - **Next Article (Step 2):** [Queue Implementation Using Array in C++](/posts/queue-using-array-in-cpp/) - **Step 3:** [Queue Implementation Using Vector in C++](/posts/queue-using-vector-in-cpp/) - **Step 4:** [Queue Implementation Using Linked List in C++](/posts/queue-using-linked-list-in-cpp/) - **Step 5:** [Most Famous Queue Problems in Competitive Programming](/posts/top-5-queue-problems-in-cpp/) - **Step 6:** [Queue vs Stack in C++: Complete Comparison](/posts/queue-vs-stack-in-cpp/)