# Stack

Stacks and queues can be considered restricted versions of arrays and linked lists.

## application

### parenthesis matching

Problem Description: match the left and right parentheses of a string.

Problem solving idea: enter the stack when you encounter the left parenthesis. In case of right parenthesis, it will be out of the stack. If there is no element, it is obviously mismatched. After traversing the string, if there are elements in the stack, they are also mismatched.

#include <stack> #include <string> #include <vector> #include <iostream> using namespace std; void printMatchedPairs(string expr); int main() { string expr = "(a*(b+c)+d)"; printMatchedPairs(expr); expr = "(a*(b+c)+d"; printMatchedPairs(expr); } void printMatchedPairs(string expr) { stack<char, vector<char>> seq; for (auto& s : expr) { if (s == '(') seq.push(s); if (s == ')') { if (seq.empty()) { cout << "not matching" << endl; return; } else seq.pop(); } } if (seq.empty()) cout << "matching" << endl; else cout << "not matching" << endl; return; }

### Hanoi

Problem Description: suppose there are n dishes and 3 towers. Initially, all the dishes are stacked on Tower 1 from large to small. We need to move all the dishes to tower 2, one at a time, and we can't press the large dishes on the small dishes at any time.

Solution idea: three towers, which are divided into starting tower, target tower and transfer tower. Every time: put n-1 bricks on the target tower into the transfer tower, put the last brick into the target tower, and finally put the brick on the transfer tower into the target tower. Then the problem becomes how to put the N-1 bricks on the target tower into the transfer tower. The essence is the same idea as before, so a recursive method is obvious.

#include <vector> #include <stack> #include <iostream> using namespace std; vector<stack<int, vector<int>>> tower; void move(int, int, int, int); int main() { tower.assign(3, {}); for (int i = 64; i >= 1; i--) tower[0].push(i); move(tower[0].size(), 0, 1, 2); cout << tower[1].size() << endl; return 0; } void move(int n, int x, int y, int z) { if (n > 0) { move(n - 1, x, z, y); tower[y].push(tower[x].top()); tower[x].pop(); move(n - 1, z, y, x); } }

The inspiration given to us in this problem is that the recursive method is suitable for solving the problem of the same process in a loop.

In solving this problem, the moving mode of Hanoi tower is a typical first in and last out, which is suitable for using the data structure of stack to represent the tower.

### Train carriage rearrangement

Problem Description:

A freight train has n carriages, each of which has to stop at a different station. Suppose n stations are numbered from 1 to N, and the freight train passes through the station in the order from n to 1. The number of the carriages is the same as the number of the station they will stop at. In order to facilitate the unloading of corresponding carriages from the train, the carriages must be rearranged from front to back and from 1 to n.

The rearrangement of carriages is carried out at a transfer station, in which there are three buffer tracks H1, H2 and H3. At the beginning, the train with n carriages starts to enter the track, and the last order on the exit track is from right to left, that is, from 1 to n.

Problem analysis:

One car after another enters the sorting process. If it is the car I want to row out, then I don't need to enter the buffer track. If it is not, then enter the buffer track, and find the track that is larger than it and the nearest one.

#include <vector> #include <stack> using namespace std; // global variable vector<stack<int,vector<int>>> track; int numberOfCars; // Number of cars int numberOfTracks; // Number of tracks int smallestCar; // The car with the smallest number in the buffer track int itsTrack; // Buffer track with the smallest number of cars parked void outputFromHoldingTrack() { // Move the smallest number out of the track // Delete the car with the lowest number from the stack itsTrack track[itsTrack].pop(); // After deletion, the smallest carriage and its track should be found at the top of all stacks smallestCar = numberOfCars + 2; for(int i=1;i<=numberOfTracks;i++) if (!track[i].empty() && (track[i].top() < smallestCar)) { smallestCar = track[i].top(); itsTrack = i; } } bool putInHoldingTrack(int c) { // Move carriage c to a buffer track. Returns false if and only if no buffer track is available // Find a suitable buffer track for car c // initialization int bestTrack = 0; int bestTop = numberOfCars + 1; // Scan buffer track for (int i = 1; i <= numberOfTracks; i++) if (!track[i].empty()) { int topCar = track[i].top(); // Follow the principle: find the orbit with the nearest number in the, but larger than it if (c < topCar && topCar < bestTop) { bestTop = topCar; bestTrack = i; } } else // If the buffer track is empty and there is no better choice if (bestTrack == 0) bestTrack = i; if (bestTrack == 0) return false; track[bestTrack].push(c); if (c < smallestCar) { smallestCar = c; itsTrack = bestTrack; } return true; } bool railroad(int inputOrder[], int theNumberOfCars, int theNumberOfTrackers) { // Rearrange the cars from the initial sequence // If the rearrangement is successful, return true; otherwise, return false numberOfCars = theNumberOfCars; numberOfTracks = theNumberOfTrackers; // Create a stack for buffering tracks. Here is the number of tracks + 1. The purpose is to consider the non existence. If it does not exist, my bestTrack is 0 track.assign(numberOfTracks + 1, {}); int nextCarToOutput = 1; // The car number you want to move out smallestCar = numberOfCars + 1; // No car in buffer track // Rearrange the carriage for (int i = 1; i <= numberOfCars; i++) if (inputOrder[i] == nextCarToOutput) { // If the carriage to be arranged happens to be the one I want to move out, move it out directly // Move the carriage inputOrder[i] directly out of the track nextCarToOutput++; // After moving out, see if there is anything in the current orbit that can also be moved out while (smallestCar == nextCarToOutput) { outputFromHoldingTrack(); nextCarToOutput++; } } else if (!putInHoldingTrack(inputOrder[i])) return false; return true;

