栈(stack)是限制插入和删除只能在一个位置上进行的有序表,该位置是表的末端,即最后插入的元素的位置,叫做栈的顶(top)。栈的修改是按先进后出的原则进行的,因此,栈又叫LIFO(Last
In First Out)表。
栈有三种基本操作:
- 进栈
- 在栈顶增加一个元素。
- 出栈
- 把栈顶元素删除。
- 取栈顶元素
- 在不删除的情况下得到栈顶元素的值。
另外很多实现可以完成一些其他的操作:
- 清空
- 清空一个栈。
- 求元素个数
- 判空
判断一个栈是否为空。
//--------------------------------------------------------
了解一下STL(C++ Standard Library)中的stack的操作:
#include <stack> stack<类型名> s; s.empty( ) // 栈空返回true, 否则返回false s.pop( ) //移除堆栈中最顶层元素 s.push( ) //压栈 s.size( ) //返回当前栈中的元素个数 s.top( ) //引用栈顶元素
括号匹配问题
贴上自己渣渣的code:
#include <iostream> #include <stack> using namespace std; stack<char> s; int main() { char c, x; c=getchar(); while(c!='\n'){ if(c=='['||c=='('||c=='>') s.push(c); if(c==')'){ if(s.top()!='('){ cout<<"Don't match!"<<endl; break; } else s.pop(); } if(c==']'){ if(s.top()!='['){ cout<<"Don't match!"<<endl; break; } else s.pop(); } if(c=='}'){ if(s.top()!='{'){ cout<<"Don't match!"<<endl; break; } else s.pop(); } if(c=='>'){ if(s.top()!='<'){ cout<<"Don't match!"<<endl; break; } else s.pop(); } c=getchar(); } if( s.size()) cout<<"Don't match!"<<endl; else cout<<"It's match!"<<endl; return 0; }