栈与队列
相信很多同学都在功课基础课，今天cht带大家攻克栈与队列。
一、栈的模拟
模拟栈是用数组模拟出可以弹出栈底，像栈顶插入，判断栈是否为空，查询栈顶元素的栈。
我们可以用tt来存栈的一端。
每次插入时数组的长度加1，那我们把tt++，然后我们把数加入tt。
那具体如何插入呢？
方法就是把上面两部加在一起：
tt += 1;
stk[tt] = x;
快速写法就是合二为一：
stk[ ++ tt] = x;
弹出就简单多了，直接
tt --;
就好了。
然后怎么算一下栈空不空呢？
其实也很简单。如果tt是0，那栈应该就是空的。
所以代码就是：
if(tt) cout << "NO" << endl;
else cout << "YES" << endl;
快速就是：
cout << (tt ? "NO" ; "YES") << endl;
然后是查询，就直接输出stk[tt]就好了。
对，这就是模拟栈，就是这么简单。
接下来我们应用到题目上。
请看题目： ACWING.818模拟栈
这题把模板套一遍就行了，很弱对吧。
具体模板：
#include<iostream>
using namespace std;
const int N = 100010;
int m;
int stk[N], tt;
int main()
{
cin >> m;
while(m --)
{
string op;
int x;
cin >>op;
if(op == "push")
{
cin >> x;
stk[ ++ tt] = x;
}
else if(op == "pop")
{
tt --;
}
else if(op == "empty") cout << (tt ? "NO" : "YES") << endl;
else cout << stk[tt] << endl;
}
return 0;
}
快速写法：
#include<iostream>
using namespace std;
const int N = 100010;
int m, tt, stk[N], x;
int main()
{
cin >> m;
while(m --)
{
string op;
cin >> op;
if(op == "push")
{
cin >> x;
stk[ ++ tt] = x;
}
else if(op == "pop") tt --;
else if(op == "empty") cout<<(tt ? "NO" : "YES") << endl;
else cout<< stk[tt] << endl;
}
}
好然后我们看队列。
队列就有点难了（稍微，大家别怕），毕竟y总说过：
你觉得一个算法难是因为你的大脑对未知世界的恐惧。——yxc巨佬
所以其实队列很弱。
队列有这么几个功能需要模拟。
1. 向队尾插入一个数x
2. 从队头弹出一个数
3. 判断队列是否为空
4. 查询队头元素
可能大家不太好理解队列的操作，所以我来带着大家 想象一下。
你在一个公园里排队买票。假设人们都很礼貌，很有素质，大家都不插队，然后一个人买完票会从队头出来（操作2），要买票需要从队尾进入（操作1），看看有没有人买票（操作3），看看正在买票的人是谁（操作4）。
是不是明白了？
好我们看看对应模板。
我们设两个端点tt = -1, hh = 0, 分别表示队列的两端。
插入和栈一样：
tt += 1;
q[tt] = x;
快速写就是：
q[ ++ tt] = x;
从队头弹出一个数我们把队头加加那队头就会被弹出。
hh ++;
判断队列是否为空的话我们就看看队头是否是小于等于队尾的，如果是就不为空，否则为空（可以想象一下如果队头是3队尾是2这还是一个队列吗？）
那就是：
if(hh <= tt) cout << "NO" << endl;
else cout << "YES" << endl;
快速写法就是：
cout << (hh <= tt ? "NO" : "YES") << endl;
接下来我们讲解一道模板题：
请看题目： ACWING.829模拟队列
本题为模板题，直接套模板：
#include<iostream>
using namespace std;
const int N = 100010;
int n, q[N], hh, tt=-1;
int main()
{
cin >> n;
while(n --)
{
string op;cin >> op;
int x;
if(op == "push")
{
cin >> x;
q[ ++ tt] = x;
}
else if(op == "pop") hh ++;
else if(op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl;
else cout << q[hh] << endl;
}
}
最后分享下津津的储蓄计划的AC代码（上次思考题）
昨天晚上看了看y总的题解又自己想了想最后终于弄出来了。
#include<iostream>
using namespace std;
int main()
{
int now = 0, store = 0, add_money = 300;
int a[12];
for(int i = 0; i < 12; i ++) cin >> a[i];
for(int i = 0; i < 12; i ++)
{
if(a[i] > now + add_money)
{
cout << "-" << i + 1 << endl;
return 0;
}
now += add_money - a[i];
store += now / 100 * (1.2 * 100);
now %= 100;
}
cout << store + now << endl;
return 0;
}
栈与队列的作业会在讲完单调栈和单调队列后分别布置。