Based on the data structure of the stack, the problem completes the sorting by grasping the conditions of leaving the candidate track and entering the candidate track.

### Off line equivalence problem

Problem Description: input elements and relationships, and divide these n elements into equivalence classes.

Solution strategy:

- In the first stage, input data and establish n tables to represent relationship pairs;
- The second stage is to find equivalence classes, which is a depth first strategy.

The essence of offline equivalence class is that each equivalence class forms a tree and traverses it through depth first.

The problem of online equivalence class is to know the elements and whether they are equivalent, and divide these n elements into equivalence classes.

Online equivalence classes build this tree step by step through relationships.

The purpose is to divide equivalence classes, but they have different applications for equivalence relations.

### Wiring problem

Problem introduction and ideas

The key is to grasp the conditions of exit and entry. Each line divides the box into areas, so when the line wants to go out of the stack, all the lines in the area should go out. It is a bit similar to the bracket matching problem.

Pairing problems usually consider stacks.

### Maze mouse

Find a path from the entrance to the exit.

First, take the maze entrance as the current position. If the current position is the maze exit, then a path has been found and the search work is over. If the current position is not the labyrinth exit, place an obstacle on the current position to prevent the search process from winding back to this position.

Then check whether the adjacent location is free. If so, move to a free adjacent location, and then start from this location to find the path to the exit.

In order to facilitate movement, the current position is saved in a stack before entering a new adjacent position.

If all idle adjacent locations have been explored, but the path cannot be found, it indicates that this path does not exist in the maze.

#include <iostream> #include <stack> #include <vector> #include <utility> using namespace std; using container = stack<pair<int, int>, vector<pair<int, int>>>; using node = pair<int, int>; vector<vector<int>> maze = { {1,1,1,1,1,1,1,1,1,1,1,1}, {1,0,1,1,1,1,1,0,0,0,0,1}, {1,0,0,0,0,0,1,0,1,0,0,1}, {1,0,0,0,1,0,1,0,0,0,0,1}, {1,0,1,0,1,0,1,0,1,1,0,1}, {1,0,1,0,1,0,1,0,1,0,0,1}, {1,0,1,1,1,0,1,0,1,0,1,1}, {1,0,1,0,0,0,1,0,1,0,1,1}, {1,0,1,0,1,1,1,0,1,0,0,1}, {1,1,0,0,0,0,0,0,1,0,0,1}, {1,0,0,0,0,1,1,1,1,0,0,1}, {1,1,1,1,1,1,1,1,1,1,1,1} }; container find_path() { container path; // Set start and end points node start = { 1,1 }; node exit = { 10,10 }; // Initialization offset pair<int, int> offset[4]; offset[0].first = 0; offset[0].second = 1; // right offset[1].first = 1; offset[1].second = 0; // down offset[2].first = 0; offset[2].second = -1; // left offset[3].first = -1; offset[3].second = 0; // up node current_location = start; maze[start.first][start.second] = 1; int option = 0; int lastOption = 3; while (current_location != exit) { int r, c; // Find an accessible way while (option <= lastOption) { r = current_location.first + offset[option].first; c = current_location.second + offset[option].second; if (maze[r][c] == 0) break; option++; } // Found, update if (option <= lastOption) { path.push(current_location); current_location.first = r; current_location.second = c; maze[r][c] = 1; option = 0; } // Not found, backtrack or return incomplete path else { if (path.empty()) return path; node next = path.top(); path.pop(); if (next.first == current_location.first) { option = 2 + next.second - current_location.second; } else option = 3 + next.first - current_location.first; current_location = next; } } return path; } int main() { container path = find_path(); while (!path.empty()) { cout << path.top().first << path.top().second << endl; path.pop(); } }

From this code, you can learn the following methods: 01 map representation and using preset offset to represent movement.

