文章目录
栈
栈和队列可以视为数组和链表的限制版本。
应用
括号匹配
问题描述：对一个字符串的左右括号进行匹配。
解题思路：遇到左括号，入栈。遇到右括号，出栈，若没元素，显然是不匹配的。字符串遍历后，如果栈里面还有元素，那么也是不匹配的。
#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;
}
汉诺塔
问题描述：假设有n个碟子和3座塔。初始时所有碟子从大到小堆在塔1上，我们要把碟子都移动到塔2上，每次移动一个，而且任何时候都不能把大碟子压在小碟子上。
解题思路：三个塔，分为起始塔，目标塔，中转塔。每一次都是：将目标塔上n-1个砖放到中转塔，将最后一块砖放到目标塔，最后将中转塔上的砖放到目标塔。然后问题就变成了如何将目标塔上的n-1个砖放到中转塔，本质还是之前的那个思路，于是一个递归的方法就显而易见了。
#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);
}
}
在这个问题中给我们的启发是，递归的方法适用于循环解决同一流程的问题。
在解决这一问题中，汉诺塔的移动方式则是典型的先进后出，适合用栈的数据结构来表示塔。
列车车厢重排
问题描述：
一列货运列车有n节车厢，每节车厢要停靠在不同的车站。假设n个车站从1到n编号，而且货运列车按照从n到1的顺序经过车站。车厢的编号与它们要停靠的车站编号相同。为了便于从列车上卸掉相应的车厢，必须按照从前到后、从1到n的顺序把车厢重新排列。
车厢的重排工作在一个转轨站，其中有3个缓冲轨道H1、H2和H3。开始时挂有n节车厢的火车开始在入轨道，而最后在出轨道上的顺序是从右到左，即从1~n。
问题分析：
一节节车厢进入排序流程，如果它就是我要排出去的车厢，那么就不用进入缓冲轨道，如果它不是的话那么进入缓冲轨道，且要找到比他大的，又离他最近的一个数所在的轨道。
#include <vector>
#include <stack>
using namespace std;
// 全局变量
vector<stack<int,vector<int>>> track;
int numberOfCars; // 车厢的数量
int numberOfTracks; // 轨道的数量
int smallestCar; // 在缓冲轨道中编号最小的车厢
int itsTrack; // 停靠着最小编号车厢的缓冲轨道
void outputFromHoldingTrack() {
// 将编号最小的移出轨道
// 从栈itsTrack中删除编号最小的车厢
track[itsTrack].pop();
// 删除完了之后就要在所有栈顶中找到最小的车厢和其所在轨道
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) {
// 将车厢c移到一个缓冲轨道。返回false，当且仅当没有可用的缓冲轨道
// 为车厢c寻找合适的缓冲轨道
// 初始化
int bestTrack = 0;
int bestTop = numberOfCars + 1;
// 扫描缓冲轨道
for (int i = 1; i <= numberOfTracks; i++)
if (!track[i].empty()) {
int topCar = track[i].top();
// 遵循原则：找到里这个数最近的，但又比它大一些的轨道
if (c < topCar && topCar < bestTop) {
bestTop = topCar;
bestTrack = i;
}
}
else // 如果缓冲轨道为空且没有更好的选择
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) {
// 从初始顺序开始重排车厢
// 如果重排成功，返回true，否则返回false
numberOfCars = theNumberOfCars;
numberOfTracks = theNumberOfTrackers;
// 创建用于缓冲轨道的栈 这里是轨道数+1 目的就是考虑到了不存在的情况，如果不存在，那么我的bestTrack就是0
track.assign(numberOfTracks + 1, {});
int nextCarToOutput = 1; // 希望移出去的车厢号
smallestCar = numberOfCars + 1; // 缓冲轨道中无车厢
// 重排车厢
for (int i = 1; i <= numberOfCars; i++)
if (inputOrder[i] == nextCarToOutput) {
// 如果将要排位的车厢刚好就是我要移出去的，那么直接移出去
// 将车厢inputOrder[i]直接移出轨道
nextCarToOutput++;
// 移出去之后看看当前轨道里有没有也可以移出去的
while (smallestCar == nextCarToOutput) {
outputFromHoldingTrack();
nextCarToOutput++;
}
}
else
if (!putInHoldingTrack(inputOrder[i]))
return false;
return true;
该题基于栈的数据结构，抓住离开候选轨道、进入候选轨道的条件完成了此次排序。
离线等价类问题
问题描述：输入元素、关系，将这n个元素划分为等价类。
求解策略：
- 第一阶段，输入数据，建立n个表以表示关系对；
- 第二阶段，寻找等价类，是深度优先的策略。
离线等价类本质就是每个等价类形成了一棵树，通过深度优先遍历出来。
在线等价类问题就是知道元素，知道两两之间是否等价，将这n个元素划分为等价类。
在线等价类就是通过关系一步步把这棵树搭建起来。
目的都是为了划分等价类，不过两者对于等价关系的应用不一样。
布线问题
关键还是把握住出栈和入栈的条件。每一个线都把这个盒分了个区，所以说当这个线想要出栈时，区域内的线应该都出去了。有点类似于括号匹配问题。
配对问题通常考虑栈。
迷宫老鼠
寻找一条从入口到出口的路径。
首先把迷宫入口作为当前位置。如果当前位置是迷宫出口，那么已经找到了一条路径，寻找工作结束。如果当前位置不是迷宫出口，则在当前位置上放置障碍物，以阻止寻找过程又绕回到这个位置。
然后检查相邻位置是否有空闲。如果有，就移动到一个空闲的相邻位置，然后从这个位置开始寻找通往出口的路径。
为了方便移动，在进入新的相邻位置之前，把当前位置保存在一个栈中。
如果所有空闲的相邻位置都已经被探索果，但未能找到路径，则表明迷宫不存在此路径。
#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;
// 设置起点和终点
node start = { 1,1 };
node exit = { 10,10 };
// 初始化偏移量
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;
// 找无障碍的路
while (option <= lastOption) {
r = current_location.first + offset[option].first;
c = current_location.second + offset[option].second;
if (maze[r][c] == 0) break;
option++;
}
// 找到了，进行更新
if (option <= lastOption) {
path.push(current_location);
current_location.first = r;
current_location.second = c;
maze[r][c] = 1;
option = 0;
}
// 没找到，进行回溯或者返回未完成的路径
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();
}
}
从该代码中，可以学到的方法有：01地图表示、用预设的偏移量来表示移动。
综上所述，栈通常用于配对问题（括号匹配、布线问题）或者针对实际应用中事物的移动情况（汉诺塔、列车重排、离线等价类问题）或者搜索问题，尤其是深度优先（迷宫老鼠）。
队列
应用
列车车厢重排
#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++) {
// 弹出一节车厢
int train = trains.back();
trains.pop_back();
// 判断是否可以直接驶出轨道
if (train == next_train) {
target.push_front(next_train);
next_train++;
// 驶出之后，再看看当前轨道中有没有可以续上的车厢
target = clear_the_rest(target);
}
// 如果不可以，则将该车厢安排进轨道
else {
// 候选驶入轨道及其末尾车厢号，因为空视为车厢号为0，所以这里需要设置为-1
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();
// 找到仅次于驶入车厢的最大车厢号
if (train > max && max > wait_tr.second) {
wait_tr.first = i;
wait_tr.second = max;
}
}
// 实时更新最小车厢号及其位置
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;
}
电路布线（Lee算法）
Lee算法是一种从网格中寻找最短路径的经典算法。
比如说，我们要寻找a和b之间的最短路径。a和b之间的最短路径需要在两个过程中确定。一个是距离标记的过程，另一个是路径标记的过程。
在距离标记过程中，从位置a开始，把从a可到达的相邻方格都标记为1，然后把标记为1的方格可到达的方格标记为2，以此类推。直到到达b或者没有可到达的相邻的方格为止。
一旦到达b，b的编号便是b与a之间的距离。之后，路径标记过程开始，从方格b开始，首先移动到比b小1的相邻位置。重复这个过程，直到到达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;
}
// 初始化偏移量
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
// 初始化网格四周的障碍物
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表示无障碍且未标记，1表示障碍；于是起点设置为2，只要将距离-2就可得到真实距离。
grid[entrance.first][entrance.second] = 2;
int numOfNbrs = 4; // 一个方格的相邻位置数；
node nbr;
queue<node, deque<node>> q;
// 距离标记
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);
// 路径构造
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;
}