栈
1.定义
栈是限定仅在表头进行插入和删除操作的线性表。要搞清楚这个概念，首先要明白”栈“原来的意思，如此才能把握本质。"栈“者,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。首先系统或者数据结构栈中数据内容的读取与插入（压入push和 弹出pop）是两回事！插入是增加数据，弹出是删除数据 。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。栈允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底。
2.性质
简而言之为先进后出。
3.应用
1．进栈（PUSH）算法
①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；
②置TOP=TOP+1（栈指针加1，指向进栈地址）；
③S(TOP)=X，结束（X为新进栈的元素）；
2．退栈（POP）算法
①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；
②X=S(TOP)，（退栈后的元素赋给X）：
③TOP=TOP-1，结束（栈指针减1，指向栈顶）。
代码实现
1.进栈（PUSH）算法
void PUSH(){
if(top>=n) printf("Wrong");
stack[++top]=a;
return;
}
2．退栈（POP）算法
void POP(){
if(top<=0) printf("Wrong");
x=stack[top--];
return;
}
4.例题
1.表达式求值
1+2(3-(5-6)8) 中缀表达式
1 2 + 后缀表达式：
思路：
开一个栈，逐个扫描这个后缀表达式
1）数字：入栈
2）运算符：取出栈顶两个数，进行一次运算，把运算结果入栈。
中缀表达式怎么转后缀表达式？
开一个栈，用于存储运算符。逐个扫描我们的中缀表达式
1）数：直接输出
2）碰到运算符（+ - * /），如果栈为空或者当前运算符的优先级高于栈顶的优先级，直接入栈。否则（当前的优先级小于或等于栈顶的优先级），栈顶一直出栈，直到符合前面两个情况，再将当前的运算符入栈。
3）如果是左括号：直接入栈
4）如果是右括号：一直出栈，直到碰到左括号
即优先级大于入栈，优先级小于等于出栈；
1+2(3-(5-6)8)
后缀表达式：1 2 3 5 6 - 8 * - * +（逆波兰表达式）
前缀表达式 （波兰表达式）（由后向前扫，优先级大于等于入栈，优先级小于出栈）
代码实现
先咕咕以后再补
5.单调栈，单调队列
例题
一个长度为N的整数序列，从中找出一段长度不超过M的连续子序列，让这个子序列所有数的和最大。
1 2 -10 6 8 4 10
M = 4
-1 -1 -8 -9 -5 100 -99 -8
M = 4
暴力：枚举子序列的起点，枚举子序列的长度（1->M）
优化：
前缀和 S【i】前i项的和
【L，R】===S【R】-S[L-1]，
找到两个位置x和y，让s【y】-s【x】最大且y-x<=M，枚举右端点i，当i固定的时候，去找左端点j
满足的条件就是:j=>[i-m,i-1]，并且s[j]最小。
1）判断队头（最左端）与i的距离是否超出M的范围，如果超出了出队
2）当前的队头就是最优的选择
3）不断删除队尾，直到队伍对应的S值小于S[i]，然后把i作为一个新的入队
代码实现
#include<bits/stdc++.h>
using namespace std;
long long n,m,sum[300010],q[300010],l=1,r=1,k,ans;
int main(){
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;++i){
scanf("%lld",&k);
sum[i]=sum[i-1]+k;
}
q[1]=0;
for(int i=1;i<=n;++i){
while(l<=r&&q[l]<i-m) l++;
ans=max(ans,sum[i]-sum[q[l]]);
while(l<=r&&sum[q[r]]>=sum[i]) r--;
q[++r]=i;
}
printf("%lld",ans);
return 0;
}
6.习题
yzoj：
1515，1681，1680，1679
yzoj1680括号画家：
题目描述
Candela是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。这一天，刚刚起床的Candela画了一排括号序列，其中包含小括号( )、中括号[ ]和大括号{ }，总长度为N。这排随意绘制的括号序列显得杂乱无章，于是Candela定义了什么样的括号序列是美观的：
(1) 空的括号序列是美观的；
(2) 若括号序列A是美观的，则括号序列 (A)、[A]、{A} 也是美观的；
(3) 若括号序列A、B都是美观的，则括号序列AB也是美观的。
例如 (){} 是美观的括号序列，而 )({)[}]( 则不是。
现在Candela想在她绘制的括号序列中，找出其中连续的一段，满足这段子序列是美观的，并且长度尽量大。你能帮帮她吗？
输入
一个由括号组成的字符串。
输出
一个整数，表示最长的美观的子段的长度。
样例输入
({({(({()}})}{())})})[){{{([)()((()]]}])[{)]}{[}{)
样例输出
4
提示：字符串长度不超过100000
思路：
单调栈，左括号进，右括号出，遇到匹配的记录长度，当遇到不匹配的出并且计数器清零，取每次的最大值。
代码实现
#include<bits/stdc++.h>
using namespace std;
char str[100010],line[100010];
int ans=0,add,len,sum,tot;
bool flag=1;
bool book(char a,char b){
if(a=='('&&b==')') return true;
if(a=='{'&&b=='}') return true;
if(a=='['&&b==']') return true;
else return false;
}
int main(){
scanf("%s",str+1);
len=strlen(str+1);
for(int i=1;i<=len;++i){
if(str[i]=='('||str[i]=='{'||str[i]=='['){
line[++add]=str[i];
}
else{
while(book(line[add],str[i])&&add){
i++;
sum++;
add--;
}
ans=max(ans,sum);
while(str[i]!='('&&str[i]!='{'&&str[i]!='['&&book(line[add],str[i])==0&&add!=0){
i++;
sum=0;
add--;
}
if(str[i]=='('||str[i]=='{'||str[i]=='['){
line[++add]=str[i];
}
}
}
printf("%d",ans*2);
return 0;
}