To sum up, stack is usually used for pairing problems (bracket matching, routing problems) or for the movement of things in practical applications (Hanoi Tower, train rearrangement, offline equivalence problems) or search problems, especially depth first (maze mouse).

# queue

## application

### Train carriage rearrangement

#include <iostream> #include <queue> #include <list> #include <vector> #include <deque> #include <utility> using namespace std; using tracks = vector<queue<int,deque<int>>>; tracks trs = { {},{},{} }; int next_train = 1; pair<int, int> min_train = { 0,11 }; list<int> clear_the_rest(list<int> target); list<int> get_trains(list<int> trains); int main() { list<int> trains = { 5,8,1,7,4,2,9,6,3 }; list<int> target = get_trains(trains); for (auto& t : target) cout << t << endl; return 0; } list<int> get_trains(list<int> trains) { list<int> target = {}; int len = trains.size(); for (int i = 0; i < len; i++) { // Eject a carriage int train = trains.back(); trains.pop_back(); // Determine whether you can drive out of the track directly if (train == next_train) { target.push_front(next_train); next_train++; // After driving out, see if there is any carriage that can be continued in the current track target = clear_the_rest(target); } // If not, arrange the car into the track else { // The candidate entering the track and its end car number. Because the empty car number is regarded as 0, it needs to be set to - 1 here pair<int, int> wait_tr = { 0,-1 }; for (int i = 0; i < 3; i++) { int max; if (trs[i].empty()) max = 0; else max = trs[i].back(); // Find the largest car number next to the one entering the car if (train > max && max > wait_tr.second) { wait_tr.first = i; wait_tr.second = max; } } // Update the minimum car number and its position in real time trs[wait_tr.first].push(train); if (min_train.second > train) { min_train.first = wait_tr.first; min_train.second = train; } } } return target; } list<int> clear_the_rest(list<int> target) { while (min_train.second == next_train) { target.push_front(next_train); next_train++; trs[min_train.first].pop(); min_train = { 0,11 }; for (int i = 0; i < 3; i++) { if (trs[i].empty()) continue; if (trs[i].front() < min_train.second) { min_train.first = i; min_train.second = trs[i].front(); } } } return target; }

### Circuit routing (Lee algorithm)

Lee algorithm is a classical algorithm to find the shortest path from the grid.

For example, we need to find the shortest path between a and b. The shortest path between a and b needs to be determined in two processes. One is the process of distance marking, the other is the process of path marking.

In the process of distance marking, starting from position a, mark the adjacent squares reachable from a as 1, then mark the squares reachable from 1 as 2, and so on. Until b is reached or there is no reachable adjacent square.

Once b is reached, the number of b is the distance between b and a. After that, the path marking process starts, starting from square b, and first moves to an adjacent position 1 smaller than b. Repeat this process until you reach a.

#include <queue> #include <utility> using namespace std; using node = pair<int, int>; bool findPath() { node entrance = { 1,1 }; node exit = { 10,10 }; const int size = 10; int grid[size + 2][size + 2]; if (entrance == exit) { const int pathLength = 0; return true; } // Initialization offset pair<int, int> offset[4]; offset[0].first = 0; offset[0].second = 1; // right offset[1].first = 1; offset[1].second = 0; // down offset[2].first = 0; offset[2].second = -1; // left offset[3].first = -1; offset[3].second = 0; // up // Initialize obstacles around the mesh for (int i = 0; i <= size + 1; i++) { grid[0][i] = grid[size + 1][i] = 1; grid[i][0] = grid[i][size + 1] = 1; } node here = entrance; // 0 means no obstacle and unmarked, and 1 means obstacle; Therefore, the starting point is set to 2, and the real distance can be obtained as long as the distance is - 2. grid[entrance.first][entrance.second] = 2; int numOfNbrs = 4; // The number of adjacent positions of a square; node nbr; queue<node, deque<node>> q; // Distance marker do { for (int i = 0; i < numOfNbrs; i++) { nbr.first = here.first + offset[i].first; nbr.second = here.second + offset[i].second; if (grid[nbr.first][nbr.second] == 0) { grid[nbr.first][nbr.second] = grid[here.first][here.second] + 1; if (nbr == exit) break; q.push(nbr); } } if (nbr == exit) break; if (q.empty()) return false; here = q.front(); q.pop(); } while (true); // Path construction const int pathLength = grid[exit.first][exit.second] - 2; node *path = new node[pathLength]; here = exit; for (int j = pathLength - 1; j >= 0; j--) { path[j] = here; for (int i = 0; i < numOfNbrs; i++) { nbr.first = here.first + offset[i].first; nbr.second = here.second + offset[i].second; if (grid[nbr.first][nbr.second] == j + 2) break; } here = nbr; } return true; }