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;
//保存数据用的栈stackData
-
stack<
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，再等于5
-
for(
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 =
False
-
tmp = []
-
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 =
True
-
return index
-
-
if __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 =
False
-
sum =
0
-
tmp = []
-
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:
-
break
-
if sum ==
0:
-
index =
True
-
return index
-
-
if __name__ ==
"__main__":
-
try:
-
while
True:
-
str1 = [i
for i
in input().split()]
-
print(isRight(str1))
# 返回判断结果
-
except:
-
pass
运行结果同上。
转载：https://blog.csdn.net/zichen_ziqi/article/details/80807989