1. Queue Stack (Queue and BFS)
02 Nov 2019 | Data structure_1
1. Introduction
- We may access a random element by index in Array. However, we might want to restrict the processing order in some cases.
- we introduce two different processing orders, First-in-First-out and Last-in-First-out and its two corresponding linear data structures, Queue and Stack.
- We go through the definition, implementation and built-in functions for each data structure.
- Then, we focus more on the practical applications of these two data structures.
- By completing this card, you should be able to:
- Understand the principle of the processing orders of FIFO and LIFO
- Implement these two data structures
- Be familiar with the built-in queue and stack structure
- Solve basic queue-related problems, especially BFS(Breadth-Frist Search)
- Solve basic stack-related problems problems
- Understand how system stack helps you when you solve problems using DFS(Depth-First Search) and other recursion algorithms
2. Queue and BFS
- One common application of Breadth-first Search (BFS) is to find the shortest path from the root node to the target node.
- In this article, we provide an example to explain how queue is applied in a BFS algorithm step by step.
Example
Here we provide an example to show how BFS is used to find the shortest path between the root node A and the target node G.
3. Insights
- After watching the animation above, let’s answer the following questions:
- What is the processing order of the nodes?
- In the first round, we process the root node. In the second round, we process the nodes next to the root node; in the third round, we process the nodes which are two steps from the root node; so on and so forth.
- Similar to tree’s level-order traversal, the nodes closer to the root node will be traversed earlier.
- If a node X is added to the queue in the kth round, the length of the shortest path between the root node and X is exactly k.
- That is to say, you are already in the shortest path the first time you find the target node.
- What is the enqueue and dequeue order of the queue?
- As shown in the animation above, we first enqueue the root node.
- Then in each round, we process the nodes which are already in the queue one by one and add all their neighbors to the queue.
- It is worth noting that the newly-added nodes will not be traversed immediately but will be processed in the next round.
- The processing order of the nodes is the exact same order as how they were added to the queue, which is First-in-First-out (FIFO). That’s why we use a queue in BFS.
4. BFS - Template
- Previously, we have already introduced two main scenarios of using BFS:
- traversal or find the shortest path.
- Typically, it happens in a tree or a graph. As we mentioned in the chapter description, BFS can also be used in more abstract scenarios.
- In this article, we will provide you with a template. Then, we provide some exercise after this article for practice.
- It will be important to determine the nodes and the edges before doing BFS in a specific question
- Typically, the node will be an actual node or a status while the edge will be an actual edge or a possible transition.
Example(walls and gates)
- You are given a m x n 2D grid initialized with these three possible values.
- -1 - A wall or an obstacle.
- 0 - A gate.
- INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
- Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
map
- Given the 2D grid
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
- After running your function, the 2D grid should be:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
- Understand the problem:
- It is very classic backtracking problem. We can start from each gate (0 point), and searching for its neighbors. We can either use DFS or BFS solution.
class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
if (rooms.empty()) return;
int m = rooms.size(), n = rooms[0].size();
queue<pair<int, int>> q;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!rooms[i][j]) q.push({i, j});
}
}
for (int d = 1; !q.empty(); d++) {
for (int k = q.size(); k; k--) {
int i = q.front().first, j = q.front().second;
q.pop();
add(rooms, q, i - 1, j, m, n, d);
add(rooms, q, i + 1, j, m, n, d);
add(rooms, q, i, j - 1, m, n, d);
add(rooms, q, i, j + 1, m, n, d);
}
}
}
private:
void add(vector<vector<int>> &rooms, queue<pair<int, int>> &q, int i, int j, int m, int n, int d) {
if (i >= 0 && i < m && j >= 0 && j < n && rooms[i][j] > d) {
q.push({i, j});
rooms[i][j] = d;
}
}
};
vector<vector>
- vector of vectors of int as follows:
vector<vector<int>> v;
- above definition results in an empty two-dimensional vector.
- in order to use it, we have to define vector size and allocate storage for its elements.
- there are several methods to grow a two-dimensional vector with help of resize() or push_back() functions or using the fill constructor or initializer lists.
- resize() function
- the resize() function is used to resize a vector to the specified size. we can use it to initialize a vector of vectors as shown below
#include <iostream>
#include <vector>
using namespace std;
#define R 4
#define C 5
int main()
{
// instantiate a vector of R objects of type vector<int>
// and resize each object to size C
vector<vector<int>> mat(R);
for (int i = 0 ; i < R ; i++)
mat[i].resize(C);
// print the vector
return 0;
}
- we can picture a vector of vectors as a two-dimensional array consisting of R rows and C columns. here’s alternative version of above code which uses overloaded version of the resize() function which accepts the container size, and the object to be copied in that container
#include <iostream>
#include <vector>
using namespace std;
#define R 4
#define C 5
int main()
{
// instantiate vector object of type vector<int>
vector<vector<int>> mat;
// resize the vector to R elements of type vector<int>, each having size C
mat.resize(R, std::vector<int>(C));
// print the vector
return 0;
}
- push_back() function
- another plausible way of initializing a vector of vectors is to use the push_back() function which adds a given element at the end of the vector.
#include <iostream>
#include <vector>
using namespace std;
#define R 4
#define C 5
int main()
{
// instantiate vector object of type vector<int> and
// use push_back() function to resize it
vector<vector<int>> mat;
for (int i = 0; i < R; i++)
{
// construct a vector of int
vector<int> v;
for (int j = 0; j < C; j++)
v.push_back(0);
// push back above one-dimensional vector
mat.push_back(v);
}
// print the vector
return 0;
}
result
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
- note when dimensions R and C are Large, above code suffers from potential performance penalties caused by frequent re-allocation of memory by push_back() function.
- this should be used only when vector dimensions are not known in advance
- Fill Constructor
- the recommended approach is to use fill constructor of the vector container for constructing a vector of vectors. the fill constructor accepts an initial size n and a value and creates a vector of n elements and fills with the specified default value
#include <iostream>
#include <vector>
using namespace std;
#define R 4
#define C 5
int main()
{
// Using the fill constructor to construct a vector of vectors
vector<vector<int>> mat(R, vector<int>(C));
// print the vector
return 0;
}
- we can split above initialization into two parts
- first initialize a vector of ints and then use this vector to initialize the vector of vectors using the fill constructor.
#include <iostream>
#include <vector>
using namespace std;
#define R 4
#define C 5
int main()
{
// first initialize a vector of int
vector<int> v(C);
// Use above vector to initialize the vector of vectors
// using the fill constructor
vector<vector<int>> mat(R, v);
// print the vector
return 0;
}
result
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
- Initializer list
- Finally, we can use initializer list introduced with c++11 to construct a vector of vectors as shown
#include <iostream>
#include <vector>
using namespace std;
int main()
{
// using an initializer list to construct a vector of vectors
vector<vector<int>> mat {
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 }
};
// print the vector
return 0;
}
1. Introduction
- We may access a random element by index in Array. However, we might want to restrict the processing order in some cases.
- we introduce two different processing orders, First-in-First-out and Last-in-First-out and its two corresponding linear data structures, Queue and Stack.
- We go through the definition, implementation and built-in functions for each data structure.
- Then, we focus more on the practical applications of these two data structures.
- By completing this card, you should be able to:
- Understand the principle of the processing orders of FIFO and LIFO
- Implement these two data structures
- Be familiar with the built-in queue and stack structure
- Solve basic queue-related problems, especially BFS(Breadth-Frist Search)
- Solve basic stack-related problems problems
- Understand how system stack helps you when you solve problems using DFS(Depth-First Search) and other recursion algorithms
2. Queue and BFS
- One common application of Breadth-first Search (BFS) is to find the shortest path from the root node to the target node.
- In this article, we provide an example to explain how queue is applied in a BFS algorithm step by step.
Example Here we provide an example to show how BFS is used to find the shortest path between the root node A and the target node G.
3. Insights
- After watching the animation above, let’s answer the following questions:
- What is the processing order of the nodes?
- In the first round, we process the root node. In the second round, we process the nodes next to the root node; in the third round, we process the nodes which are two steps from the root node; so on and so forth.
- Similar to tree’s level-order traversal, the nodes closer to the root node will be traversed earlier.
- If a node X is added to the queue in the kth round, the length of the shortest path between the root node and X is exactly k.
- That is to say, you are already in the shortest path the first time you find the target node.
- What is the enqueue and dequeue order of the queue?
- As shown in the animation above, we first enqueue the root node.
- Then in each round, we process the nodes which are already in the queue one by one and add all their neighbors to the queue.
- It is worth noting that the newly-added nodes will not be traversed immediately but will be processed in the next round.
- The processing order of the nodes is the exact same order as how they were added to the queue, which is First-in-First-out (FIFO). That’s why we use a queue in BFS.
- What is the processing order of the nodes?
4. BFS - Template
- Previously, we have already introduced two main scenarios of using BFS:
- traversal or find the shortest path.
- Typically, it happens in a tree or a graph. As we mentioned in the chapter description, BFS can also be used in more abstract scenarios.
- In this article, we will provide you with a template. Then, we provide some exercise after this article for practice.
- It will be important to determine the nodes and the edges before doing BFS in a specific question
- Typically, the node will be an actual node or a status while the edge will be an actual edge or a possible transition.
Example(walls and gates)
- You are given a m x n 2D grid initialized with these three possible values.
- -1 - A wall or an obstacle.
- 0 - A gate.
- INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
- Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
map
- Given the 2D grid
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
- After running your function, the 2D grid should be:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
- Understand the problem:
- It is very classic backtracking problem. We can start from each gate (0 point), and searching for its neighbors. We can either use DFS or BFS solution.
class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
if (rooms.empty()) return;
int m = rooms.size(), n = rooms[0].size();
queue<pair<int, int>> q;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!rooms[i][j]) q.push({i, j});
}
}
for (int d = 1; !q.empty(); d++) {
for (int k = q.size(); k; k--) {
int i = q.front().first, j = q.front().second;
q.pop();
add(rooms, q, i - 1, j, m, n, d);
add(rooms, q, i + 1, j, m, n, d);
add(rooms, q, i, j - 1, m, n, d);
add(rooms, q, i, j + 1, m, n, d);
}
}
}
private:
void add(vector<vector<int>> &rooms, queue<pair<int, int>> &q, int i, int j, int m, int n, int d) {
if (i >= 0 && i < m && j >= 0 && j < n && rooms[i][j] > d) {
q.push({i, j});
rooms[i][j] = d;
}
}
};
vector<vector>
- vector of vectors of int as follows:
vector<vector<int>> v;
- above definition results in an empty two-dimensional vector.
- in order to use it, we have to define vector size and allocate storage for its elements.
- there are several methods to grow a two-dimensional vector with help of resize() or push_back() functions or using the fill constructor or initializer lists.
- resize() function
- the resize() function is used to resize a vector to the specified size. we can use it to initialize a vector of vectors as shown below
#include <iostream>
#include <vector>
using namespace std;
#define R 4
#define C 5
int main()
{
// instantiate a vector of R objects of type vector<int>
// and resize each object to size C
vector<vector<int>> mat(R);
for (int i = 0 ; i < R ; i++)
mat[i].resize(C);
// print the vector
return 0;
}
- we can picture a vector of vectors as a two-dimensional array consisting of R rows and C columns. here’s alternative version of above code which uses overloaded version of the resize() function which accepts the container size, and the object to be copied in that container
#include <iostream>
#include <vector>
using namespace std;
#define R 4
#define C 5
int main()
{
// instantiate vector object of type vector<int>
vector<vector<int>> mat;
// resize the vector to R elements of type vector<int>, each having size C
mat.resize(R, std::vector<int>(C));
// print the vector
return 0;
}
- push_back() function
- another plausible way of initializing a vector of vectors is to use the push_back() function which adds a given element at the end of the vector.
#include <iostream>
#include <vector>
using namespace std;
#define R 4
#define C 5
int main()
{
// instantiate vector object of type vector<int> and
// use push_back() function to resize it
vector<vector<int>> mat;
for (int i = 0; i < R; i++)
{
// construct a vector of int
vector<int> v;
for (int j = 0; j < C; j++)
v.push_back(0);
// push back above one-dimensional vector
mat.push_back(v);
}
// print the vector
return 0;
}
result
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
- note when dimensions R and C are Large, above code suffers from potential performance penalties caused by frequent re-allocation of memory by push_back() function.
- this should be used only when vector dimensions are not known in advance
- Fill Constructor
- the recommended approach is to use fill constructor of the vector container for constructing a vector of vectors. the fill constructor accepts an initial size n and a value and creates a vector of n elements and fills with the specified default value
#include <iostream>
#include <vector>
using namespace std;
#define R 4
#define C 5
int main()
{
// Using the fill constructor to construct a vector of vectors
vector<vector<int>> mat(R, vector<int>(C));
// print the vector
return 0;
}
- we can split above initialization into two parts
- first initialize a vector of ints and then use this vector to initialize the vector of vectors using the fill constructor.
#include <iostream>
#include <vector>
using namespace std;
#define R 4
#define C 5
int main()
{
// first initialize a vector of int
vector<int> v(C);
// Use above vector to initialize the vector of vectors
// using the fill constructor
vector<vector<int>> mat(R, v);
// print the vector
return 0;
}
result
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
- Initializer list
- Finally, we can use initializer list introduced with c++11 to construct a vector of vectors as shown
#include <iostream>
#include <vector>
using namespace std;
int main()
{
// using an initializer list to construct a vector of vectors
vector<vector<int>> mat {
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 }
};
// print the vector
return 0;
}
Comments