Queue

This page introduces data structures related to queues and their applications.

Introduction

A queue is a list with the property that an element that enters the queue first always leaves first. For this reason, a queue is also commonly called a first-in-first-out (first in first out) list, or an FIFO list for short.

Implementation

Simulating a queue with an array

A queue is commonly simulated with an array and two variables marking its front and back.

int q[SIZE], ql = 1, qr;

The corresponding queue operations are:

• Insert an element: q[++qr] = x;
• Delete an element: ql++;
• Access the front: q[ql]
• Access the back: q[qr]
• Clear the queue: ql = 1; qr = 0;

#include <cstdio>
using namespace std;

const int SIZE = 10000 + 5;

struct Queue {
  int q[SIZE], ql, qr;

  Queue() : ql(1), qr(0) {}

  bool empty() { return ql > qr; }

  void push(int x) { q[++qr] = x; }

  void pop() { ++ql; }

  int front() { return q[ql]; }

  int back() { return q[qr]; }

  int size() { return qr - ql + 1; }

  int clear() {
    ql = 1;
    qr = 0;
  }
};

int main() {
  Queue q;
  int n;
  scanf("%d", &n);
  while (n--) {
    int opt;
    scanf("%d", &opt);
    if (opt == 1) {
      int x;
      scanf("%d", &x);
      q.push(x);
    } else if (opt == 2) {
      if (q.empty())
        printf("ERR_CANNOT_POP\n");
      else
        q.pop();
    } else if (opt == 3) {
      if (q.empty())
        printf("ERR_CANNOT_QUERY\n");
      else
        printf("%d\n", q.front());
    } else
      printf("%d\n", q.size());
  }
  return 0;
}

Simulating a queue with two stacks

Another less common method is to use two stacks to simulate a queue.

Use two stacks $F$ and $S$, where $F$ is the stack at the back and $S$ is the stack at the front. The supported operations are push (insert at the back) and pop (remove from the front):

• push: push into stack $F$.
• pop: if $S$ is nonempty, pop from $S$; otherwise transfer the elements of $F$ to $S$ in reverse order (pop and push them one by one, which reverses their order), and then pop from $S$.

Each element enters, is transferred, and is popped only once, so the amortized complexity is $O(1)$.

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

struct Queue {
  stack<int> f, s;

  bool empty() { return f.empty() && s.empty(); }

  void push(int x) { f.push(x); }

  void pop() {
    if (s.empty())
      for (; !f.empty(); f.pop()) s.push(f.top());
    s.pop();
  }

  int front() {
    if (s.empty())
      for (; !f.empty(); f.pop()) s.push(f.top());
    return s.top();
  }

  int size() { return f.size() + s.size(); }
};

int main() {
  Queue q;
  int n;
  scanf("%d", &n);
  while (n--) {
    int opt;
    scanf("%d", &opt);
    if (opt == 1) {
      int x;
      scanf("%d", &x);
      q.push(x);
    } else if (opt == 2) {
      if (q.empty())
        printf("ERR_CANNOT_POP\n");
      else
        q.pop();
    } else if (opt == 3) {
      if (q.empty())
        printf("ERR_CANNOT_QUERY\n");
      else
        printf("%d\n", q.front());
    } else
      printf("%d\n", q.size());
  }
  return 0;
}

The queue in the C++ STL

The C++ STL provides a container std::queue; include the <queue> header before using it.

// clang-format off
template<
    class T,
    class Container = std::deque<T>
> class queue;

T is the type of data stored in the queue.

Container is the underlying container type used to store the elements. This container must provide the following functions with their usual semantics:

• back()
• front()
• push_back()
• pop_front()

The STL containers std::deque and std::list satisfy these requirements. If no container is specified, std::deque is used by default.

The STL queue container provides many member functions. The commonly used ones include:

• Element access
  • q.front() returns the front element
  • q.back() returns the back element
• Modification
  • q.push() inserts an element at the back
  • q.pop() removes the front element
• Capacity
  • q.empty() checks whether the queue is empty
  • q.size() returns the number of elements in the queue

The queue container also provides several operators. A commonly used one is the assignment operator =, which assigns one queue to another:

std::queue<int> q1, q2;

// Insert 1 at the back of q1
q1.push(1);

// Assign q1 to q2
q2 = q1;

// Output the front element of q2
std::cout << q2.front() << std::endl;
// Output: 1

Special queues

Double-ended queue

A double-ended queue is a queue that allows elements to be inserted or deleted at either the front or the back. It combines the functions of a stack and a queue. Specifically, a deque supports four operations:

• Insert an element at the front
• Insert an element at the back
• Delete an element at the front
• Delete an element at the back

