一.栈和队列
栈
队列
二.栈的应用-单调栈
三.队列的应用-单调队列
四.习题
一.用两个栈实现队列
二.栈的压入、弹出序列
三.包含min函数的栈
一.栈和队列栈谈到栈，要答到以下三点：
栈是「只允许一端进行元素插入与删除」的线性表(数组)；插入和删除的一端叫做「栈顶」；栈的性质是先进后出；栈的一般操作:栈定义;向栈顶插入一个元素;从栈顶弹出一个元素;栈顶的值;判断栈是否为空;
栈定义,tt表示栈顶:int[]stk=newint[N];//初始值设为0目的是为了使得数组有意义inttt=0;向栈顶插入一个元素：
stk[++tt]=x;从栈顶弹出一个元素:
tt--;栈顶的值：
stk[tt];判断栈是否为空：
if(tt0){//表明栈不为空}队列
谈到队列，要答到以下三点：
队列是「只允许从一端插入，另一端删除」的线性表(数组)；允许插入的一端称为「队尾」，允许删除的一端称为「队头」；队列的性质是先进先出；队列的一般操作:队列的定义;向队尾插入一个元素;从队头弹出一个元素;队头的值;判断队列是否为空;
队列的定义,hh表示队头,tt表示队尾：int[]q=newint[N];//从队尾插入元素,因此队尾值初始为-1inttt=-1;//从队头出元素，队头默认比队尾大1,初始为0;inthh=0;向队尾插入一个元素：
q[++tt]=x;从队头弹出一个元素：
hh++;队头的值：
q[hh];判断队列是否为空:
if(hh=tt){//队列不为空}二.栈的应用-单调栈
单调栈解决的典型问题是:
给定一个序列，求序列中的每个数「左边离它最近的比它小的数」在什么地方。首先这种题的普通做法是两层循环，第一层循环遍历序列的每个值i，第二层循环从i-1个数向前遍历，如果遍历到的值比a小,就进行输出。
for(inti=0;in;i++){for(intj=i-1;j=0;j--){if(aa[j]){//输出a[j]}}}
那么考虑使用单调栈的解法，就是利用栈的性质对循环中的过程进行优化。随着i遍历序列时，可以用栈来存储i左边的元素，在这种情况下，有一些元素会永远不会以答案输出：如果在栈中，stk[3]stk[5]时，那其实stk[3]永远也不会输出。因为：如果当前值i大于stk[5],因为stk中存的是i左边的所有元素，离i最近的是stk[5],且最小的也是a[5],会以a[5]输出；如果当前值i小于等于a[5],则可以把i入栈,也没有stk[3]什么事;由此来构造一个单调递增的栈，即「只要i比栈顶元素小，就把栈顶元素弹出，直到找到小于i的栈元素，再把小于i栈顶元素输出，把当前值i插入到栈中」。
//arr={}//-13-inttt=0;inthh=0,tt=-1;int[]stk=newint[n];for(inti=0;iarr.length;i++){while(tt!=nullstk[tt]=arr))tt--;if(tt0){//如果栈不为空，说明栈顶元素就是离i近的最小元素System.out.print(stk[tt]);}elseSystem.out.print(-1);stk[++tt]=arr;}三.队列的应用-单调队列
单调队列解决的典型问题是:「找出滑动窗口中的最大值/最小值」。
先看下暴力解法：双层循环。第一层循环遍历序列的每个值i，将值存入队列中，当值个数到达滑动窗口的数目时，先从队尾进队一个元素，再从队头出队一个元素。第二层就是遍历这个队列求出最小值后输出。
再看下在这个过程中，怎样利用队列的性质来进行优化。在队尾元素左边的值，如果比队尾值还大，那么在判断窗口最小值时，队尾左边的值一定是不可能作为输出的，于是可以把该值从队列的队头移出。
由此来构造一个单调的队列，从而只需每次输出队头元素，就可以找到滑动窗口的最小值。
//arr={1,3,-1,-3,5,3,6,7}//hh是队头,tt是队尾inthh=0,tt=-1;int[]q=newint[n];int[]arr=newint[n];//队列存的是index//求最小值for(inti=0;in;i++){//保证滑动数组每次向右移动一格;if(hh=tti-k+1q[hh])hh++;while(hh=ttarr[q[tt]]=arr)tt--;q[++tt]=i;if(i=k-1)System.out.print(arr[q[hh]]+"");}
题目连接：