C++数据结构——栈
最近计划再复习一遍数据结构，看到一篇博客：https://www.cnblogs.com/QG-whz/p/5170418.html#_label0。
1、栈(Stack)是一种线性存储结构，它具有如下特点：
（1）栈中的数据元素遵守“先进后出"(First In Last Out)的原则，简称FILO结构。（后进先出的叫法，也是可以的）
（2）限定只能在栈顶进行插入和删除操作。
2、栈的相关概念：
（1）栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。
（2）压栈：栈的插入操作，叫做进栈，也称压栈、入栈。
（3）弹栈：栈的删除操作，也叫做出栈。
3、栈的常用操作为：
（1）弹栈，通常命名为pop
（2）压栈，通常命名为push
（3）求栈的大小
（4）判断栈是否为空
（5）获取栈顶元素的值
4、栈的常见分类：
（1）基于数组的栈——以数组为底层数据结构时，通常以数组头为栈底，数组头到数组尾为栈顶的生长方向
（2）基于单链表的栈——以链表为底层的数据结构时，以链表头为栈顶，便于节点的插入与删除，压栈产生的新节点将一直出现在链表的头部
5、实例分析
使用标准库的栈时, 应包含相关头文件，在栈中应包含头文件： #include< stack > 。定义：stack< int > s;
s.empty(); //如果栈为空则返回true, 否则返回false;
s.size(); //返回栈中元素的个数
s.top(); //返回栈顶元素, 但不删除该元素
s.pop(); //弹出栈顶元素, 但不返回其值
s.push(); //将元素压入栈顶（1）基于数组的栈
#include <stack>
#include <iostream>
using namespace std;int main()
{stack<int> mystack;int sum = 0;for (int i = 0; i <= 10; i++){mystack.push(i);}cout << "size is " << mystack.size() << endl;while (!mystack.empty()){cout << " " << mystack.top();mystack.pop();}cout << endl;system("pause");return 0;
}
//size is 11
// 10 9 8 7 6 5 4 3 2 1 0（2）基于单链表的栈
#include <iostream>
using namespace std;
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;T 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();}}
};
int main()
{Stack<char> s;s.push('a');s.push('b');s.push('c');while (!s.isEmpty()){cout << s.pop() << endl;}system("pause");return 0;
}
练习1、实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
解法参考博客：https://blog.csdn.net/cherrydreamsover/article/details/79475925，具体过程如下：
（1）使用两个栈，一个栈用来保存当前的元素，记做：stackData，一个栈用来保存压入操作每一步的最小元素，记做：stackMin。
（2）入栈：当stackData栈中压入一个数据时，判断satckMin中是否为空。若为空，将该元素压入stackMin栈中。若不空，判断两者之间的大小，当前者小于或等于后者时，将前者中的数据压入后者中；当前者大于后者时，
不进行任何操作。
（3）出栈：保证stackMin中栈顶的元素是stackData中最小的。
#include<iostream>
#include <stack>
#include <cassert>
using namespace std;//方法一： 一个辅助栈，如果这个栈为空，直接将元素入这个栈，如果辅助栈中有元素，将压入的元素和辅助栈顶元素比较，
//压入两者中较小的那个元素使得辅助栈总是维持栈顶元素为最小值。
//class Stack
//{
//public:
// void Push(int data)
// {
// stackData.push(data);
// if (stackMin.empty())
// {
// stackMin.push(data);
// }
// else
// {
// int tmp = stackMin.top();
// int min = data > tmp ? tmp : data;
// stackMin.push(min);
// }
// }
//
// void Pop()
// {
// assert(!stackData.empty() && !stackMin.empty());
// stackData.pop();
// stackMin.pop();
// }
//
// int GetMin()
// {
// assert(!stackMin.empty());
// return stackMin.top();
// }
//
//private:
// stack<int> stackData;
// stack<int> stackMin;
//}; //方法二： 一个辅助栈，如果这个栈为空，直接将元素入这个栈，如果辅助栈中有元素，将压入的元素和辅助栈顶元素比较，
//如果压入的元素小于等于辅助栈顶元素，者将这个元素入辅助栈，否则无操作，出栈的时候判断要出栈的元素是否等于辅助
//栈顶元素，如果是，也将辅助栈顶元素出栈。否则无操作。
class Stack
{
public:void Push(int data){stackData.push(data);if (stackMin.empty()){stackMin.push(data);}else{if (data <= stackMin.top()){stackMin.push(data);}}}void Pop(){assert(!stackData.empty() && !stackMin.empty());if (stackData.top() == stackMin.top()){stackMin.pop();}stackData.pop();}int GetMin(){assert(!stackMin.empty());return stackMin.top();}private:stack<int> stackData;stack<int> stackMin;};int main()
{Stack s;//s.Push(5); s.Push(36);s.Push(15);s.Push(95);s.Push(50);s.Push(53);cout << s.GetMin() << endl;system("pause");return 0;
}//15（3）栈的应用举例
1）进制转换
2）括号匹配的检验
3）行编辑程序
4）迷宫求解、汉诺塔等经典问题
5）表达式求值
6）栈与递归的实现
练习2、剑指offer面试题30——包含min函数的栈
题目描述
class Solution {
public:stack<int> stackData;//保存数据用的栈stackDatastack<int> stackMin;//保存最小的数的栈stackMin，其中它的栈顶始终为最小的数void push(int value) {stackData.push(value);if(stackMin.empty()) stackMin.push(value);//如果stackMin为空，则value是最小的值，入栈else{if(stackMin.top()>=value) stackMin.push(value);//否则当value小于等于stackMin的栈顶元素时，入栈（等于的时候也入栈是因为我考虑有相同的数）}}void pop() {if(stackData.top()==stackMin.top())//如果出栈的数刚好是最小的数，那么stackMin也应该出栈stackMin.pop();stackData.pop();}int top() {return stackData.top();//栈顶元素应返回stackData的栈顶元素}int min() {return stackMin.top();//stackMin的栈顶元素即是最小的数}
};运行结果：
练习3、剑指offer面试题31——栈的压入、弹出序列
参考博客：https://blog.csdn.net/budf01/article/details/76232497，解题思路为：创建一个栈进行压入、弹出操作。具体操作如下：
（1）当栈为空或者栈顶元素和popV当前元素不相等时，将pushV当前元素压入；
（2）当栈顶元素与popV当前元素相等时，将栈顶元素弹出，并移至popV下一个元素；
（3）如果需要压入的元素个数大于pushV的元素个数，说明popV不可能是pushV的弹出序列。
代码为：
class Solution {
public:bool IsPopOrder(vector<int> pushV,vector<int> popV) {//特殊输入测试if(pushV.empty() || popV.empty() || pushV.size()!=popV.size())return false;stack<int> mystack;//定义一个辅助栈int index=0;for(int i=0;i<popV.size();i++){//当辅助栈为空或者栈顶元素和popV当前元素不相等时，将pushV当前元素压入while(mystack.empty()||mystack.top()!=popV[i]){if(index>=pushV.size())//如果需要压入的元素个数大于pushV的元素个数，说明popV不可能是pushV的弹出序列return false;mystack.push(pushV[index++]);}//当栈顶元素与popV当前元素相等时，将栈顶元素弹出，并移至popV下一个元素if(mystack.top()==popV[i])mystack.pop();}return true;}
};运行结果：
当然可以利用其他思想解决，如引入哈希或直接利用向量的方式求解。
class Solution {
public:bool IsPopOrder(vector<int> pushV,vector<int> popV) {if(pushV.empty() && popV.empty() && pushV.size() != popV.size()){return false;}map<int,int> Hash; //用map做一个映射，入栈顺序的值不一定是递增 for(int i=0;i<pushV.size();i++){Hash[pushV[i]]=i+1;}int now=Hash[popV[0]]; //当前最靠后入栈的键值，例如题目给的4 3 5 1 2，now先等于4，再等于5for(int i=0;i<popV.size();i++){//如果入栈序列中没有这个值if(Hash[popV[i]]==0){return false;}if(Hash[popV[i]]>=now){now=Hash[popV[i]];}else if(Hash[popV[i]]<=Hash[popV[i-1]]){continue ;}else{return false;}}return true;}
};练习4、简单的括号匹配判断
例如，爱奇艺的一道实习在线编程题：当输入为（）（（））（），返回true；当输入为）（）（）（）（）），返回false，时间15min。（不能使用栈）
1、假设可以使用栈（15min可以完成）
C++代码：
#include <iostream>
#include <stack>
#include <vector>
using namespace std;bool isRight(vector<char> &vec){stack<char> stack1;bool index = false;if (vec.size() <= 1 || vec[0]!='(' || vec.size()%2!=0){return index;}for (int i = 0; i < vec.size(); i++){if (vec[i] == '(')stack1.push(vec[i]);else if (vec[i] == ')')stack1.pop();}if (stack1.empty())index = true;return index;
}int main(){//输入不定长的括号vector<char> vec;char tmpCh;char t;cout << "输入一串括号为：";do{cin >> tmpCh;vec.push_back(tmpCh);} while ((t = cin.get()) != '\n');//调用isRight函数bool myRes = isRight(vec);cout << myRes << endl;system("pause");return 0;
}运行结果：
python代码：
def isRight(str1):index = Falsetmp = []if(len(str1)>=2 and len(str1)%2==0 and str1[0]=='('):for id in range(len(str1)):if str1[id] == '(':tmp.append(str1[id])else:tmp.pop()if len(tmp)==0:index = Truereturn indexif __name__ == "__main__":try:while True:str1 = [i for i in input().split()]print(isRight(str1)) # 返回判断结果except:pass运行结果：
2、不能使用栈（15min，不太好想，mad，笔试那会儿就没想到！）
以下是我的想法，具体的过程如下：
（1）由于不能使用栈，将左括号定义为数值1，右括号定义为数值-1，存放到向量id（C++）或列表tmp （Python）中；
（2）初始化变量sum，用于判断总的求和结果是否等于0，若不等于0，则肯定不正确，若等于0，不一定正确；
（3）循环遍历输入的括号向量vec，判断当前括号属性的同时，进行累加求和，如果求和值小于等于-1，break（跳出循环）；
（4）最后再检查sum是否等于0，此时若等于0，则为正确。
C++代码：
#include <iostream>
#include <vector>
using namespace std;bool isRight(vector<char> &vec){vector<int> id(vec.size()); //用于存放左右括号的属性：左括号用1表示，右括号用-1表示int sum = 0;bool index = false;if (vec.size() <= 1 || vec[0]!='(' || vec.size()%2!=0){return index;}for (int i = 0; i < vec.size(); i++){if (vec[i] == '('){id.push_back(1);sum = id[i] + sum;}else if (vec[i] == ')'){id.push_back(-1);sum = id[i] + sum;if (sum <= -1)break;}}if (sum == 0)index = true;return index;
}int main(){//输入不定长的括号vector<char> vec;char tmpCh;char t;cout << "输入一串括号为：";do{cin >> tmpCh;vec.push_back(tmpCh);} while ((t = cin.get()) != '\n');//调用isRight函数bool myRes = isRight(vec);cout << myRes << endl;system("pause");return 0;
}运行结果同上
python代码：
def isRight(str1):index = Falsesum = 0tmp = []if(len(str1)>=2 and len(str1)%2==0 and str1[0]=='('):for id in range(len(str1)):if str1[id] == '(':tmp.append(1)sum += tmp[id]else:tmp.append(-1)sum += tmp[id]if sum<=-1:breakif sum == 0:index = Truereturn indexif __name__ == "__main__":try:while True:str1 = [i for i in input().split()]print(isRight(str1)) # 返回判断结果except:pass运行结果同上。