An array-based deque can be simulated in the same way as an ordinary queue.

The two-stack queue technique can likewise be used to maintain a deque. However, if one stack is empty, alternating queries at the front and back invalidates the amortized analysis. When moving elements, move only half of the nonempty stack into the empty stack while preserving the roles of the front and back stacks. This still gives amortized constant-time insertion and deletion.

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

const int M = 1000000 + 5;

struct Deque {
  // Replace the stack's underlying deque with a vector to reduce the space constant
  stack<int, vector<int>> f, s;

  bool empty() { return f.empty() && s.empty(); }

  void push_back(int x) { f.push(x); }

  void push_front(int x) { s.push(x); }

  void balance() {
    // An auxiliary stack is needed to reverse the elements within a stack during balancing
    stack<int, vector<int>> t;
    if (s.empty()) {
      int n = f.size() / 2;
      for (; f.size() > n; f.pop()) t.push(f.top());
      for (; !t.empty(); t.pop()) s.push(t.top());
      for (; !f.empty(); f.pop()) t.push(f.top());
      f.swap(t);
      if (!f.empty()) s.swap(f);
    } else if (f.empty()) {
      int n = s.size() / 2;
      for (; s.size() > n; s.pop()) t.push(s.top());
      for (; !t.empty(); t.pop()) f.push(t.top());
      for (; !s.empty(); s.pop()) t.push(s.top());
      s.swap(t);
      if (!s.empty()) f.swap(s);
    }
  }

  void pop_front() {
    if (s.empty()) balance();
    s.pop();
  }

  void pop_back() {
    if (f.empty()) balance();
    f.pop();
  }

  int front() {
    if (s.empty()) balance();
    return s.top();
  }

  int back() {
    if (f.empty()) balance();
    return f.top();
  }

  int size() { return f.size() + s.size(); }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  vector<Deque> q(M);
  int n;
  cin >> n;
  while (n--) {
    string opt;
    int a;
    cin >> opt >> a;
    if (opt == "push_back") {
      int x;
      cin >> x;
      q[a].push_back(x);
    } else if (opt == "pop_back") {
      if (!q[a].empty()) q[a].pop_back();
    } else if (opt == "push_front") {
      int x;
      cin >> x;
      q[a].push_front(x);
    } else if (opt == "pop_front") {
      if (!q[a].empty()) q[a].pop_front();
    } else if (opt == "size")
      cout << q[a].size() << "\n";
    else if (opt == "front") {
      if (!q[a].empty()) cout << q[a].front() << "\n";
    } else {
      if (!q[a].empty()) cout << q[a].back() << "\n";
    }
  }
  return 0;
}

The double-ended queue in the C++ STL

The C++ STL also provides a container std::deque; include the <deque> header before using it.

// clang-format off
template<
    class T,
    class Allocator = std::allocator<T>
> class deque;

The STL deque container provides many member functions. The commonly used ones include:

• Element access
  • q.front() returns the front element
  • q.back() returns the back element
• Modification
  • q.push_back() inserts an element at the back
  • q.pop_back() removes the back element
  • q.push_front() inserts an element at the front
  • q.pop_front() removes the front element
  • q.insert() inserts an element before a specified position (taking an iterator and an element)
  • q.erase() deletes the element at a specified position (taking an iterator)
• Capacity
  • q.empty() tests whether the deque is empty
  • q.size() returns the number of elements in the deque

The deque container also provides several operators. Common ones include:

• Use the assignment operator = to assign one deque to another, similarly to queue.
• Use [] to access elements, similarly to vector.

The <queue> header also provides the priority queue std::priority_queue. Since it is more similar to a heap, it is not introduced further here.

Double-ended queues in Python

In Python, the deque container is provided by collections.deque.

For example:

from collections import deque

# Create a deque initialized with [1, 2, 3]
queue = deque([1, 2, 3])

# Insert 4 at the back
queue.append(4)

# Insert 0 at the front
queue.appendleft(0)

# Access the queue
# >>> queue
# deque([0, 1, 2, 3, 4])

Circular queue

Simulating a queue with an array creates a problem: over time, the entire queue moves toward the end of the array. Once it reaches the end, enqueueing can overflow even when free positions remain at the front of the array. This phenomenon, in which an array still has free positions but an overflow occurs, is called "false overflow".

To avoid false overflow, organize the array storing the queue elements circularly: treat index 0 as the successor of the last index. (The successor of the element at array index x is (x + 1) % SIZE.) This forms a circular queue.

References

1. std::queue - zh.cppreference.com
2. std::deque - zh.cppreference.com