Explicit stack

Questions 1 to 5 of 6

1. 1. Put these steps of the explicit-stack pattern in the correct order, from start to finish.

   Use the arrows to put the steps in order.

   1. 1.Do the work for that item, and push_back each piece of work a recursive call would have made.↑↓
   2. 2.Go back to the empty() check and repeat until the stack is empty.↑↓
   3. 3.While the stack is not empty, read the top item with back() and remove it with pop_back().↑↓
   4. 4.Put the first piece of work on the stack.↑↓
2. 2. In the version that marks a cell when it is pushed, put these steps for one neighbour of the cell in the correct order.

   Use the arrows to put the steps in order.

   1. 1.Check that the neighbour is inside the grid and still '.'.↑↓
   2. 2.Write 'o' into the neighbour's cell.↑↓
   3. 3.Push the neighbour onto the stack.↑↓
   4. 4.Compute the neighbour's row and column by adding one offset to the cell's row and column.↑↓
3. 3. What does this program print? ``cpp #include <iostream> #include <vector> int main() { std::vector<int> pending; pending.push_back(1); pending.push_back(2); pending.push_back(3); pending.pop_back(); pending.push_back(4); while (!pending.empty()) { std::cout << pending.back() << ' '; pending.pop_back(); } std::cout << "\n"; } ``

   1 2 42 4 14 2 14 1 2
4. 4. The program below prints one line for each cell it fills. What is the third line it prints? ``cpp #include <iostream> #include <string> #include <vector> using Grid = std::vector<std::string>; struct Cell { int row; int col; }; bool inside(const Grid& grid, int row, int col) { return row >= 0 && row < static_cast<int>(grid.size()) && col >= 0 && col < static_cast<int>(grid[row].size()); } int main() { Grid grid = { "...", ".#.", }; std::vector<Cell> pending; pending.push_back({0, 0}); while (!pending.empty()) { Cell cell = pending.back(); pending.pop_back(); if (!inside(grid, cell.row, cell.col) || grid[cell.row][cell.col] != '.') { continue; } grid[cell.row][cell.col] = 'o'; std::cout << "fill (" << cell.row << "," << cell.col << ")\n"; pending.push_back({cell.row + 1, cell.col}); pending.push_back({cell.row - 1, cell.col}); pending.push_back({cell.row, cell.col + 1}); pending.push_back({cell.row, cell.col - 1}); } } ``

   fill (0,2)fill (0,1)fill (1,2)fill (1,0)
5. 5. The loop below should read the top cell and then remove it. What is wrong with it? ``cpp #include <iostream> #include <vector> struct Cell { int row; int col; }; int main() { std::vector<Cell> pending; pending.push_back({0, 0}); pending.push_back({1, 0}); while (!pending.empty()) { pending.pop_back(); Cell cell = pending.back(); std::cout << cell.row << "," << cell.col << "\n"; } } ``

   Nothing is wrong, because pop_back() returns the removed cell.The while condition should check size() > 1 instead of empty().The struct Cell needs a constructor, or push_back cannot accept {0, 0}.back() runs after pop_back(), so it reads the cell below the removed one, and on the second pass it reads an empty vector.