一、栈ADT是what？
1、定义
栈，是限制插入和删除都只能在一个位置上进行的表。
2、图示
3、栈的基本功能
（1）是否为空
（2）进栈
（3）出栈
（4）清空
（5）取栈顶
二、栈的链表实现
#ifndef Exercise_Stack_h
#define Exercise_Stack_h typedef struct Node *PrtToNode;
typedef PrtToNode Stack;
typedef int ElementType; struct Node
{
ElementType Element;
PrtToNode Next;
}; bool IsEmpty(Stack S); Stack CreateStack(); void MakeEmpty(Stack S); void Push(ElementType X,Stack S); void Pop(Stack S); ElementType Top(Stack S); #endif bool IsEmpty(Stack S)
{
return S->Next==nullptr;
} Stack CreateStack()
{
Stack S; S = new struct Node;
if(S==nullptr)
{
std::cout<<"Create Error!"<<std::endl;
return nullptr;
} S->Next=nullptr; return S;
} void MakeEmpty(Stack S)
{
if(S==nullptr)
{
std::cout<<"not initStack Error!"<<std::endl;
return ;
} while (!IsEmpty(S))
{
Pop(S);
} } void Push(ElementType X,Stack S)
{
PrtToNode Temp; Temp = new struct Node;
if(Temp==nullptr)
{
std::cout<<"init Node Error!"<<std::endl;
return;
} Temp->Element=X;
Temp->Next=S;
S->Next=Temp;
} void Pop(Stack S)
{
if(IsEmpty(S))
{
std::cout<<"Stack Empty!"<<std::endl;
return;
}
auto temp = S->Next;
S->Next=S->Next->Next;
delete temp;
} ElementType Top(Stack S)
{
if(IsEmpty(S))
{
std::cout<<"Stack Empty!"<<std::endl;
return ;
}
return S->Next->Element;
}
PS：优点：不用担心栈溢出的现象
缺点：开辟内存和释放内存的时候貌似开销比较昂贵。
三、栈的数组实现
typedef int ElementType;
const int MaxCapacity = ; struct StackRecord
{
int Capacity;
int TopOfStack;
ElementType *Array;
}; typedef struct StackRecord *Stack; bool IsFull(Stack S); bool IsEmpty(Stack S); Stack CreateStack(int MaxElements); void DisposeStack(Stack S); void MakeEmpty(Stack S); void Push(ElementType X,Stack S); void Pop(Stack S); ElementType Top(Stack S); ElementType TopandPop(Stack S); Stack CreateStack(int MaxElements)
{
Stack S; S = new struct StackRecord;
if(S==nullptr)
{
std::cout<<"Out of space!"<<std::endl;
return nullptr;
} S->Array = new ElementType(MaxElements);
if(S->Array==nullptr)
{
std::cout<<"Out of space!"<<std::endl;
return nullptr;
} S->Capacity=MaxElements;
S->TopOfStack=-; MakeEmpty(S); return S; } void DisposeStack(Stack S)
{
if(S!=nullptr)
{
delete S->Array;
delete S;
}
} bool IsEmpty(Stack S)
{
return S->TopOfStack==-;
} void MakeEmpty(Stack S)
{
S->TopOfStack=-;
} void Push(ElementType X,Stack S)
{
if(IsFull(S))
{
std::cout<<"Full Stack"<<std::endl;
return;
}
S->Array[++S->Array[S->TopOfStack]]=X; } ElementType Top(Stack S)
{
if(!IsEmpty(S))
{
return S->Array[S->TopOfStack];
} std::cout<<"Empty Error"<<std::endl;
return ;
} void Pop(Stack S)
{
if(IsEmpty(S))
{
std::cout<<"Empty Error"<<std::endl;
}
else{
S->TopOfStack--;
}
} ElementType TopandPop(Stack S)
{
if(!IsEmpty(S))
{
return S->Array[S->TopOfStack--];
}
std::cout<<"Empty Error"<<std::endl;
return ; } bool IsFull(Stack S)
{
return S->Capacity==MaxCapacity;
}
优点：把不断开空间的时间省下来了；
缺点：数组商都是有限的；
四、应用
（1）括号的匹配
void test(string s)
{
auto stack = CreateStack(); for(auto c: s)
{
if(c=='['||c=='{'||c=='(')
{
Push(c, stack);
}
else
{
if(c==']'||c=='}'||c==')')
{
if(IsEmpty(stack))
{
cout<<"Error!"<<endl;
}
else
{
if(c==']')
{
auto temp = TopandPop(stack);
if(temp!='[')
{
cout<<"Error!"<<endl;
}
}
else if(c=='}')
{
auto temp = TopandPop(stack);
if(temp!='{')
{
cout<<"Error!"<<endl;
}
}
else if(c==')')
{
auto temp = TopandPop(stack);
if(temp!='(')
{
cout<<"Error!"<<endl;
}
}
else
{
cout<<"Scanf Error!"<<endl;
} }
}
else
{
cout<<"Scanf Error!"<<endl;
}
} } if(stack->TopOfStack==-)
{
cout<<"RIGHT"<<endl;
}
else
{
cout<<"Error!"<<endl;
} }
（2）后缀表达式的计算。
后缀表达式的优点就是完全不需要考虑什么优先级之类的，直接从左边算到右边就可以了，简直方便快捷，在这里我就默默的实现下，小白勿喷
int calculate(string S) //10以内的整数运算
{ auto stack = CreateStack(); for(auto c:S)
{
switch (c)
{
case '+' :
{
auto t1=TopandPop(stack);
auto t2=TopandPop(stack);
double t3=t1+t2; Push(t3, stack);
} break;
case '-':
{
auto t1=TopandPop(stack);
auto t2=TopandPop(stack);
double t3=t2-t1; Push(t3, stack);
}
break;
case '*':
{
auto t1=TopandPop(stack);
auto t2=TopandPop(stack);
double t3=t2*t1; Push(t3, stack);
}
break;
case '/':
{
auto t1=TopandPop(stack);
auto t2=TopandPop(stack);
double t3=t2/t1; Push(t3, stack);
}
break;
default:
{
Push(c-'', stack);
}
break;
}
} return Top(stack); }
3、中缀表达式转化成后缀表达式
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std; int pre(char a) //操作符优先级比较
{
if(a == '=' || a == '(')
return ;
else if(a == '+' || a == '-')
return ;
else if(a == '*' || a == '/')
return ;
else
{
cout<<"Error!"<<endl;
return ;
}
} int main()
{
string str;
stack<char> ope; //操作符
vector<char> ans;//后缀表达式
vector<char>::iterator start, end;
getchar(); //清除输入垃圾 while(!ope.empty()) //初始化
ope.pop();
ans.clear();
ope.push('='); //结束标志
cin>>str;
auto len = str.length();
for(int i = ; i < len; ++i)
{
if(str[i] >= '' && str[i] <= '') //操作数直接存入ans
ans.push_back(str[i]);
else if(str[i] == '(') //左括号入栈
ope.push(str[i]);
else if(str[i] == ')') //右括号，将匹配的左括号内容存入ans,左括号出栈
{
while (ope.top() != '(')
{
ans.push_back(ope.top());
ope.pop();
}
ope.pop(); //左括号出栈
}
else if(pre(str[i]) > pre(ope.top())) //优先级大于栈顶元素则入栈
ope.push(str[i]);
else //小于栈顶元素
{
while(pre(str[i]) <= pre(ope.top()))
{
ans.push_back(ope.top());
ope.pop();
}
ope.push(str[i]);
}
}
while(ope.top() != '=') //其余操作符存入后缀表达式中
{
ans.push_back(ope.top());
ope.pop();
}
for(start = ans.begin(), end = ans.end(); start < end; ++start)
printf("%c", *start);
printf("\n"); return ;
}