# :-: **栈(Stack)** * 本篇只是强调如何使用栈，请自行选择是否观看。 <br> ## **栈是什么** * **栈**是一种非常重要的线性结构，从数据结构角度来看，栈也是线性表，其特殊性在于它是受限的线性表。 * **栈**的特性：后进先出(Last In First Out) * 对于栈来说，表尾端有其特殊含义，成为**栈顶**（top），相应的，表头端称为**栈底**（bttom）。 * 不含元素的栈称为空栈。 <br> ## **栈的定义及操作** * 假设栈 S 中的元素按照的次序进栈，则称为栈底元素，为栈顶元素。出栈的第一个元素应该是栈顶元素(如下图所示) *  * 举个例子：你在洗碗把洗好的碗编号为1、2、、、n依次摞起来，1号在最下面，向上编号依次增加，然后再从上到下把碗放好，这样的话，先被洗的碗，就后被放好。 #### **栈的操作** * 定义栈 `stack<int> s; // 声明存储int类型数据的栈` * 常用操作 `s.empty()//如果栈为空返回true，否则返回false ` `s.size()//返回栈中元素的个数 ` `s.pop()//删除栈顶元素但不返回其值 ` `s.top()//返回栈顶的元素，但不删除该元素 ` `s.push(X)//在栈顶压入新元素 ，参数X为要压入的元素` ## **一些实例** * [HDU2031进制转换](http://acm.hdu.edu.cn/showproblem.php?pid=2031)，我们用栈来实现一下进制转换问题 ``` #include <cstdio> #include <stack> using namespace std; int main() { int N,R; int negetive;//控制是否输出负号 while(~scanf("%d %d",&N,&R)) { stack<int> s;//定义一个栈 negetive = 0; if(N<0) { negetive = 1; N = -N; } while(N)//利用栈来实现进制转换是非常方便的 { s.push(N%R);//每次往栈里放入余数 N /= R; } if(negetive) printf("-"); while(s.size())//判断栈是否为空，我喜欢这样子用 { int z = s.top();//取栈顶元素 if(z<10) printf("%d",z); else printf("%c",z - 10 + 'A'); s.pop();//让栈顶元素出栈 } puts("");//输出回车的另外一种方式 } return 0; } ``` * 栈在很多方面都具有很大的用处的，比如火车调度问题,括号匹配问题，表达式求值问题，都可以用栈来实现， ## **一些例题** * [火车调度问题](http://acm.hdu.edu.cn/showproblem.php?pid=1022&tdsourcetag=s_pctim_aiomsg)，问以前者进栈，正否以后者出栈 * [大鱼吃小鱼](http://www.51nod.com/Challenge/Problem.html#!#problemId=1289%3Ftdsourcetag=s_pctim_aiomsg) * [Seinfeld](http://acm.hdu.edu.cn/showproblem.php?pid=3351&tdsourcetag=s_pctim_aiomsg) * [括号配对问题](http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=2) * [括号匹配（二）](http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=15) * [表达式求值](http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=35) 建议把上边的问题给做一下