Skip to content

Queue

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

Introduction

A queue is a type of list with the property that "elements that enter the queue first will definitely leave the queue first." Due to this property, a queue is often referred to as a First-In-First-Out (FIFO) list.

Implementation

Array Simulation of a Queue

Typically, an array is used to simulate a queue, with two variables marking the head and tail of the queue.

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

The corresponding code for queue operations is as follows:

  • Insert element: q[++qr] = x;
  • Delete element: ql++;
  • Access front element: q[ql]
  • Access rear element: q[qr]
  • Clear queue: ql = 1; qr = 0;
Luogu B3616【Template】Queue Array Simulation Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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;
}

Double Stack Simulation of a Queue

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

This method uses two stacks \(F\) and \(S\) to simulate a queue, where \(F\) is the stack at the rear of the queue, and \(S\) represents the stack at the front of the queue. It supports push (insert at the rear) and pop (remove from the front) operations:

  • push: Insert into stack \(F\).
  • pop: If \(S\) is not empty, pop from \(S\); otherwise, transfer all elements from \(F\) to \(S\) (by popping from \(F\) and pushing into \(S\), which reverses their order), then pop from \(S\).

It can be easily proven that each element is only pushed/transferred/popped once, resulting in an amortized complexity of \(O(1)\).

Luogu B3616【Template】Queue Double Stack Simulation Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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;
}

Queue in C++ STL

C++ provides a container std::queue in the STL. To use it, include the <queue> header.

STL Definition of queue 
1
2
3
4
5
// clang-format off
template<
    class T,
    class Container = std::deque<T>
> class queue;

T is the data type stored in the queue.

Container is the underlying container type used to store 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 not specified, std::deque is used as the default underlying container.

The queue container in STL provides a set of member functions for use. Commonly used ones include:

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

Additionally, queue provides some operators. The most commonly used is the assignment operator = to assign one queue to another. Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
std::queue<int> q1, q2;

// Insert 1 at the rear 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 (deque) is a queue that allows insertion and deletion at both the front and the rear. It essentially combines the functionalities of a stack and a queue. Specifically, a deque supports four operations:

  • Insert an element at the front
  • Insert an element at the rear
  • Delete an element from the front
  • Delete an element from the rear

The method for simulating a deque with an array is the same as for a regular queue.

Similarly, the idea of using two stacks to simulate a queue can be adapted to maintain a deque. However, note that if one stack becomes empty, alternating queries to the front and rear may break the amortized analysis. To address this, when moving elements, only half of the elements from the non-empty stack are moved to the empty stack, while preserving the properties of the front and rear stacks. This approach still achieves amortized constant-time insertion and deletion.

Brief Proof

Since insertion operations contribute only constant complexity, consider the deletion operations. Suppose the queue initially has \(m\) elements. We calculate the time complexity to pop all elements (from either end). The first balancing operation costs \(O(m)\). Then each stack has \(\frac{m}{2}\) elements. Clearing one stack then costs \(O(\frac{m}{2})\), which can trigger another balancing operation of complexity \(O(\frac{m}{2})\), and so on, until all elements are popped. Therefore, the total complexity is

\[ T(m)=T\left(\frac{m}{2}\right)+O(m) \]

By the Master Theorem, \(T(m)=O(m)\). Thus, the total complexity of this maintenance method remains amortized constant.

Luogu B3656【Template】Double-ended Queue 1 Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

const int M = 1000000 + 5;

struct Deque {
  // Change the underlying container of stack from deque to vector to reduce space overhead
  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() {
    // Balancing requires an auxiliary stack to reverse elements within a stack
    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;
}

Double-ended Queue in C++ STL

C++ also provides a container std::deque in the STL. To use it, include the <deque> header.

STL Definition of deque 
1
2
3
4
5
// clang-format off
template<
    class T,
    class Allocator = std::allocator<T>
> class deque;

T is the data type stored in the deque.

Allocator is the allocator. This is not discussed in detail here; generally, the default is sufficient.

The deque container in STL provides a set of member functions for use. Commonly used ones include:

  • Element Access
    • q.front() returns the front element
    • q.back() returns the rear element
  • Modification
    • q.push_back() inserts an element at the rear
    • q.pop_back() removes the rear 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 (takes an iterator and an element)
    • q.erase() deletes an element at a specified position (takes an iterator)
  • Capacity
    • q.empty() checks if the deque is empty
    • q.size() returns the number of elements in the deque

Additionally, deque provides some operators. Commonly used ones include:

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

The <queue> header also provides the priority queue std::priority_queue, which is more similar to a heap and is not discussed in detail here.

Double-ended Queue in Python

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

Example:

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from collections import deque

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

# Insert element 4 at the rear
queue.append(4)

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

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

Circular Queue

Using an array to simulate a queue leads to an issue: over time, the entire queue shifts toward the end of the array. Once it reaches the end of the array, even if there is free space at the front of the array, further enqueue operations will cause overflow (this phenomenon, where overflow occurs despite available space in the array, is called "false overflow").

The solution to false overflow is to organize the array storing the queue elements in a circular manner. That is, treat position 0 of the array as the successor of the last position. (For an element at index x, its successor is (x + 1) % SIZE). This forms a circular queue.

References

  1. std::queue - zh.cppreference.com
  2. std::deque - zh.cppreference.com
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用