Skip to content

Queue

In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. By convention, the end of the sequence at which elements are added is called the back, tail, or rear of the queue, and the end at which elements are removed is called the head or front of the queue, anologously to the words used when people line up to wait for goods or services.

queue

The operations of a queue make it a first-in-first-out(FIFO) data structure. Common implementations of queue are:

  • circular buffers
  • linked lists

Problems

Implementation

A common use of BFS is to find the shortest path, in other words, the minimum steps from start state to the target state. If the problem is about states transforming and we can traverse all states step by step, we can use DFS to find the answer.

The general pattern for BFS is:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
queue<Node> q{};
q.push(start_node);
while (!q.empty()) {
  auto node = q.front();
  q.pop();

  for (auto n : node.next_nodes()) {
    q.push_back(n);
  }
}

And if we want to count how many times (steps) the state transformation happens, we should use deque and add the counter:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
deque<Node> q{};
q.push_back(start_node);
int step = 0;
while (!q.empty()) {
  auto size = q.size();
  while (size--) {
    auto node = q.front();
    q.pop_front();

    for (auto n : node.next_nodes()) {
      q.push_back(n);
    }
  }
  ++step;
}

And more often, we do not want to visit a state twice(because the state is viisted and there is no need to do it again), we can choose which node can enqueue:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
deque<Node> q{};
q.push_back(start_node);
unordered_set<Node> visited{};
visited.insert(start_node);
int step = 0;
while (!q.empty()) {
  auto size = q.size();
  while (size--) {
    auto node = q.front();
    q.pop_front();

    for (auto n : node.next_nodes()) {
      if (visited.count(n)) continue;
      visited.insert(n);
      q.push_back(n);
    }
  }
  ++step;
}

Reference