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;
}