文章目录

• 栈
• • 应用
  • • 括号匹配
    • 汉诺塔
    • 列车车厢重排
    • 离线等价类问题
    • 布线问题
    • 迷宫老鼠
• 队列
• • 应用
  • • 列车车厢重排
    • 电路布线（Lee算法）

栈

栈和队列可以视为数组和链表的限制版本。

应用

括号匹配

问题描述：对一个字符串的左右括号进行匹配。

解题思路：遇到左括号，入栈。遇到右括号，出栈，若没元素，显然是不匹配的。字符串遍历后，如果栈里面还有元素，那么也是不匹配的。

#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个元素划分为等价类。

求解策略：

1. 第一阶段，输入数据，建立n个表以表示关系对；
2. 第二阶段，寻找等价类，是深度优先的策略。

离线等价类本质就是每个等价类形成了一棵树，通过深度优先遍历出来。

在线等价类问题就是知道元素，知道两两之间是否等价，将这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;

}