栈
一、什么是栈？
- 特点总结为先进后出，后进先出 就是 “First In Last Out (FILO)” 这就是典型的“栈”结构。
- 从其操作特性来看，栈是一种“操作受限”的线性表，它只允许从一端进行数据的插入与移除。
二、 既然栈不如链表、数组灵活，为什么要用？
- 栈是一种操作受限的数据结构，其操作特性用数组和链表均可实现。
- 正因为栈没有数组、链表那样灵活，他暴露出来的接口越少，就越安全。不会很容易出现操作错误
- 特性之所以称为特性，就是因为有特殊的应用场景。当一个数据集只涉及在某端进行数据的插入和删除，并且满足顺序为先进者后出，后进者先出的特点(比如 括号的匹配问题 )。我们首选栈。
三、如何实现一个栈？
-
常见API
对于C++STL栈，我们常用的行为有 入栈、出栈、判断栈空、返回栈中元素数目、取栈顶元素等
//创建一个栈对象st，用来存储int型
stack<int> st;
//入栈
st.push(777);
//出栈
st.pop();
//判空
st.empty();//为空返回true,否则false
//返回栈内元素个数
st.size();
//取栈顶元素
st.top();
-
栈的实现——数组
栈的实现方式常见的有数组实现与链表实现，两种方式都可以很契合的实现栈FILO的特性
//JAVA实现
// 基于数组实现的顺序栈
public class ArrayStack {
private String[] items; // 数组
private int count; // 栈中元素个数
private int n; //栈的大小
// 初始化数组，申请一个大小为n的数组空间
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
// 入栈操作
public boolean push(String item) {
// 数组空间不够了，直接返回false，入栈失败。
if (count == n) return false;
// 将item放到下标为count的位置，并且count加一
items[count] = item;
++count;
return true;
}
// 出栈操作
public String pop() {
// 栈为空，则直接返回null
if (count == 0) return null;
// 返回下标为count-1的数组元素，并且栈中元素个数count减一
String tmp = items[count-1];
--count;
return tmp;
}
}
以上通过数组实现栈的方法中，在创建栈对象时，需要指定栈的容量大小。在向栈内添加元素时，维护一个已添加元素的下标指针count，始终指向已入栈元素的尾部。
那如果容量到达上限，需要实现动态容量的栈的话，为之奈何？
之前看到数组，在到达容量上限的时候，会自动扩容成原来的1.5倍。用类似的机制可以实现栈的扩容。在执行入栈操作的时候判断站内元素个数是否已达上限，若是，则调用resize()函数，重新划分数组的容量，再把原来的数据拷贝过去。
时间复杂度分析:据均摊复杂度的定义，多数情况下时间复杂度为O(1)，少数情况下（自动扩容）会成为O(n) 因为涉及所有栈内元素的拷贝操作。
空间复杂度分析：通常的入栈、出栈、访问栈顶操作。只需要一两个临时变量存储空间，此外我们可以直接访问到需要的元素，因此空间复杂度为O(1)级别。
-
栈的实现——链表
//C++的链表实现
template<class T>class Stack
{
private:
struct Node
{
T data;
Node *next;
};
Node *head;
Node *p;
int length;
public:
Stack()
{
head = NULL;
length = 0;
}
void push(T n)//入栈
{
Node *q = new Node;
q->data = n;
if (head == NULL)
{
q->next = head;
head = q;
p = q;
}
else
{
q->next = p;
p = q;
}
length ++;
}
T pop()//出栈并且将出栈的元素返回
{
if (length <= 0)
{
abort();
}
Node *q;
int data;
q = p;
data = p->data;
p = p->next;
delete(q);
length --;
return data;
}
int size()//返回元素个数
{
return length;
}
T top()//返回栈顶元素
{
return p->data;
}
bool isEmpty()//判断栈是不是空的
{
if (length == 0)
{
return true;
}
else
{
return false;
}
}
void clear()//清空栈中的所有元素
{
while(length > 0)
{
pop();
}
}
};
//借来网上大佬的代码，简洁美观，方便记忆
————————————————
版权声明：本文为CSDN博主「胡大炮的妖孽人生」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/huplion/article/details/49870831
时间复杂度分析：压栈与弹栈均为O(1)级别，因为只需要工改单个节点的索引即可。
空间复杂度分析：在入栈与出栈过程中，只需要一两个临时变量存储空间，所以也为O(1)级别。
四、栈的应用
- 栈在函数调用中的应用
操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将其中的临时变量作为栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
- 栈在数学表达式求值中的应用
利用两个栈，其中一个用来保存操作数，另一个用来保存运算符。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较，若比运算符栈顶元素优先级高，就将当前运算符压入栈，若比运算符栈顶元素的优先级低或者相同，从运算符栈中取出栈顶运算符，从操作数栈顶取出2个操作数，然后进行计算，把计算完的结果压入操作数栈，继续比较。
- 在括号匹配中的用法
用栈保存为匹配的左括号，从左到右一次扫描字符串，当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号，如果能匹配上，则继续扫描剩下的字符串。如果扫描过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。
当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明未匹配的左括号为非法格式。
- 实现浏览器的前进、后退功能
我们使用两个栈X和Y，我们把首次浏览的页面依次压如栈X，当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据一次放入Y栈。当点击前进按钮时，我们依次从栈Y中取出数据，放入栈X中。当栈X中没有数据时，说明没有页面可以继续后退浏览了。当Y栈没有数据，那就说明没有页面可以点击前进浏览了。
五、 一些问题
Q：在讲栈的应用时，讲到用函数调用栈来保存临时变量，为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？
A：函数的调用执行顺序是符合FILO 先进后出，后进先出的特点的。
比如函数中定义的局部变量的生命周期的长短是：先定义的生命周期长，后定义的生命周期短；
函数中调用函数也是这样，先开始执行的函数只有等到内部调用的其他函数执行完毕，该函数才能执行结束。
由于以上特点，再结合数据结构是特定应用场景的抽象的原则，我们优先考虑栈结构，但并不是其他数据结构不可以用。
从调用函数进入被调用函数，对于数据来说变化的是作用域所以从根本上来说只要能保证每次进入一个新的函数，都是一个新的作用域就可以。要实现此功能，栈是非常方便的，当进入到被调用函数的时候，分配一段栈空间给这个函数的变量，当函数结束的时候，将栈顶复位，正好回到调用函数的作用域内。(这个角度还是蛮厉害的，很有道理)
Q：数据结构中的“栈”与内存中的“栈”什么关系？是同一个东西？
A：内存中的“栈”是虚拟的内存空间，数据结构中的堆栈是抽象的数据存储结构。
内存空间逻辑上分为三部分：代码区、静态数据区、动态数据区。
动态数据去又被分为栈区和堆区。
代码区：存储方法体的二进制代码。
静态数据区：存储全局变量、静态变量、常量。包括final修饰的常量等，由系统自动分配和回收。
栈区：存储运行方法的一个形参、局部变量、返回值。由系统自动分配和回收。
堆区：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据。
习题
有效的括号 LC:20
LC20——有效的括号
//逻辑判断，略显复杂
//总的就是遍历符号串s，遇到左边括号就入栈，遇到右边括号就与栈顶元素匹配，若能匹配，则弹出栈顶元素模拟匹配过程
//若不能匹配，则说明该串非法，出现了右边括号先出现的情况。
//一般都是用右边括号消去左边括号，若出现左边括号的剩余，上述逻辑无法判断，只需最终判断st是否为空(是否s中所有的左括号都被消除了)
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(auto ss:s){
if(ss == '(' || ss == '{' || ss == '[') st.push(ss);
else{
if(st.empty()) return false;
else if(st.top() == '(' && ss == ')' || st.top() == '{' && ss == '}' || st.top() == '[' && ss == ']') st.pop();
else return false;
}
}
return st.empty();
}
};
//引入哈希表
class Solution {
public:
bool isValid(string s) {
stack<char> st;
unordered_map<char,char> mymap{{']','['},{')','('},{'}','{'}};
for(int i=0;i<s.size();i++){
if(s[i] == '{' || s[i] == '(' || s[i] == '['){
st.push(s[i]);
}
//注意一个问题，在判断栈为空与判断栈顶元素与遍历到的s[i]是否相等时，首先考虑 若栈此时为空，则取st.top()会报错
//因此把该判断条件前移。切记！
else if(!st.empty() && st.top() == mymap[s[i]]) st.pop();
else return false;
}
return st.empty();
}
};
最小栈 LC:155
LC155——最小栈
//是实现一个类的题目，还是比较吃细节
//基本思路是用一个栈，但是存放的是键值对，第一个元素是当前模拟的栈的存入数据(有效部分)
//第二个元素存放的是目前为止的栈的最小值。因为栈的特性，每次入栈的元素只需要与栈顶元素的最小值进行比较即可。
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int val) {
//要注意当栈为空的情况，此时直接栈内元素为val，最小元素也只有val因此特殊考虑，直接作键值压栈
if(st.empty()) st.push({val,val});
else st.push({val,min(st.top().second,val)});
}
void pop() {
st.pop();
}
int top() {
//要注意键值对用的是"."方法 不是“->”
return st.top().first;
}
int getMin() {
return st.top().second;
}
private:
stack<pair<int,int>> st;
};
//链表实现
//本质和栈存储键值类似，也是同时维护最小值与最后入栈的值，但是链表的写法比较新颖
//而且这个链表的实现方式不是从头节点向后拓展，而是在原先节点的基础上直接添加新的头节点。
//这样出栈的时候，负责维护栈顶元素的头节点指针就可以转移到正确的地方去了。
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
// 初始结点为空
head = nullptr;
}
void push(int x) {
if(head==nullptr){
// 两步走
// 1.新建结点 最小值为入栈结点值 新结点指向head
// 2.head移动到新结点
head = new ListNode(x,x,head);
}else{
// 最小值为 入栈结点值和之前结点最小值的min
head = new ListNode(x,min(x,head->min),head);
}
}
void pop() {
// 删除末端
ListNode* p = head;
head = head->next;
//delete 一般慎用，直接释放p指针指向的内存，意味着删除了整个节点。
//删除之前记得让指针转移到正确的地方。
//使用的内存不是连续的，随时删除，这是链表的好处
delete p;
}
int top() {
return head->val;
}
int getMin() {
return head->min;
}
private:
// 声明链表结构
//多了一个min元素，当前链表节点同时要维护栈当前值与目前为止所有元素的最小值
struct ListNode{
int val;
int min;
ListNode* next;
ListNode():val(0),min(0),next(nullptr){}
ListNode(int _val,int _min, ListNode* _next):val(_val),min(_min),
next(_next){}
};
// 初始结点
ListNode* head;
};
用栈实现队列 LC:232
LC232——用栈实现队列
//同样是用栈来写一个类模拟一个功能，看来栈在很多种场合下都很适合。
//倒腾，核心就是倒腾，关键是什么时候倒腾，如果每次入栈出栈都倒腾，复杂度会增加
//如果是出栈 取队前元素时倒腾，有均摊复杂度可降为O(1)
//用两个FILO结构去模拟FIFO结构，那就考虑入栈时，效果是一致的，当出栈时，用另一个FILO容器去倒腾当前FILO容器，让原本容器中的顺序颠倒过来。
//可以想象两个瓶子，按顺序往其中一个里面放小物块。
//当想取出第一个放进去的小物块又希望剩下的物块保持一定顺序的时候，就把两个瓶子口对口倒腾一下，就按要求取出来了。
class MyQueue {
private:
stack<int> IN, OUT;
//一个倒腾函数。目的是把输入栈的顺序逆序存放在输出栈中
void IN2OUT(){
while(!IN.empty()){
OUT.push(IN.top());
IN.pop();
}
}
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
IN.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
if(OUT.empty()){
IN2OUT();
}
int x = OUT.top();
OUT.pop();
return x;
}
/** Get the front element. */
int peek() {
if(OUT.empty()) IN2OUT();
return OUT.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return (IN.empty() && OUT.empty());
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
累了，明天写叭
比较含退格的字符串 LC:844
LC:844——比较含退格的字符串
//用栈来实现吧，每个字符串都压栈。
//遇到退格'#'且栈不为空时，弹出栈顶元素；
//遇到退格'#'但栈为空时，保持。
//最后比较两个栈是否完全一致
class Solution{
public:
//用一个函数来实现压栈的过程吧，这样方便拓展到多个字符串的实现
void Instack(stack<char>& st,string& s){
for(int i=0;i<s.size();i++){
if(s[i] == '#'){
if(st.empty()) continue;
else st.pop();
}
else st.push(s[i]);
}
}
bool backspaceCompare(string s,string t){
stack<char> sts,stt;
Instack(sts,s);
Instack(stt,t);
return sts == stt;
}
}
基本计算器 LC:224
LC:224——基本计算器
//困难题，但是不是逻辑上的困难，是实现的时候需要考虑的情况稍微多一点。
//首先是把字符串转化成数字，如果是python的话也许会简单很多。
//其次是对括号的处理，很容易可以想到用栈来实现匹配操作。
//在括号之外的情况，直接运算到结果里，遇到括号，把左括号里的数字都压栈
//当遇到匹配的右括号时，把栈内元素计算出来
//这样遇到套叠的括号也不会有问题
//符号只有正负，所以用sign变量来标志正负，若为负，则用-sign*当前元素，最后统一用加法实现。
//还有一个问题就是字符串里会出现空格' ' 有点狗。。遇到空格就忽略吧，不予操作，注意一下就好了。
class Solution {
public:
int calculate(string s) {
stack<int> st;
int sign = 1,ans = 0;
for(int i=0;i<s.size();i++){
char c = s[i];
//在ASCII表中，数字0的值比较大，超过其他可能出现的字符+ - ( )等，用判断ASCII值大于'0'可以快速筛选出数字。
if(c>='0'){
int num = 0;
//用临时变量num表示当前处理的，可能是个多位数的数字。
while(i<s.size() && s[i]>='0'){
//这里是i++ 意味着当前处理的仍然是字符s[i]，处理之后i++ 然后while循环处再判断是否下一位仍满足条件。
num = 10*num + (s[i++] - '0');
}
ans += sign*num;
//处理完这段数字后要回退一格，否则大循环的i++操作会略过下一个符号位。
--i;
}
else if(c == '+') sign = 1;
else if(c == '-') sign = -1;
//当遇到左括号，把当前阶段的数字之和结果压栈，再把符号位压栈，接下来处理左括号内部的优先操作部分。
//如果再遇到左括号，同样的把上一个左括号到这一个左括号之间的部分压栈，当前左括号前的符号压栈。
//这样括号的优先顺序不会变，当出栈时总是从最里面的括号开始处理。
else if(c == '('){
//入栈时，先将上一部分的阶段和压栈，然后是当前符号位，依次交替，顺序别乱。
st.push(ans);
st.push(sign);
ans = 0;
sign = 1;
}
//当遇到右括号时，表明与之匹配的左括号内的数据处理完毕了。准备把之前压栈的各个括号部分的和取出来。
else if(c == ')'){
//出栈时栈顶一定是上一个符号位，接着是上一段括号的元素之和，依次交替，顺序别乱。
ans *= st.top();
st.pop();
ans += st.top();
st.pop();
}
}
return ans;
}
};
棒球比赛 LC:682
LC:682——棒球比赛
//用栈实现就可以了，把数字压栈，遇到特殊操作特殊处理。
//题目还蛮友好的，保证每个操作都一定是有效的，别想那么多了，冲吧
//注意给的是字符串，字符串！！！ 如果是特殊操作“C” “D” “+”，就直接判断操作就好。
//如果是数字，谨慎一点，还要小心溢出的问题，这道题好像不会。
//先判断操作指令，把数字的判断放到else里面。
class Solution {
public:
int calPoints(vector<string>& ops) {
stack<int> st;
int ans = 0;
for(auto o:ops){
if(o == "+"){
int temp1 = st.top();
st.pop();
int temp2 = st.top();
st.push(temp1);
st.push(temp1+temp2);
}
//MDZZ，这个地方之前把0当成o了 看了一上午，人傻了都。以后再也不用o了，要换成y或者x这样有区分度的字母
else if(o == "D"){
st.push(2*st.top());
}
else if(o == "C"){
st.pop();
}
else{
//C++中string转int的方法
//函数原型 int atoi(const char*nptr)
//atoi( ) 函数会扫描参数 nptr字符串，跳过前面的空白字符（例如空格，tab缩进等）
//可以通过isspace( )函数来检测），直到遇上数字或正负符号才开始做转换.
//而再遇到非数字或字符串结束时('\0')才结束转换，并将结果返回。
//如果 nptr不能转换成 int 或者 nptr为空字符串，那么将返回 0。
//C++中若需要将string类型转为int类型，需先将string转为const char*。 非常重要。
st.push(atoi(o.c_str()));
}
}
while(!st.empty()){
ans+=st.top();
st.pop();
}
return ans;
}
};
下一个更大元素I LC:496
LC:496: 下一个更大元素
//简单逻辑 再nums2中找到nums1中的数字，再在nums2中该位置开始向后遍历。
//若找到符合条件的就存入答案，否则就是非法的，ans存入-1
//若在nums2中找到的数字已经是nums2中的最后一个，那么一定是非法的，直接存入-1。
//逻辑很简单，感觉可以进一步优化
//暴力法，逻辑简单，但是复杂度过高为O(MN)
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int> ans;
for(int i=0;i<nums1.size();i++){
//注意find函数并不属于vector，而实借用algorithm.h实现的，他将返回vector指定搜索范围内指向指定元素的迭代器。
vector<int>::iterator it = find(nums2.begin(),nums2.end(),nums1[i]);
if(it == nums2.end()-1) ans.push_back(-1);
else{
for(auto nit = it+1;nit!=nums2.end();nit++){
if(*nit > nums1[i]){
ans.push_back(*nit);
break;
}
if(nit == nums2.end()-1) ans.push_back(-1);
}
}
}
return ans;
}
};
//单调栈，单调栈的用途很窄，但是偏偏就是解决这一类问题的。
//单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。
//首先顺序遍历nums2将2中的元素压入单调栈。
//入栈规则：若栈为空，则直接压栈。若栈非空，首先弹出所有比自身小的元素，然后压栈。栈内元素保持单调递增。
//同时加入一个哈希表，在单调栈出栈过程中，需要被弹出的元素的下一位更大元素就是当前操作元素。
//将机将弹栈的元素做键，当前操作元素做值。映射关系为 A元素的下一位更大元素B mymap[A] = B
//单调栈制作过程中更新哈希表。单调栈制作完成后，栈内剩余的元素呢？
//剩余的元素意味着他们的后面没有更大的元素了，也就是不符合题意的元素。
//对剩余的元素，更新哈希表，值用-1代替，意味着它们是非法的。
//最后遍历nums1的值，并对照哈希表更新每个元素在nums2中的下一位更大值。
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map <int,int> mymap;
stack<int> st;
vector<int> ans;
for(int i=0;i<nums2.size();i++){
while(!st.empty() && st.top()<nums2[i]){
mymap[st.top()] = nums2[i];
st.pop();
}
st.push(nums2[i]);
}
while(!st.empty()){
mymap[st.top()] = -1;
st.pop();
}
for(auto n:nums1){
ans.push_back(mymap[n]);
}
return ans;
}
};
