营销型建设网站公司,专业建设公司网站,南昌有哪些推广平台,中国软件开发公司排行#x1f4d6; 1.1 什么是栈
栈是一种线性数据结构#xff0c;具有后进先出#xff08;Last-In-First-Out#xff0c;LIFO#xff09;的特点。可以类比为装满盘子的餐桌#xff0c;每次放盘子都放在最上面#xff0c;取盘子时也从最上面取#xff0c;因此最后放进去的盘… 1.1 什么是栈
栈是一种线性数据结构具有后进先出Last-In-First-OutLIFO的特点。可以类比为装满盘子的餐桌每次放盘子都放在最上面取盘子时也从最上面取因此最后放进去的盘子最先取出。栈的典型应用场景有函数调用、括号匹配、表达式求值等。
元素从固定一侧开口进入和离开栈的操作分别称为入栈和出栈。
栈中元素由深到浅存储我们将栈最深的存储位置称为栈底当前栈中最外围元素所在的位置则称为栈顶。 栈底通常固定不变而栈顶则由当前栈中最外侧元素位置栈中元素数量确定。
由栈的特点可知栈的插入和删除入栈和出栈操作都是在栈顶这一端进行的。
栈顶Top线性表允许进行插入删除的那一端。 栈底Bottom固定的不允许进行插入和删除的另一端。 空栈不含任何元素的空表。
栈又称为后进先出Last In First Out的线性表简称LIFO结构 栈的常见基本操作 InitStack(S)初始化一个空栈S 。 StackEmpty(S)判断一个栈是否为空若栈为空则返回true否则返回false。 Push(S, x)进栈栈的插入操作若栈S未满则将x加入使之成为新栈顶。 Pop(S, x)出栈栈的删除操作若栈S非空则弹出栈顶元素并用x返回。 GetTop(S, x)读栈顶元素若栈S非空则用x返回栈顶元素。 DestroyStack(S)栈销毁并释放S占用的存储空间“”表示引用调用。 1.2 栈的实现数组模拟
栈的实现可以使用数组来模拟。我们可以定义一个固定大小的数组和一个指向栈顶的指针。栈顶指针初始化为 -1表示栈为空。每次入栈操作时将元素放入数组并将栈顶指针加一出栈操作时将栈顶指针减一。
#include iostream
using namespace std;const int MAX_SIZE 100; // 栈的最大容量
int stack[MAX_SIZE]; // 栈的数组
int top -1; // 栈顶指针// 入栈操作
void push(int x) {if (top MAX_SIZE - 1) {cout 栈已满无法入栈 endl;return;}stack[top] x;
}// 出栈操作
void pop() {if (top -1) {cout 栈为空无法出栈 endl;return;}top--;
}// 获取栈顶元素
int peek() {if (top -1) {cout 栈为空无栈顶元素 endl;return -1;}return stack[top];
}// 判断栈是否为空
bool isEmpty() {return top -1;
}// 获取栈的大小
int size() {return top 1;
}int main() {push(1);push(2);push(3);cout 当前栈顶元素 peek() endl;cout 栈的大小 size() endl;pop();cout 当前栈顶元素 peek() endl;cout 栈是否为空 (isEmpty() ? 是 : 否) endl;return 0;
}运行结果
当前栈顶元素3
栈的大小3
当前栈顶元素2
栈是否为空否1.3 栈的实现STL 方法
在 C 中我们也可以使用标准模板库STL提供的 stack 容器来实现栈。使用 stack 容器非常方便不需要手动处理数组和指针。
#include iostream
#include stack
using namespace std;int main() {stackint st;st.push(1);st.push(2);st.push(3);cout 当前栈顶元素 st.top() endl;cout 栈的大小 st.size() endl;st.pop();cout 当前栈顶元素 st.top() endl;cout 栈是否为空 (st.empty() ? 是 : 否) endl;return 0;
}运行结果
当前栈顶元素3
栈的大小3
当前栈顶元素2
栈是否为空否使用 stack 容器我们可以更方便地实现栈的入栈、出栈、获取栈顶元素等操作而无需自己处理底层的数据结构。 1.4 出入栈顺序火车调度案例
火车调度是一个经典的栈的应用场景。给定 n 辆火车的进站顺序请输出所有可能的出站顺序。
我们使用递归来生成所有可能的出站顺序。对于每一辆火车它可以先进站再出站也可以直接从进站过程中出站。我们不断尝试所有可能的出站顺序直到所有火车都出站。
#include iostream
#include vector
using namespace std;void dfs(vectorint in, vectorint out, vectorint path) {if (in.empty() out.empty()) {for (int num : path) {cout num ;}cout endl;return;}if (!in.empty()) {int num in.back();in.pop_back();path.push_back(num);dfs(in, out, path);path.pop_back();in.push_back(num);}if (!out.empty()) {int num out.back();out.pop_back();path.push_back(num);dfs(in, out, path);path.pop_back();out.push_back(num);}
}int main() {vectorint in {1, 2, 3};vectorint out;vectorint path;dfs(in, out, path);return 0;
}运行结果
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 1.5 栈的应用
有效的括号
题目描述
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
示例 1
输入s ()
输出true示例 2
输入s ()[]{}
输出true示例 3
输入s (]
输出false提示
1 s.length 104s 仅由括号 ()[]{} 组成 力扣官方题解https://leetcode.cn/problems/valid-parentheses/solutions/373578/you-xiao-de-gua-hao-by-leetcode-solution/ 我们遍历给定的字符串 s。当我们遇到一个左括号时我们会期望在后续的遍历中有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合因此我们可以将这个左括号放入栈顶。 当我们遇到一个右括号时我们需要将一个相同类型的左括号闭合。此时我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型或者栈中并没有左括号那么字符串 s 无效返回False。为了快速判断括号的类型我们可以使用哈希表存储每一种括号。哈希表的键为右括号值为相同类型的左括号。 在遍历结束后如果栈中没有左括号说明我们将字符串 s 中的所有左括号闭合返回 True否则返回 False。 注意到有效字符串的长度一定为偶数因此如果字符串的长度为奇数我们可以直接返回 False省去后续的遍历判断过程。 栈在括号匹配中有着重要的应用。给定一个只包含 (、)、[、]、{ 和 } 的字符串判断括号是否匹配。
使用栈可以轻松解决这个问题。遍历字符串中的每个字符如果是左括号将其入栈如果是右括号判断与栈顶元素是否匹配若匹配则出
栈否则返回 false。最后检查栈是否为空为空则括号匹配。
#include iostream
#include stack
#include unordered_map
using namespace std;bool isValid(string s) {stackchar st;unordered_mapchar, char mapping {{), (}, {], [}, {}, {}};for (char c : s) {if (c ( || c [ || c {) {st.push(c);} else if (c ) || c ] || c }) {if (st.empty() || st.top() ! mapping[c]) {return false;}st.pop();}}return st.empty();
}int main() {cout isValid(()) endl; // 输出1 (true)cout isValid(()[]{}) endl; // 输出1 (true)cout isValid((]) endl; // 输出0 (false)return 0;
} 总结
栈是一种非常重要的数据结构在计算机算法中有着广泛的应用。通过模拟入栈和出栈操作我们可以解决很多实际问题比如火车调度、括号匹配等。同时C 中也提供了标准模板库STL中的 stack 容器方便我们使用栈来解决问题。熟练掌握栈的使用将会对你的编程技能有很大的提升。
⭐️希望本篇文章对你有所帮助。
⭐️如果你有任何问题或疑惑请随时向提问。
⭐️感谢阅读
