100字范文 > 《数据结构算法与应用 —— C++语言描述》学习笔记 — 栈 —— 应用（一）

《数据结构算法与应用 —— C++语言描述》学习笔记 — 栈 —— 应用（一）

时间：2023-06-14 00:59:29

《数据结构、算法与应用 —— C++语言描述》学习笔记 — 栈 —— 应用（一）

一、括号匹配二、汉诺塔问题1、扩展stack的拷贝赋值2、实现三、列车车厢重排1、问题描述2、求解策略3、算法及实现4、测试代码5、复杂度

一、括号匹配

括号匹配是一个典型的用栈这种数据结构解决的问题。其基本原理是每一个右括号都应该与前面最后一个出现的左括号匹配。因此，我们只要以栈结构保存所有出现的左括号，然后每当遇到一个右括号就把栈顶的左括号取出，即可知道有哪些左括号或右括号没有匹配。

LeetCode有一道题为此类问题的变形：

这个问题本身并不复杂。我们只要抓住什么样的括号子串是有效的：可能是两个或多个匹配的括号对续接为一个合理的括号子串（如“((()(())()”中的“()(())()”）；也可能是一个括号子串（如“(((())”中的“(())”）。因此，不难发现以下规则：

1、只有当我们遇到一个右括号时，才可能有一个新的有效子串；

2、当且仅当每个右括号按照括号匹配规则与一个左括号匹配，左右括号中间的部分才是有效括号;

3、多个匹配的括号对可以续接的条件是前一个括号对的右括号与后一个括号对的左括号紧邻。

因此，我们可以得到下面的算法：

1、使用一个栈保存遇到的左括号的位置上，使用一个数组保存每个右括号对应有效括号子串的长度（初始值为0）；

2、遍历数组：

（1）每当遇到一个左括号，将其index放入栈中;

（2）每当遇到一个右括号，如果栈不为空，则认为该右括号对应于一个有效括号串；

（3）确定该有效串所属的最长有效括号子串的长度：计算当前有效串的长度（根据index之差）与左括号index- 1 所对应的有效括号子串长度之和。根据其结果确定是否需要更新最长有效子串的长度。

实现如下：

#include "arrayStack.h"#include "../linearList/arrayList.h"int longestValidParentheses(string s) {arrayStack<int> st;arrayList<int> arrPos(s.length());int maxLength = 0;for (int i = 0; i < s.length(); i++){if (s.at(i) == '('){st.push(i);}if (s.at(i) == ')'){if (!st.empty()){int iPos = st.top();st.pop();int lastLength = iPos - 1 >= 0 ? arrPos[iPos - 1] : 0;int length = i - iPos + 1 + lastLength;arrPos[i] = length;maxLength = maxLength > length ? maxLength : length;}}}return maxLength;}

二、汉诺塔问题

汉诺塔问题来自大梵天创世的一个古老传说。在创世之日，有一座钻石宝塔（塔1），其上有64个金碟，所有碟子从大到小从塔底堆到塔顶，旁边还有另外两座钻石宝塔（塔2和塔3）。从创世之日起，婆罗门一直试图把塔1上的碟子移动到塔2去，不过要借助塔3。由于碟子非常重，所以一次只能移动一个碟子。另外，任何时候大碟子都不能压在小碟子上面。根据这个传说，等到婆罗门把盘子搬完了，世界末日就到了。

在汉诺塔问题中，假设有n个碟子和3座塔。初始时所有碟子从大到小堆在塔1上，我们要把碟子都移动到塔2上，每次移动一个，而且任何时候都不能把打碟子压在小碟子上面。

汉诺塔的经典解法是使用递归。我们这里借助栈结构显示每次移动之后三座塔的数据。

1、扩展stack的拷贝赋值

template<class T>inline arrayStack<T>::arrayStack(const arrayStack& other){T* pTmp = new T[other.arrayLength];copy(other.stack, other.stack + other.arrayLength, pTmp);stack = pTmp;arrayLength = other.arrayLength;stackTop = other.stackTop;}

2、实现

#pragma once#include "arrayStack.h"arrayStack<int> tower[3]; // 全局变量，用于保存每座塔的盘子/** @param n移动的盘子个数* @param from 从哪个塔移动* @param to 移动到哪个塔* @param relay 中继塔*/void moveAndShow(int n, int from, int to, int relay);/** @brief 显示三座塔状态*/void showState();void towerOfHanoi(int n){for (int d = n; d > 0; d--){tower[0].push(d);}showState();moveAndShow(n, 0, 2, 1);}void moveAndShow(int n, int from, int to, int relay){if (n <= 0){return;}moveAndShow(n - 1, from, relay, to);int d = tower[from].top();tower[from].pop();tower[to].push(d);showState();moveAndShow(n - 1, relay, to, from);}void showState(){for (int i = 0; i < 3; i++){arrayStack<int> temp(tower[i]);cout << "dishes in tower" << i + 1 << ": ";while (!temp.empty()){cout << temp.top() << " ";temp.pop();}cout << endl;}cout << endl;}

如果我们尝试打印四个盘子的汉诺塔的移动，其结果为：

汉诺塔问题的时间复杂度为 O ( 2 n O(2^{n} O(2n)。

三、列车车厢重排

1、问题描述

一列货运列车有n节车厢，每节车厢要停靠在不同的车罩。假设n个车站从1到n编号，而且货运列车按照从n到1的顺序经过车站。车厢的编号要与它们要停靠的车站编号相同。为了便于从列车上卸载掉相应的车厢，必须按照从前之后、从1到n的顺序把车厢重新排列。这样排列之后，在每个车站只需要卸掉最后一节车厢即可。车厢重排工作在一个转轨站进行。转轨站上有个一个入轨道（input track）、一个出轨道（output track）和k个缓冲轨道（holding track）。缓冲轨道位于入轨道和出轨道之间。如图显式了轨道的相对位置，以及某种输入车厢序列及其输出情况：

2、求解策略

为了重拍车厢，我们从前至后检查入轨道上的车厢。如果当前车厢是满足排列要求的下一节车厢，就直接把它移动到出轨道上。如果不是，则把它移动到缓冲轨道上，直到它满足排列要求时才将它移动到出轨道上。缓冲轨道时按照LIFO的方式管理的。在重排车厢的过程中，仅允许以下移动：

（1）车厢可以从入轨道的前端移动到一个缓冲轨道的顶部或出轨道的后端。

（2）车厢可以从一个缓冲轨道的顶部移动到出轨道的后端。

简单分析下这个问题，不难看出对于某种排序的车厢，该问题是否有解取决于缓冲轨道的数量。因此，我们可以得出该问题有解的两个条件：

（1）在整个过程中，任何一条缓冲轨道上的车厢都需要保证从顶到底是递增的。

如果不满足这个条件，必然会导致编号大的车厢先进入输出队列中。这个条件等同于当我们从入轨道中移动车厢到缓冲轨道时，需要找到某个空轨道或者轨道顶部车厢序号大于当前车厢序号的缓冲轨道。

（2）从入轨道中移动车厢到缓冲轨道时，如果有多个满足条件的缓冲轨道时，其选择的优先级按照当前车厢序号与轨道顶部车厢序号之差的顺序从小到大排列，空轨道的优先级最低。

这个条件是为了保证所有的缓冲轨道都能被充分利用。如果以每条轨道当前顶部元素值作为该轨道的容量，那么我们可以认为向某缓冲轨道中添加新的车厢时，该轨道顶部车厢编号与新车厢编号越小，意味着缓冲轨道剩余的总容量越大。

考虑极限情况，对于初始排列为1,n,n-1,n-2,…,2的车厢需要n-1个缓冲轨道。

3、算法及实现

算法放于注释之中：

#include "arrayStack.h"#include <tuple>#include <queue>/** @brief 排序车厢* @param inputOrder 初始车厢顺序* @param numOfCars 车厢数* @param numOfTracks 缓冲轨道数* @return 返回说明*true 排序成功*false 不满足要求，排序失败 string - errmsg*/tuple<bool, string> railroad(int inputOrder[], int numOfCars, int numOfTracks){auto tracks = new arrayStack<int>[numOfTracks]; // 所有缓冲轨道int smallestCar = numOfCars + 1; // 所有缓冲轨道中最小的车厢编号int smallestTrack = -1;// 最小车厢编号对应的缓冲轨道号int needCar = 1; // 下一个希望输出的车厢编号for (int i = 1; i < numOfCars + 1; i++){// 遍历车厢并检查输入车厢是否为下一个希望输出的车厢if (inputOrder[i] == needCar){// 1 如果是下一个希望输出的车厢，则：// 1.1 将其输出到输出队列中，并递增下一个希望输出的车厢编号cout << "Move car " << needCar << " from input track to output track" << endl;needCar++;// 1.2 寻找缓冲轨道中是否已经保存了下一个希望输出的车厢while (smallestCar == needCar){// 如果是，则：// 1.2.1 删除编号最小的车厢tracks[smallestTrack].pop();cout << "Move car " << needCar << " from holding track " << smallestTrack << " to output track " << endl;// 1.2.2 寻找现在编号最小的车厢及其所说缓冲队列smallestCar = numOfCars + 2;for (int i = 0; i < numOfTracks; ++i){if (!tracks[i].empty() && tracks[i].top() < smallestCar){smallestCar = tracks[i].top();smallestTrack = i;}}// 1.2.3 递增下一个希望的车厢编号needCar++;}}else{// 2 如果不是下一个车厢，则// 2.1 寻找最适合放入输入车厢的缓冲轨道int bestTop = numOfCars + 1; // 最佳缓冲轨道对应的栈顶车厢编号（用于比较）int bestTrack = -1;// 最佳缓冲轨道for (int j = 0; j < numOfTracks; ++j){if (!tracks[j].empty()){// 2.1.1 如果当前缓冲轨道的栈顶车厢编号比想要放进来的车厢编号大且二者之间的差值比当前的最优差值小，则更新if (tracks[j].top() > inputOrder[i] && tracks[j].top() < bestTop){bestTop = tracks[j].top();bestTrack = j;}}else if (bestTrack == -1){// 2.2.2 有空轨道时，选择该轨道；// 因为当遇到一个空轨道时，所有不为空的缓冲轨道必然在前面遍历过了。bestTrack = j;}}// 2.2 如果没找到能放入当前输入车厢的缓冲轨道，则说明缓冲轨道数不满足要求去if (bestTrack == -1){return make_tuple<bool, string>(false, "too few tracks");}// 2.3 将车厢从输入轨道移入输出轨道tracks[bestTrack].push(inputOrder[i]);cout << "Move car " << inputOrder[i] << " from input track to holding track " << bestTrack << endl;// 2.4 如果需要，更新缓冲轨道中最小编号的车厢及其轨道号if (inputOrder[i] < smallestCar){smallestCar = inputOrder[i];smallestTrack = bestTrack;}}}return make_tuple<bool, string>(true, "");}

在1.2.2步骤，我们在将重新寻找缓冲轨道编号最小的车厢时，需要重置smallestCar（否则后面的比较永远无法成功）。有趣的是，我们重新选择的初值为numOfCars + 2。这是因为：

这段代码所处的while循环的退出条件是smallestCar != needCar。这个条件会在两种情况下被触发。第一种情况是所有的输入车厢都已经到达输出车厢（最后一个是通过缓冲轨道到达输出队列的）；第二种情况是缓冲轨道没有车厢了或者缓冲轨道中编号最小的车厢不是期待输出的车厢。这个初值正是为了解决第一种情况。在此情况下，needCar的值为numOfCars + 1。因此如果想要使循环能够顺利退出，我们就不能让smallestCar的值也为numOfCars + 1。

4、测试代码

void test(){int p[] = {0, 3, 6, 9, 2, 4, 7, 1, 8, 5 };cout << "Input permutation is 369247185" << endl;auto [result, error] = railroad(p, 9, 3);cout << boolalpha << "result = " << result << " error = " << error << endl;}

5、复杂度

整个算法包含三个for循环，一个while循环。不难看出，步骤1.2.2和步骤2.1中的for循环的复杂度均为O(numOfTracks)。在1.2的while循环中，我们无法估计每次调用的复杂度，但是我们可以分析出，在外层for循环的整个执行过程中，内层while循环执行的总次数不会超过numOfCars。因此，2.1的for循环和1.2中的while循环总的时间复杂度均为O(numOfCars * numOfTracks)。其余部分执行需耗时O(numOfCars)（不考虑push的扩容）。因此该算法总的复杂度为O(numOfCars * numOfTracks)。