数据结构之——栈
栈
一.简单介绍：（来自维基百科）[概念 stack.h及其多个接口]
计算机科学中，栈是一种抽象数据类型，LIFO（Last in first out）后进先出，用两个基本的操作pop(弹出)和push(压入)用于存储元素。
根据pop和push的操作，使得一个序列栈具有先进后出的机制。这种机制也是线性数据类型，弹出和压入都只是在序列的最后一个元素(也就是一个栈的top)中进行。峰值操作就是在序列顶部进行的。
如上图的操作，那么要实现这样的两个简单的操作应该怎么进行呢?
// stack::push/pop
#include <iostream> // std::cout
#include <stack> // std::stack
int main ()
{
std::stack<int> mystack;
for (int i=0; i<5; ++i) mystack.push(i);
std::cout << "Popping out elements...";
while (!mystack.empty())
{
std::cout << ' ' << mystack.top();
mystack.pop();
}
std::cout << 'n';
return 0;
}
其实Stack是C++里面的一个STL，所以可以直接调用这个源文件，所以mystack.pop和mystack.push可以直接调用，但是回归到源文件去看看这个类库里面的一些有用的接口：
1.push()：将元素压到栈顶
2.stackinit():初始化整个栈
3.pop():将元素从栈顶弹出
4.top():返回栈顶元素
5.stacksize():返回栈中元素个数
6.isempty():判断栈是否为空
二.栈的基本实现模板
template <typename T>class stack::public vector <T>{
public://可以沿用vector中的size()和empty()
void push(T const & e){insert(size(),e)}//入栈
T pop(){return remove(size()-1);}//出栈
T & top{return (this)[size()-1];}//取顶
}
前面实现过向量，这里可以直接公有继承vector类的一些成员.
三.栈的简单基本应用
由于LIFO的基本特点，可以让栈拥有很独特的使用价值，这种数据存储方式可以运用到许多方面，比如计算普通的二进制：
- 短除法：
这段代码的具体实现方式为：
void convert(stack<char>&s,_int64 n,int base){
static char digit[] //新进制下的数位符号，可视base取值适当扩充
{'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
while(n>0){
S.push(digit[n%base]);//余数入栈
n/base;//n更新为其对base的除商
}
}
当然，这串代码输出在主函数直接pop就可以了，在pop弹出之前还要判断是否已经是空栈，如果是空栈，就结束输出。
- 括号匹配的实例
除了基本的二进制之外，还有一个很重要的：括号匹配，运用于许多语言（比如HTML）的括号匹配检查机制。简单说就是判断括号是否是()成对出现的，为了完成这个判断，也需要运用到栈的物理存储方式。
（简直不能忍，这图太丑~）
具体实现方式：（摘自：GP-KING）
bool isbalance(const string &str)
{
string::size_type len = str.size();
Stack<char> stack;
for(string::size_type i = 0; i < len ; ++ i)
{
/*first selection 左括号都进去*/
if(str[i] == '[' || str[i] == '{' ||
str[i] == '(' || str[i] == '<')
{
stack.push(str[i]);
}
/*判断右括号的类型都*/
if(str[i] == ']' || str[i] == '}' ||
str[i] == ')' || str[i] == '>')
{
/*判断是否为空*/
if(stack.isempty())
{
cout << "the string is Unblanced" << endl;
return false;
}
/*switch-case来完成弹出*/
switch(str[i])
{
case ']':
{
/*一一对应*/
if('[' != stack.pop())
{
cout << "Can not blanced with ]" << endl;
return false;
}
break;
}
case ')':
{
if('(' != stack.pop())
{
cout << "Can not blanced with )" << endl;
return false;
}
break;
}
case '}':
{
if('{' != stack.pop())
{
cout << "Can not blanced with }" << endl;
return false;
}
break;
}
case '>':
{
if('<' != stack.pop())
{
cout << "Can not blanced with >" << endl;
return false;
}
break;
}
/*如果是没以上括号 就返回*/
default:
break;
}
}
}
/************************************************
判断是否为空决定是否括号匹配
************************************************/
if(stack.isempty())
{
cout << "string is blanced!!" << endl;
return true;
}
else/*如果不匹配 弹出剩下的*/
{
cout << stack.pop() << " " << "Unblance string!!" << endl;
return false;
}
}
- 栈的复杂应用
著名的逆波兰表达式：RPN
大意：RPN，是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。也就是平常所说的后缀表达式。
基本表达式 ： (2+3)*7
RPN表达式 ：2 3 + 7 *
后缀表达式的求值算法只使用了一个堆栈，即数字堆栈，没有必要再使用例外一个操作符栈，因为每个操作符一旦被读取就会马上被使用。
我们一般的写法都是中缀表达式，这就需要我们把中缀表达式转换为后缀表达式然后再进行表达式的计算。
实例：中缀表达式在栈中的实现，需要使用两个栈，一个存放数字，一个存放操作符
- 具体的：中缀表达式转换为后缀表达式（参考 主页菌）
1+((2+3)×4)-5
运用2个栈，一个是真正后缀表达式的栈，一个是存放运算符的栈
1.遇到操作数，放在后缀表达式的栈中S2
2.当栈为空的时候，遇到运算符，直接入栈
3.遇到左括号，入栈S1
4.遇到右括号，执行出栈操作，并将出栈的操作符压入后缀的栈中，直到弹出栈的左括号，左括号不弹出。
5.遇到其他运算符，加减乘除，弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入后缀的S2栈
6.最终将栈中的元素依次出栈，输出。
（捂脸）这个实现我自己还没有写，最近备考二级想刷刷题，觉得这个可能要写个3-4小时才搞得出来…..就讲到这里吧。希望把数据结构系列写完了就写一个语法分析器。
Written by:SpeakNow
Enjoy Reading This Article?
Here are some more articles you might like to read next: