Stacks and Queues

Queue Enqueue/Dequeue

Enqueue values at the back and dequeue them from the front in first-in, first-out order.

Algorithm

Basic Implementation

basic.cpp 
#include <deque>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

string render(const vector<int>& values) {
    ostringstream out;
    for (size_t i = 0; i < values.size(); ++i) {
        if (i > 0) out << " -> ";
        out << values[i];
    }
    return out.str();
}

int main() {
    deque<int> queue;
    for (int value : {10, 20, 30}) queue.push_back(value);
    vector<int> removed;
    while (!queue.empty()) {
        removed.push_back(queue.front());
        queue.pop_front();
    }
    cout << render(removed) << endl;
}

The queue keeps the oldest value at the front and adds new values at the back.

Step 1 - Enqueue 10, 20, 30

New values join at the back. The oldest value, 10, stays at the front.

Queue after three enqueues: front 10, then 20, then back 30.nextnext10front2030back

Step 2 - Dequeue removes 10

Removing from the front returns 10 and makes 20 the new front.

After one dequeue: removed is 10; front moves to 20.next10removed20front30back

Complexity

  • Time: O(1) per operation with a real queue
  • Space: O(n)

Implementation notes

  • In C++, the checked source uses std::deque<int> queue directly rather than the std::queue adapter, so the front/back operations are visible in source.
  • Enqueue is queue.push_back(value) over the initializer list {10, 20, 30}; dequeue reads queue.front() into removed.push_back(...) before queue.pop_front() mutates the deque.
  • The loop guard is while (!queue.empty()), so front() and pop_front() are only called on a non-empty deque in the checked path.
  • Dequeued values are copied into a std::vector<int> removed; the deque values themselves are integers, so there is no object ownership transfer.
  • The trace records queue [], then [10, 20, 30], then removed [10] with queue [20, 30], ending with removed [10, 20, 30] and queue [].
  • render(const std::vector<int>&) uses std::ostringstream and a size_t loop to produce 10 -> 20 -> 30, which is printed with std::cout.
  • Visible allocation is the deque storage, the removed vector, and the output string buffer; mutation happens in the deque and removed vector.
front The front is the oldest value still waiting in the queue.
FIFO A queue removes values in first-in, first-out order.