第3章栈和队列
3．1实战题解析
【实战3．1】POJ1363——铁轨问题


视频讲解


时间限制： 1000ms； 内存限制： 65536KB。
问题描述： A市有一个著名的火车站，那里的山非常多。该站建于20世纪，不乐观的是该火车站是一个死胡同，并且只有一条铁轨，如图3．1所示。
当地的传统是从A方向到达的每列火车都继续沿B方向行驶，需要以某种方式进行车厢重组。假设从A方向到达的火车有n(n≤1000)个车厢，按照递增的顺序1，2，…，n编号。火车站负责人必须知道是否可以通过重组得到B方向的车厢序列。


图3．1铁轨问题示意图

输入格式： 输入由若干块组成。除了最后一个块之外，每个块描述了一个列车以及可能更多的车厢重组要求。在每个块的第一行中为上述的整数n，下一行是1，2，…，n的车厢重组序列。每个块的最后一行仅包含0。最后一个块只包含一行0。
输出格式： 输出包含与输入中具有车厢重组序列对应的行。如果可以得到车厢对应的重组序列，输出一行“Yes”，否则输出一行“No”。此外，在输入的每个块之后有一个空行。
输入样例： 

5

1 2 3 4 5

5 4 1 2 3

0

6


6 5 4 3 2 1

0

0

输出样例： 

Yes

No



Yes


第3章栈和队列
数据结构在线编程实训（C++语言）（全程视频讲解版）
解： 先考虑这样的情况，假设a和b数组中均含n个整数(n为大于1的正整数)，都是1~n的某个排列，现在要判断b是否为以a作为输入序列的一个合法出栈序列，即a序列经过一个栈是否得到b的出栈序列。
求解思路是，建立一个整型栈st，用i、j分别遍历a、b序列(初始值均为0)，在a序列没有遍历完时循环： 
① 将a［i］进栈，i++。
② 栈不空并且栈顶元素与b［j］相同时循环： 出栈元素e，j++。
在上述过程结束后，如果栈空返回true，表示b序列是a序列的出栈序列，否则返回false，表示b序列不是a序列的出栈序列。
例如，a=［1，2，3，4，5］，b=［3，2，1，5，4］，i=0，j=0，判断过程如下： 
① 初始时栈空，a［0］进栈(i=1)。b［0］≠栈顶元素，a［1］进栈(i=2)。b［0］≠栈顶元素，a［2］进栈(i=3)，如图3．2(a)所示。
② b［0］=栈顶元素，出栈一次，j增1(j=1)。b［1］=栈顶元素，出栈一次，j增1(j=2)。b［2］=栈顶元素，出栈一次，j增1(j=3)，如图3．2(b)所示。
③ 此时栈空，a［3］进栈(i=1)。b［3］≠栈顶元素，a［3］进栈(i=4)。b［3］≠栈顶元素，a［4］进栈(i=5，a序列遍历完毕)，如图3．2(c)所示。
④ b［3］=栈顶元素，出栈一次，j增1(j=4)。b［4］=栈顶元素，出栈一次，j增1(j=5)，如图3．2(d)所示。


图3．2判断b=［3，2，1，5，4］是否为出栈序列的过程


此时a序列遍历完毕，栈空返回true，表示b序列是a序列的出栈序列。
又例如，a=［1，2，3］，b=［3，1，2］，i=0，j=0，判断过程如下： 
① 初始时栈空，a［0］进栈(i=1)。b［0］≠栈顶元素，a［1］进栈(i=2)。b［0］≠栈顶元素，a［2］进栈(i=3，a序列遍历完毕)，如图3．3(a)所示。
② b［0］=栈顶元素，出栈一次，j增1(j=1)。b［1］≠栈顶元素，如图3．3(b)所示。
此时a序列遍历完毕，栈不空返回false，表示b序列不是a序列的出栈序列。


图3．3判断b=［3，1，2］是否为出栈序列的过程


再回到本题，实际上就是有多个测试用例，每个测试用例给一个正整数n和若干由1~n排列构成的b序列，判断1，2，…，n作为输入序列经过一个栈是否得到b序列。采用上述思路，直接将a数组用1，2，…，n替代，对应的完整程序如下： 

#include <iostream>

#include <stack>

using namespace std;

const int MAXN=1005;

bool isSerial(int b［］,int n)//判断b序列是否为1~n的出栈序列

{stack<int> st;   //建立一个栈对象 

int i=1,j=0;

while (i<=n)//输入序列没有遍历完

{st.push(i);

i++;

while (!st.empty() && st.top()==b［j］)

{st.pop();   //b［j］与栈顶匹配时出栈

j++;

}

}

return st.empty();   //栈空返回true，否则返回false

}

int main()

{int n;

int b［MAXN］;

while (cin >> n && n)//n=0时输入结束 

{while(true)//处理一个块 

{cin >> b［0］;

if (b［0］==0)//一个块结束 

{cout << endl;   //输出一个空行

break;

}

else

{for (int i=1;i<n;i++)//输入一个b序列的其他n-1个整数 

cin >> b［i］;

}

if (isSerial(b,n))

cout << "Yes" << endl;

else

cout << "No" << endl;

}

}

}

上述程序是AC代码，运行时间为176ms，运行占用的空间为391KB，编译语言为C++。
【实战3．2】POJ1208——箱子操作


视频讲解


问题描述参见本书第2章中的实战2．4，这里改为用栈求解。
解： 如图3．4(a)所示为n=4的某个状态表示，box［1］表示位置1的箱子链，实际上箱子链应该是箱子栈，上方是栈顶，当执行move 0 onto 2命令时，将箱子0和2上面的箱子(只有箱子3)放回初始位置，并将0放到2上，结果如图3．4(b)所示。
为此将box数组元素由链表改为栈，即box［i］表示位置i的箱子栈，所有操作执行完毕，借助vector<int>向量输出每个栈中从栈底到栈顶的所有元素即可。


图3．4执行move 0 onto 2操作命令


对应的程序如下： 

#include <iostream>

#include <vector>

#include <string>

#include <stack>

using namespace std;

const int MAXN=30;

stack<int> box［MAXN］;   //box［i］表示位置i的箱子栈

stack<int>tmp;   //临时栈

int pos［MAXN］;   //pos［i］表示编号为i的箱子的位置

void restore(int x)//将x上面的箱子放回初始位置

{int i=pos［x］;   //找x所在的位置i

while(box［i］.top()!=x)//在位置i的箱子栈中从尾部找到x为止

{int t=box［i］.top();   //取出箱子t

box［t］.push(t);   //将箱子t添加到位置t的箱子栈中

pos［t］=t;   //设置箱子t的位置为t

box［i］.pop();   //将箱子t从位置i的箱子栈中删除

}

}

void over(int x,int y)//将箱子x及其上方的箱子放到箱子y所在的箱子栈中

{int i=pos［x］;   //找x所在的位置i

int j=pos［y］;   //找y所在的位置j

while(box［i］.top()!=x)//在位置i的箱子栈中从尾部找到x为止

{tmp.push(box［i］.top());   //将箱子x上方的箱子退出并存放在临时tmp中

box［i］.pop();

}

box［j］.push(box［i］.top());   //将箱子x放在位置j的箱子栈中

pos［x］=j;   //置箱子x的位置为j

box［i］.pop();   //从位置i的箱子栈中删除x

while(!tmp.empty())//将tmp中的箱子放在x的上方

{box［j］.push(tmp.top());

pos［tmp.top()］=j;

tmp.pop();

}

}

int main()

{int n;

cin >> n;

for(int i=0;i<n;i++)//将箱子i放在位置i

{box［i］.push(i);

pos［i］=i;

}

string str1,str2;

int a,b;

while(cin >> str1 && str1!="quit" )

{cin >> a >> str2 >> b;

if(str1=="move" && str2=="onto")//move a onto b

{restore(a);

restore(b);

over(a,b);

}

else if(str1=="move" && str2=="over")//move a over b

{restore(a);

over(a,b);

}

else if(str1=="pile" && str2=="onto")//pile a onto b

{restore(b);

over(a,b);

}

else//pile a over b

over(a,b);

}

vector<int> ans;

vector<int>::reverse_iterator rit;

for(int i=0;i<n;i++)//输出结果

{cout << i << ':';

ans.clear();

while(!box［i］.empty())//将box［i］栈元素出栈并存放在ans中

{ans.push_back(box［i］.top());

box［i］.pop();

}

for (rit=ans.rbegin();rit!=ans.rend();rit++)

cout << " " << *rit;   //反向输出ans构成该箱子栈的结果

cout << endl;

}

return 0;

}

上述程序是AC代码，运行时间为16ms，运行占用的空间为220KB，编译语言为C++。从中看出，由于vector和list容器都提供了快捷的尾端操作push_back/pop_back，用它们模拟stack十分方便，实际上实战2．4就是用list容器模拟栈来求解的。
【实战3．3】LeetCode225——用队列实现栈


视频讲解


问题描述： 使用队列实现栈的下列操作。
void push(int x)： 元素x进栈。
int pop()： 删除并且返回栈顶元素。
int top()： 返回栈顶元素。
bool empty()： 返回栈是否为空。
解： 将一个队列作为栈的示意图如图3．5所示，以queue<int>容器qu为队列，模拟栈的操作如下。


图3．5将一个队列作为栈

void push(int x)： 元素x进栈和qu进队的操作一致，直接用qu．push(x)实现。
int pop()： 出栈的元素为an-1，将qu中的前n-1个元素出队并立刻进队，再出队列元素an-1并返回该元素。
int top()： 类似pop()，但第n个元素d仍然需要进队，返回d。
bool empty()： 返回队列qu是否为空。
对应的程序代码如下： 

class MyStack

{queue<int> qu;

public:

MyStack(){}//构造函数

void push(int x)//元素z进栈

{

qu.push(x);

}

int pop()//删除并且返回栈顶元素

{int m=qu.size()-1,d;

for(int i=0;i<m;i++)

{d=qu.front();

qu.pop();

qu.push(d);

}

d=qu.front();

qu.pop();

return d;

}

int top()//获取栈顶元素

{int n=qu.size(),d;

for(int i=0;i<n;i++)

{d=qu.front();

qu.pop();

qu.push(d);

}

return d;

}

bool empty()//返回栈是否空

{

return qu.empty();

}

};

上述程序是AC代码，运行时间为4ms，运行占用的空间为8．6MB，编译语言为C++。
【实战3．4】HDU1276——士兵队列训练问题


视频讲解


时间限制： 1000ms； 内存限制： 32768KB。
问题描述： 某部队进行新兵队列训练，将新兵从1开始按顺序依次编号，并排成一行横队。训练的规则如下： 从头开始按1~2报数，凡报到2的出列，剩下的向小序号方向靠拢； 再从头开始按1~3报数，凡报到3的出列，剩下的向小序号方向靠拢； 继续从头开始按1~2报数，…； 之后从头开始轮流按1~2报数、按1~3报数，直到剩下的人数不超过3个为止。
输入格式： 本题有多个测试数据组，第一行为组数n，接着为n行新兵人数，新兵人数不超过5000。
输出格式： 共有n行，分别对应输入的新兵人数，每行输出剩下的新兵的最初编号，编号之间有一个空格。
输入样例： 

2

20

40

输出样例： 

1 7 19

1 19 37

解法1： 本题实际上是约瑟夫问题的变形，与(n，m)约瑟夫问题相比，一方面m是可变的(这里轮流做m=2和m=3的报数)，另外每次报数都是从头开始。其求解思路与《教程》中的例3．13类似，这里用queue容器代替队列。对应的程序如下： 

#include <iostream>

#include <queue>

using namespace std;

void solve(int n)//求解算法

{queue<int> qu;

for (int i=1;i<=n;i++)//m个士兵排成一行

qu.push(i);

bool flag=true;   //是否做1~2报数

while (qu.size()>3)//剩余人数超过3时循环

{if (flag)//1~2报数

{int rest=qu.size();   //剩余人数

int half=rest/2;

for (int i=0;i<half;i++)//处理前面满两人的组

{qu.push(qu.front()); qu.pop(); 

qu.pop();   //每组中第2个人只出不进

}

if ((rest%2)!=0)//处理最后一人的组

{qu.push(qu.front());   //这些人都保留

qu.pop();

}

flag=false;

}

else//做1~3报数

{int rest=qu.size();   //剩余人数

int third=rest/3;

for (int i=0;i<third;i++)//处理前面满3人的组

{qu.push(qu.front()); qu.pop();

qu.push(qu.front()); qu.pop();

qu.pop();   //每组中第3个人只出不进

}

rest=rest%3;

while (rest--)//处理最后一或者两人的组

{qu.push(qu.front());

qu.pop();   //这些人都保留 

}

flag=true;

}

}

bool first=true;   //输出最后剩下的士兵

while (!qu.empty())

{if (first)

{printf("%d", qu.front());

first=false;

}

else

printf(" %d", qu.front());

qu.pop();

}

printf("＼n");

}

int main()

{int t,n;

scanf("%d",&t);   //输入测试用例的个数

while (t--)

{scanf("%d",&n);   //输入一行的人数n

solve(n);   //求解一个测试用例的问题

}

return 0;

}

上述程序是AC代码，运行时间为15ms，运行占用的空间为1840KB，编译语言为C++。
解法2： 直接采用链表模拟，这里采用list<int>链表容器lst存放一行的n个新兵(编号为1~n)，依次报数并删除出列的新兵，直到剩下的人数不超过3人为止，再输出lst中的所有新兵。
参考博客： https://www．cnblogs．com/randylo/p/12607874．html
对应的程序如下： 

#include <iostream>

#include <list>

using namespace std;

void solve(int n)//求解算法

{list<int> lst;

list<int>::iterator it;

for (int i=1;i<=n;i++)//m个士兵排成一行

lst.push_back(i);

int m=2;   //报数的人数

while (lst.size()>3)

{int i=1;

it=lst.begin();

while (it!=lst.end())

{if (!(i++%m))

it=lst.erase(it);   //删除之后返回下一个位置的指针

else

it++;

}

if (m==2) m=3;

else m=2;

}

it=lst.begin();   //输出最后剩下的士兵

while (it!=lst.end())

{if (it==lst.begin())

printf("%d",*it);

else

printf(" %d",*it);

it++;

}

printf("＼n");

}

int main()

{int t,n;

scanf("%d",&t);   //输入测试用例的个数

while (t--)

{scanf("%d",&n);   //输入一行的人数n

solve(n);   //求解一个测试用例的问题

}

return 0;

}

上述程序是AC代码，运行时间为15ms，运行占用的空间为1876KB，编译语言为C++。
【实战3．5】LeetCode84——柱状图中最大的矩形


视频讲解


问题描述： 给定n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1，求在该柱状图中能够勾勒出来的矩形的最大面积。例如，如图3．6(a)所示的柱状图，其中每个柱子的宽度为1，给定的高度heights［］={2,1,5,6,2,3}，求出的最大面积的矩形如图3．6(b)所示，其面积为10。要求设计相应的largestRectangleArea()函数： 

class Solution

{

public:

int largestRectangleArea(vector<int>& heights)

{…}

};



图3．6一个柱状图及其求解结果


解法1： 采用枚举法，对于heights［i．．j］(j≥i)的j-i+1个柱子，构成的矩形面积为(heights［i．．j］中的最小高度)×(j-i+1)。在所有这些矩形面积中比较求最大值。对应的程序如下： 

class Solution

{

public:

int largestRectangleArea(vector<int>& heights)

{if (heights.size()==0) return 0;   //处理两种特殊情况

if (heights.size()==1) return heights［0］;

int ans=0;   //存放最大矩形面积

for (int j=0; j<heights.size(); j++)//j从0到n-1遍历

{int minh=heights［j］;

for (int i=j; i>=0; i--)//i从0到j反向遍历

{if (heights［i］<minh)//求heights［i．．j］中的最小值minh

minh=heights［i］;

int s=(j-i+1)*minh;   //求每个heights［i．．j］的面积

if (ans<s) ans=s;   //比较求最大面积

}

}

return ans;

}

};

上述程序是AC代码，运行时间为1916ms，运行占用的空间为9．2MB，编译语言为C++。显然该解法是低效的。
解法2： 采用单调栈求解。设maxr(［i．．j］)表示heights［i．．j］中的最大矩形面积，假设heights［i．．j］中所有柱子的高度是递增的，采用上述解法需要通过枚举i、j来求最大的矩形面积，实际上可以利用所有柱子的宽度为1并且高度递增推出maxr(［i．．i］)<…<maxr(［i．．j-1］)<maxr(［i．．j］)。当heights［j+1］>heights［j］时一定有maxr(［i．．j］)<maxr(［i．．j+1］)，所以没有必要求前面的maxr(［i．．i］)、…、maxr(［i．．j-1］)、maxr(［i．．j］)，只有当heights［j+1］>heights［j］不成立时再求这些面积，从中比较求出最大矩形面积。这样减少了枚举i的次数，从而提高了效率。
为此用一个栈st来维护高度递增的柱子序列(即单调递增栈)，栈中存储这些柱子的下标(索引)而不是柱子的高度，每个柱子的下标仅进栈一次，从栈底到栈顶柱子的高度是递增的。用j从0开始遍历heights： 当栈空或者柱子j的高度大于或等于栈顶柱子的高度时，将j进栈并且执行j++，即维护栈中柱子高度的递增性，否则对栈中所有高度大于heights［j］的柱子求矩形面积S。计算过程是退栈柱子tmp，求该柱子到j-1位置为止构成的最大矩形面积，显然其高度是heights［tmp］，那么最大矩形的长度length呢？分为两种情况： 
①  退栈tmp后栈不空，st．top()为新栈顶柱子，求以柱子j-1结尾、以tmp为最小高度的矩形S的面积，按照单调栈的操作有两种情况，情况1是st．top()=tmp-1(即tmp柱子和栈顶st．top()柱子是相邻的，并且heights［st．top()］<heights［tmp］)，矩形S是由柱子tmp到柱子j-1构成的，其面积为heights［tmp］×(j-tmp)=heights［tmp］×(j-st．top()-1)； 情况2是st．top()<tmp-1(即柱子st．top()+1到柱子tmp-1的所有柱子在tmp出栈之前已经出栈，说明它们的高度都大于柱子tmp的高度，需要计入矩形S中)，矩形S是由柱子st．top()+1到柱子j-1构成的，其面积为heights［tmp］×(j-st．top()-1)。合并起来矩形S的面积area=heights［tmp］×(j-st．top()-1)，求宽度length=j-st．top()-1。
②  退栈后栈空，说明在所有heights［0．．j-1］中tmp柱子的高度最小，宽度length=j，其面积area=heights［tmp］×j。
对于每次求出的area，再求ans=max(ans,area)。当所有heights序列遍历完毕，需要对栈中的全部柱子求矩形面积，为了触发这个计算过程，先在heights末尾添加一个高度为0的虚柱子。
例如，题目中的样例在末尾添加0后为heights［］={2,1,5,6,2,3,0}，用ans存放最大矩形面积(初始为0)，求解过程如下： 
①  j=0，柱子0的高度为2，直接进栈，如图3．7(a)所示，栈中元素“2［0］”表示该柱子的下标为0，高度为2。
②  j=1，柱子1的高度为1，其高度小于栈顶柱子的高度，计算当前最大面积，出栈tmp=0，栈为空，说明柱子2是heights［0．．j-1］中高度最小的，长度length=j=1，求出面积area=heights［0］×length=2×1=2，则ans=2。再将j进栈，如图3．7(b)所示。
③  j=2，柱子2的高度为5，其高度大于栈顶柱子的高度，直接进栈。j=3，柱子3的高度为6，其高度大于栈顶柱子的高度，直接进栈，结果如图3．7(c)所示。
④  j=4，柱子4的高度为2，其高度小于栈顶柱子的高度，计算当前最大面积，出栈tmp=3，栈不空，说明新栈顶之后一直到j-1所有柱子中tmp柱子的高度最小，长度length=j-st．top()-1=4-2-1=1，求出面积area=heights［3］×length=6×1=6，则ans=6。柱子4的高度仍小于栈顶柱子的高度，再计算当前最大面积，出栈tmp=2，栈不空，计算长度length=j-st．top()-1=4-1-1=2，求出面积area=heights［2］×length=5×2=10，则ans=10。再将j进栈，如图3．7(d)所示。
⑤  j=5，柱子5的高度为3，其高度大于栈顶柱子的高度，直接进栈，如图3．7(e)所示。
⑥  j=6，柱子6的高度为0，其高度小于栈顶柱子的高度，计算当前最大面积，出栈tmp=5，栈不空，计算长度length=j-st．top()-1=6-4-1=1，求出面积area=heights［5］×length=3×1=3，ans=10。
柱子6的高度仍小于栈顶柱子的高度，再计算当前最大面积，出栈tmp=4，栈不空，说明新栈顶之后一直到j-1所有柱子中tmp柱子的高度最小，长度length=j-st．top()-1=6-1-1=4(主要此时是heights［2．．5］计算面积)，求出面积area=heights［4］×length=2×4=8，ans=10。
柱子6的高度仍小于栈顶柱子的高度，再计算当前最大面积，出栈tmp=1，栈空，计算长度length=j=6，求出面积area=heights［1］×length=1×6=6，ans=10。再将j进栈，如图3．7(f)所示。


图3．7{2,1,5,6,2,3,0}的求解过程


对应的程序如下： 

class Solution

{

public:

int largestRectangleArea(vector<int>& heights)

{if (heights.size()==0) return 0;   //处理两种特殊情况

if (heights.size()==1) return heights［0］;

heights.push_back(0);   //在末尾添加一个高度为0的虚柱子

int n=heights.size();

stack<int> st;

int ans=0;   //存放最大矩形面积，初始为0

for (int j=0;j<n;j++)

{if (st.empty() || heights［j］>heights［st.top()］)

st.push(j);   //栈空或高度是单调递增的,直接进栈 

else

{while (!st.empty() && heights［st.top()］>=heights［j］)

{int tmp=st.top(); st.pop();   //退栈tmp

int length;

if(st.empty())

length=j;

else

length=j-st.top()-1;

int area=heights［tmp］*length;   //求heights［st.top()+1．．j-1］的矩形面积 

ans=max(ans,area);   //维护ans为最大矩形面积

}

st.push(j);   //j进栈

}

}

return ans;

}

};

上述程序是AC代码，运行时间为12ms，运行占用的空间为15．5MB，编译语言为C++。
【实战3．6】POJ2823——滑动窗口


视频讲解


时间限制： 12000ms； 内存限制： 65536KB。
问题描述： 给出一个长度为n≤106的整数数组。有一个大小为k的滑动窗口，它从数组的最左边移动到最右边，用户只能在窗口中看到k个整数。每次滑动窗口向右移动一个位置。在如表3．1所示的例子中，该数组为{1,3,-1,-3,5,3,6,7}，k为3。


表3．1一个k=3的滑动窗口例子


窗口位置
最小值
最大值
［1 3 -1］ -3 5 3 6 7
-1
3
1 ［3 -1 -3］ 5 3 6 7
-3
3
1 3 ［-1 -3 5］ 3 6 7
-3
5
1 3 -1 ［-3 5 3］ 6 7
-3
5
1 3 -1 -3 ［5 3 6］ 7
3
6
1 3 -1 -3 5 ［3 6 7］
3
7

确定每个位置的滑动窗口中的最大值和最小值。
输入格式： 输入包含两行，第一行包含两个整数n和k，它们是数组和滑动窗口的长度，第二行有n个整数。
输出格式： 输出中有两行，第一行按从左到右的顺序给出每个位置的窗口中的最小值，第二行为对应的最大值。
输入样例： 

8 3

1 3-1 -3 5 3 6 7

输出样例： 

-1 -3 -3 -3 3 3

3 3 5 5 6 7

解： 设计两个单调队列，minqu为单调递增队列，用于维护序列的最小值(队头为最小元素)，maxqu为单调递减队列，用于维护序列的最大值(队头为最大元素)。队列中的每个元素记录对应的整数x和输入的编号i。
由于本题是求k区间内的最大值和最小值，以使用minqu求最小值序列为例，对于当前整数x，只关心它自己和它前面k-1个整数。i标记输入的整数x的编号，当i≤k-1(处理前面的k-1个整数)时不存在区间最小值，直接做进队处理： 
①  将队尾≥x的元素从队尾出队。
②  x从队尾进队。
当i≥k(处理第k个整数以及后面的整数)时存在区间最小值，此时除了做上述直接进队的处理外，还需要将队头下标超出k区间范围的元素出队，即将满足i-minqu．front()．i>=k的整数从队头出队，目的是保持队头元素为区间内的最小值，再置mina［i］=minqu．front()．x取队首元素。
求k区间内的最大值序列与上述过程类似，最后输出最小值序列mina和最大值序列maxa。对应的程序如下： 

#include <iostream>

#include <deque>

using namespace std;

const int MAXN=1000005;

struct Node//队列元素类型

{int x;   //元素值

int i;   //元素的编号

Node(int x1,int i1):x(x1),i(i1) {} //构造函数

};

deque<Node>minqu;   //单调递增队列

deque<Node>maxqu;   //单调递减队列

int mina［MAXN］;   //存放最小元素序列

int maxa［MAXN］;   //存放最大元素序列

int main()

{int n,k,x;

scanf("%d%d",&n,&k);

for (int i=1;i<=n;i++)//按编号输入整数

{scanf("%d", &x);   //输入编号为i的整数x

while (!minqu.empty() && minqu.back().x>=x)//维护minqu为单调递增队列

minqu.pop_back();   //队尾较大元素出队 

minqu.push_back(Node(x,i));   //x从队尾进队

if(i>=k)

{while (!minqu.empty() && i-minqu.front().i>=k)//把队头下标超出k区间范围

//的元素出队

minqu.pop_front();

mina［i］=minqu.front().x;   //取队首元素

}

while (!maxqu.empty() && maxqu.back().x <=x)//维护maxqu为单调递减队列

maxqu.pop_back();   //队尾较小元素出队 

maxqu.push_back(Node(x,i));   //x从队尾进队

if (i>=k)

{while (!maxqu.empty() && i-maxqu.front().i>=k)//把队头下标超出k区间范围的

//元素出队

maxqu.pop_front();

maxa［i］=maxqu.front().x;   //取队首元素

}

}

for (int i=k;i<=n;i++)//输出最小元素序列

if (i==k)

printf("%d",mina［i］);

else

printf(" %d",mina［i］);

printf("＼n");

for (int i=k;i<=n;i++)//输出最大元素序列

if (i==k)

printf("%d",maxa［i］);

else

printf(" %d",maxa［i］);

printf("＼n");

}

上述程序是AC代码，运行时间为9094ms，运行占用的空间为9088KB，编译语言为C++。
3．2在线编程题解析
3．2．1LeetCode150——逆波兰表达式求值



视频讲解


问题描述： 根据逆波兰表示法求表达式的值，有效的运算符包括+、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。假设给定的逆波兰表达式总是有效的，换句话说，表达式总会得出有效数值且不存在除数为0的情况。其中整数除法只保留整数部分。
示例1： 
输入： ［"2", "1", "+", "3", "*"］
输出： 9
解释： ((2+1)*3)=9
示例2： 
输入： ［"4", "13", "5", "/", "+"］
输出： 6
解释： (4+(13/5))=6
示例3： 
输入： ［"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"］
输出： 22
解释： 
((10*(6/((9+3)*-11)))+17)+5
=((10*(6/(12 *-11)))+17)+5
=((10*(6/-132))+17)+5
=((10*0)+17)+5
=(0+17)+5
=17+5
=22
设计求逆波兰表达式tokens的值： 

class Solution

{

public:

int evalRPN(vector<string>& tokens)

{…}

};

解： 利用《教程》第3章中3．1．7节求后缀表达式值的思路求解。设计一个运算数栈st，遍历逆波兰表达式tokens，当遇到运算符时出栈两个运算数a和b，做相应运算并将结果进栈，若遇到数字串转换为整数并进栈，tokens处理完毕返回栈顶整数。对应的程序如下： 

class Solution

{

public:

int evalRPN(vector<string>& tokens)

{int a, b;

stack<int> st;

for (int i=0;i<tokens.size();i++)

{string s=tokens［i］;

if (s=="+")

{a=st.top(); st.pop();   //出栈整数a

b=st.top(); st.pop();   //出栈整数b

st.push(b+a);   //执行b+a并将结果进栈

}

else if(s=="-")

{a=st.top(); st.pop();   //出栈整数a

b=st.top(); st.pop();   //出栈整数b

st.push(b-a);   //执行b-a并将结果进栈

}

else if(s=="*")

{a=st.top(); st.pop();   //出栈整数a

b=st.top(); st.pop();   //出栈整数b

st.push(b*a);   //执行b*a并将结果进栈

}

else if(s=="/")

{a=st.top(); st.pop();   //出栈整数a 

b=st.top(); st.pop();   //出栈整数b

st.push(b/a);   //执行b/a并将结果进栈

}

else//遇到数字串，转换为整数后进栈

st.push(stoi(s));

}

return st.top();

}

};

运行通过，执行用时为4ms，内存消耗为12．2MB，所用语言为C++。
3．2．2LeetCode622——设计循环队列


视频讲解


问题描述： 设计循环队列的实现。循环队列是一种线性数据结构，其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后，以形成一个循环，所以它也被称为“环形缓冲器”。循环队列的一个好处是用户可以利用这个队列之前用过的空间。在一个普通队列中，一旦一个队列满了就不能插入下一个元素，即使在队列前面仍有空间，但是在使用循环队列时可以使用这些空间去存储新的值。该实现应该支持如下操作。
① MyCircularQueue(k)： 构造器，设置队列长度为k。
② Front（）： 从队首获取元素。如果队列为空，返回-1。
③ Rear（）： 获取队尾元素。如果队列为空，返回-1。
④ enQueue(value)： 向循环队列中插入一个元素。如果成功插入，则返回真。
⑤ deQueue()： 从循环队列中删除一个元素。如果成功删除，则返回真。
⑥ isEmpty()： 检查循环队列是否为空。
⑦ isFull()： 检查循环队列是否已满。
例如： 

MyCircularQueue circularQueue = new MycircularQueue(3); //设置长度为3

circularQueue.enQueue(1); //返回true

circularQueue.enQueue(2); //返回true

circularQueue.enQueue(3); //返回true

circularQueue.enQueue(4);   //返回false，队列已满

circularQueue.Rear(); //返回3

circularQueue.isFull(); //返回true

circularQueue.deQueue(); //返回true

circularQueue.enQueue(4); //返回true

circularQueue.Rear(); //返回4

提示： 所有的值都在0~1000，操作数将在1~1000，不要使用内置的队列库。
解： 循环队列的原理参见《教程》第3章中的3．2．2节，为了简单，在这里循环队列中除了data数组、队头指针front和队尾指针rear外，增加了容量capacity和长度length数据成员，同样让front指向队头元素的前一个位置，rear指向队尾元素的位置。对应的程序如下： 

class MyCircularQueue

{

public:

int *data;   //存放队中元素

int front;   //队头指针

int rear;   //队尾指针

int capacity;   //容量

int length;   //长度

public:

MyCircularQueue(int k)//构造函数

{data=new int［k］;

capacity=k;

front=rear=0;

length=0;

}

~MyCircularQueue()//析构函数

{

delete ［］ data;

}

bool isEmpty()//判断是否为空队

{

return length==0;

}

bool isFull()//判断是否队满

{

return length==capacity;

}

bool enQueue(int value)//元素value进队

{if (isFull()) return false;

rear=(rear+1) % capacity;

data［rear］=value;

length++;

return true;

}

bool deQueue()//出队一个元素

{if (isEmpty()) return false;

front=(front+1) % capacity;

length--;

return true;

}

int Front()//返回队头元素

{if (isEmpty()) return -1;

int head=(front+1) % capacity; 

return data［head］;

}

int Rear()//返回队尾元素

{if (isEmpty()) return -1;

return data［rear］;

}

};

运行通过，执行用时为28ms，内存消耗为17．1MB，所用语言为C++。
3．2．3HDU5818——合并栈操作


视频讲解


时间限制： 4000ms； 内存限制： 65536KB。
问题描述： 栈是一种后进先出的数据结构，可合并栈是支持“merge”操作的栈。3种操作的说明如下。
①  push A x： 将x插入栈A中。
②  pop A： 删除栈A的顶部元素。
③  merge A B： 合并栈A和B。

其中，“merge A B”操作后栈A包含A和B之前的所有元素，B变为空，新栈中的元素根据先前的进栈时间重新排列，就像在一个栈中重复“push”操作一样。给定两个可合并栈A和B，请执行上述操作。
输入格式： 有多个测试用例，测试用例的第一行包含一个整数n(0<n≤105)表示操作个数，接下来的n行每行包含一条指令push、pop或merge，栈元素是32位整数。A和B最初都是空的，并且保证不会对空栈执行pop操作。以n=0表示输入结束。
输出格式： 对于每个测试用例，先输出一行“Case #t:”，其中t是测试用例编号(从1开始)，对于每个“pop”操作，在一行中输出对应的出栈元素。
输入样例： 

4

push A 1

push A 2

pop A

pop A

9

push A 0

push A 1

push B 3

pop A

push A 2

merge A B

pop A

pop A

pop A

9

push A 0

push A 1

push B 3

pop A

push A 2

merge B A

pop B

pop B

pop B

0

输出样例： 

Case #1:

2

1

Case #2:

1

2

3

0

Case #3:

1

2

3

0

解法1： 本题表面上是栈操作，由于“merge”操作产生新栈，其中元素是根据先前的进栈时间重新排列的，所以每个栈元素增加一个时间戳timeid表示进栈时间，这样的栈可以看成按timeid越大越优先出栈的优先队列(体现后进先出的特性)。这样设计3个优先队列，A和B为题目中的栈，C为公共栈，存放合并后的结果。栈元素采用STL内置pair结构体，两个成员分别为timeid和进栈元素，默认的operator按timeid越大越优先。
①  push A/B x： 将x插入A/B优先队列(具有栈特性)。
②  pop A/B： 先从A/B中去找，如果A/B为空，则说明存放在公共栈C中了(题目保证不会对空栈pop)。
③  merge A B： 把当前A和B全部清空并放到公共栈C中即可。
对应的程序如下： 

#include <iostream>

#include <queue>

using namespace std;

typedef pair<int,int> PA;

priority_queue<PA> A,B,C;

int main()

{int n,t=1,x;

PA e;

char com［10］,g;   //com存放命令

while(scanf("%d", &n) != EOF && n)

{printf("Case #%d:＼n", t++);

while(!A.empty()) A.pop();   //初始化3个优先队列

while(!B.empty()) B.pop();

while(!C.empty()) C.pop();

int timeid=0;   //表示时间戳

while(n--)

{scanf("%s %c",com,&g);

if(com［1］=='u')//push A x命令

{scanf("%d",&x);

if(g=='A')

A.push(make_pair(timeid++,x));

else

B.push(make_pair(timeid++,x));

}

else if(com［1］=='o')//pop A

{if(g=='A')

{if(!A.empty())//A不空时从A出栈元素

{e=A.top(); A.pop();

printf("%d＼n", e.second);

}

else//A空时从公共栈C出栈元素

{e=C.top(); C.pop();

printf("%d＼n", e.second);

}

}

else//B不空时从B出栈元素

{if(!B.empty())

{e=B.top(); B.pop();

printf("%d＼n", e.second);

}

else//B空时从公共栈C出栈元素

{e=C.top(); C.pop();

printf("%d＼n", e.second);

}

}

}

else//merge A B

{char tmp［10］;

gets(tmp);   //忽略B参数，将A和B中的所有元素合并到C中

while(!A.empty())

{e=A.top(); A.pop();

C.push(e);

}

while(!B.empty())

{e=B.top(); B.pop();

C.push(e);

}

}

}

}

return 0;

}

运行通过，执行用时为951ms，内存消耗为2632KB，所用语言为C++。
解法2： 同样设置3个栈，A和B为题目中的栈，C为公共栈，存放合并后的结果。每个栈采用数组表示，例如A［0．．lena-1］存放栈A中的元素(长度为lena)，A［0］为栈底，A［lena-1］为栈顶。由于元素进栈是按时间戳有序的，所以每个栈元素包含元素值x和时间戳timeid数据成员，每个栈从栈底到栈顶如A［0．．lena-1］按timeid递增有序，在栈合并操作中采用二路归并将A［0．．lena-1］和B［0．．lenb-1］合并到C中(如果之前C非空，C［0．．lenc-1］一定有序，并且它们的时间戳均早于A和B中所有元素的时间戳)。对应的程序如下： 

#include <iostream>

using namespace std;

const int MAXN=100005;

struct Node//栈元素类型

{int x;   //元素值

int timeid;   //时间戳

Node() {}//构造函数

Node(int x1,int t1):x(x1),timeid(t1) {}//重载构造函数

};

Node A［MAXN］,B［MAXN］,C［MAXN］;   //全局变量： 3个栈

int lena,lenb,lenc;   //全局变量： 3个栈的长度

int main()

{int n,t=1,x;

char com［10］,g;   //com存放命令

while(scanf("%d", &n) != EOF && n)

{printf("Case #%d:＼n", t++);

lena=lenb=lenc=0;   //初始化3个栈 

int timeid=0;   //表示时间戳

while(n--)

{scanf("%s %c",com,&g);

if(com［1］=='u')//push A x命令

{scanf("%d",&x);

if(g=='A')

A［lena++］=Node(x,timeid++);

else

B［lenb++］=Node(x,timeid++);

}

else if(com［1］=='o')//pop A

{if(g=='A')

{if(lena!=0)//A不空时从A出栈元素

{lena--;

printf("%d＼n", A［lena］.x);

}

else//A空时从公共栈C出栈元素

{lenc--;

printf("%d＼n", C［lenc］.x);

}

}

else

{if(lenb!=0)//B不空时从B出栈元素

{lenb--;

printf("%d＼n", B［lenb］.x);

}

else//B空时从公共栈C出栈元素

{lenc--;

printf("%d＼n", C［lenc］.x);

}

}

}

else//merge A B

{char tmp［10］;

gets(tmp);   //忽略B参数，将A和B队列中的所有元素合并到C中 

int i=0,j=0;

while (i<lena && j<lenb)//按timeid二路归并 

{if (A［i］.timeid<B［j］.timeid)//归并timeid较小的A中元素

{C［lenc］=Node(A［i］.x,A［i］.timeid);

i++; lenc++; 

}

else//归并timeid较小的B中元素

{C［lenc］=Node(B［j］.x,B［j］.timeid);

j++; lenc++; 

}

}

while (i<lena)//归并A中的剩余元素

{C［lenc］=Node(A［i］.x,A［i］.timeid);

i++; lenc++; 

}

while (j<lenb)//归并B中的剩余元素

{C［lenc］=Node(B［j］.x,B［j］.timeid);

j++; lenc++; 

}

lena=lenb=0;   //A、B清空

}

}

}

return 0;

}

运行通过，执行用时为858ms，内存消耗为2140KB，所用语言为C++。从中看出解法2的时空性能稍好于解法1。
3．2．4HDU6215——暴力排序


视频讲解


问题描述参见本书第2章中的2．2．7节，这里采用队列求解。
参考博客： https://www．cnblogs．com/sbfhy/p/7576974．html
解： 直接用queue<int>类型的队列qu替代list<int>类型的lst。对应的程序如下： 

#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

#define MAXN 200005

struct DNode//静态双链表结点类型

{int val;   //存放整数

int prior;   //前驱位置

int next;   //后继位置

} a［MAXN］;   //a数组作为静态双链表

int n,m;

bool vis［MAXN］;   //表示元素是否已删除

int main()

{int t;

scanf("%d",&t);

while (t--)

{scanf("%d",&n);

memset(vis,false,sizeof(vis));

queue<int > qu;   //定义一个队列

vis［0］=vis［n+1］=true;

a［0］.val=0; a［0］.next=1;   //a［0］为头结点

a［n+1］.val=INT_MAX;

for (int i=1;i<=n;i++)//建立双链表

{scanf("%d",&a［i］.val);

a［i］.next=i+1;

a［i］.prior=i-1;

}

for (int i=1;i<=n;i++)//将a［i-1］<=a［i］且a［i］>a［i+1］的无序元素进队

if(a［i-1］.val<=a［i］.val && a［i］.val>a［i+1］.val)

qu.push(i); 

m=n;

while(!qu.empty())//处理无序元素

{int u=qu.front();   //出队元素

qu.pop();

if (vis［u］)//a［u］已删除时跳过

continue;

if (a［u］.val<=a［a［u］.next］.val)//a［u］正序时跳过

continue;

vis［u］=true;   //a［u］反序时标记qu中的a［u］被删除

m--;

int pos;

for (pos=a［u］.next;pos<=n;pos=a［pos］.next)//依次处理a［u］后面的元素

{if(a［a［pos］.prior］.val<=a［pos］.val)//正序时退出循环

break;

vis［pos］=true;   //反序时标记qu中的a［pos］被删除

m--;

}

a［a［u］.prior］.next=pos;   //链表操作:删除a［u］到a［pos］之前的所有结点

a［pos］.prior=a［u］.prior;

qu.push(a［u］.prior);   //将a［u］.prior进队

}

printf("%d＼n",m);   //输出结果

for(int i=a［0］.next;i<=n;i=a［i］.next)

printf("%d ",a［i］.val);

printf("＼n");

}

return 0;

}

上述程序是AC代码，运行时间为327ms，占用的空间为3120KB，编译语言为C++。
3．2．5HDU4699——编辑器


视频讲解


问题描述参见本书第2章中的2．2．8节，这里采用栈求解。
参考博客： https://www．cnblogs．com/ZhenghangHu/p/9759435．html
解： 设计两个栈，prest栈存放当前光标的前面部分元素，postst存放当前光标的后面部分元素，其他与2．2．8节的思路相同。对应的程序如下： 

#include <iostream>

#include <stack>

#include <algorithm>

using namespace std;

#define MAXN 1000010

int presum［MAXN］;   //presum［pos］存放pos位置的前缀和

int maxpresum［MAXN］;   //maxpresum［pos］存放pos位置的最大前缀和

stack<int>prest;   //存放当前光标之前的序列

stack<int>postst;   //存放当前光标之后的序列

int main()

{int n;

while (~scanf("%d",&n))

{while(!prest.empty())//清空prest栈

prest.pop();

while(!postst.empty())//清空postst栈

postst.pop(); 

int pos=0;   //当前位置

int len=0;

maxpresum［0］=-INT_MAX;

presum［0］=0;

for(int i=1;i<=n;i++)//处理n个指令

{char op［5］;

scanf("%s",op);

if (op［0］=='I')//I x指令

{int x;

scanf("%d",&x);

prest.push(x);   //把x进prest栈

pos++;

presum［pos］=presum［pos-1］+x;   //求pos位置的前缀和

maxpresum［pos］=max(maxpresum［pos-1］,presum［pos］);   //求pos位置的最大前缀和

}

else if (op［0］=='D')//D指令

{prest.pop();

pos--;

}

else if (op［0］=='L')//L指令

{if (prest.empty()) continue;

pos--;

int tmp=prest.top();

prest.pop();

postst.push(tmp);

}

else if (op［0］=='R')//R指令

{if (postst.empty()) continue;

pos++;

int e=postst.top();

postst.pop();

prest.push(e);

presum［pos］=presum［pos-1］+prest.top();

maxpresum［pos］=max(maxpresum［pos-1］,presum［pos］); 

}

else if (op［0］=='Q')//Q k指令

{int k;

scanf("%d",&k);

printf("%d＼n",maxpresum［k］);

}

}

}

return 0;

}

上述程序是AC代码，运行时间为1232ms，占用的空间为15172KB，编译语言为C++。
3．2．6HDU6375——度度熊学队列


视频讲解


时间限制： 1500ms； 内存限制： 131072KB。
问题描述： 度度熊正在学习双端队列，它对双端队列的翻转和合并产生了很大的兴趣。初始时有N个空的双端队列(编号为1~N)，用户要支持度度熊的Q次操作。
①  1 u w val： 在编号为u的队列中加入一个权值为val的元素(w=0表示加在最前面，w=1表示加在最后面)。
②  2 u w： 询问编号为u的队列中的某个元素并删除它(w=0表示询问并操作最前面的元素，w=1表示询问并操作最后面的元素)。
③  3 u v w： 把编号为v的队列“接在”编号为u的队列的最后面。w=0表示顺序接(队列v的开头和队列u的结尾连在一起，队列v的结尾作为新队列的结尾)，w=1表示逆序接(先将队列v翻转，再顺序接在队列u的后面)。该操作完成后，队列v被清空。
输入格式： 有多组测试用例，对于每组测试用例，第一行读入两个数N和Q。接下来有Q行，每行3~4个数，意义如上。规定N≤150000，Q≤400000，1≤u，v≤N，0≤w≤1，1≤val≤100000，所有数据的和不超过500000。
输出格式： 对于每个测试用例的每一个操作②，输出一行表示答案。注意，如果操作②的队列是空的，就输出-1且不执行删除操作。
输入样例： 

2 10

1 1 1 23

1 1 0 233

2 1 1

1 2 1 2333

1 2 1 23333

3 1 2 1

2 2 0

2 1 1

2 1 0

2 1 1

输出样例： 

23

-1

2333

233

23333

参考博客： https://blog．csdn．net/weixin_30274627/article/details/99221872
解： 直接用双端队列deque<int>容器数组dqu来模拟，根据输入的指令编号x执行要求的操作。对应的程序如下： 

#include <deque>

#include <iostream>

using namespace std;

#define MAXN 150010

deque<int>dqu［MAXN］;

int main()

{int N,Q;

while(~scanf("%d %d",&N,&Q))

{for(int i=0;i<=N;i++) 

dqu［i］.clear();

int x,u,v,w,val;

for(int i=0;i<Q;i++)//处理Q条指令

{scanf("%d",&x);

if(x==1)//1 u w val

{scanf("%d %d %d",&u,&w,&val);

if(w==0)//加在最前面

dqu［u］.push_front(val);

else if(w==1)//在最后面

dqu［u］.push_back(val);

}

else if(x==2)//2 u w

{scanf("%d %d",&u,&w);

if(dqu［u］.empty())

{cout << -1 << endl;

continue;

}

if(w==0)//询问并操作del最前面的元素，询问要求输出

{cout << dqu［u］.front() << endl;

dqu［u］.pop_front();

}

else if(w==1)//最后面

{cout << dqu［u］.back() << endl;

dqu［u］.pop_back();

}

}

else if(x==3)//3 u v w,该操作完成后队列v被清空

{scanf("%d %d %d",&u,&v,&w);

if(w==0)//顺序接

{while(!dqu［v］.empty())

{dqu［u］.push_back(dqu［v］.front());

dqu［v］.pop_front();

}

}

else if(w==1)//逆序接

{while(!dqu［v］.empty())

{dqu［u］.push_back(dqu［v］.back());

dqu［v］.pop_back();

}

}

}

}

}

return 0;

}

上述程序是AC代码，运行时间为936ms，占用的空间为25380KB，编译语言为C++。
3．2．7HDU4393——扔钉子


视频讲解


时间限制： 2000ms； 内存限制： 32768KB。
问题描述： 年度学校自行车比赛开始了，ZL是这所学校的学生，他太无聊了，因为他不能骑自行车！因此他决定干预比赛，他通过以前的比赛视频获得了选手的信息，一个选手第一秒可以跑F米，然后每秒跑S米。每个选手有一条直线跑道，ZL每秒向跑的最远的运动员的跑道扔一个钉子，在自行车胎爆了之后，该选手将被淘汰。如果有多个选手是NO．1，则他总是选择ID最小的选手扔钉子。
输入格式： 在第一行中有一个整数T(T≤20)，表示测试用例的数量。每个测试用例的第一行包含一个整数n(1≤n≤50000)，表示选手的人数，接着是n行，每行包含第i个选手的两个整数Fi(0≤Fi≤500)、Si(0<Si≤100)，表示该选手第一秒可以跑Fi米，然后每秒跑Si米，i是玩家从1开始的ID。
输出格式： 对于每个测试用例，第一行的输出均为“Case #c：”，c是测试用例的编号(从1开始)。第二行输出n个数字，以空格分隔，第i个数字是选手的ID，该选手将在第i秒结束时被淘汰。
输入样例： 

2

3

100 1

100 2

3 100

5

1 1

2 2

3 3

4 1

3 4

输出样例： 

Case #1:

1 3 2

Case #2:

4 5 3 2 1

参考博客： https://blog．csdn．net/rssj_chlh/article/details/8040023
解： 题目大意是给出n个人，每个人有两个速度，第一个是第一秒的速度，第二个是第一秒以后的平均速度。找到每一秒输出跑的路程最长的一个人，然后淘汰他，直到所有人输出完毕为止。如果路程相同就输出ID最小的那一个。
采用优先队列，每次出队一个最远选手即可。由于选手人数n可达50000，如果建立一个优先队列会出现超时，为此按选手的平均速度划分，由于选手的平均速度最大为100，这样建立105个优先队列，用qu数组表示，每次遍历所有队列，通过比较找到路径长度最长的选手pid出队。对应的程序如下： 

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

struct QNode

{int id;   //选手ID

int len;   //选手跑了路径长度

bool operator < (const QNode & s)const

{if (len==s.len)//路径长度相同，ID越小越优先

return id>s.id;

else//路径长度不同，其值越大越优先

return len<s.len;

}

};

priority_queue<QNode> qu［105］;

int main()

{int t;

scanf("%d",&t);

int cas=1;

while (t--)

{int n;

scanf("%d",&n);

cout << "Case #" << cas++ << ":" << endl;

for(int i=0;i<n;i++)//处理n个选手

{int f,s;

QNode p;

cin >> f >> s;   //输入f和s

p.len=f;

p.id=i+1;

qu［s］.push(p);   //所有选手按p速度划分

}

for(int i=0;i<n;i++)//扔n次钉子(每秒一次)

{int pos,pid;

int maxs=-1;   //最长的长度 

for(int j=1;j<101;j++)//遍历每个优先队列 

{if (!qu［j］.empty())

{QNode p=qu［j］.top();

if (p.len+j*i>maxs || (p.len+j*i==maxs && p.id<pid))

{pos=j;   //记录是哪个优先队列

pid=p.id;   //记录选手的ID

maxs=p.len+j*i;   //记录其连接长度

}

}

}

if (i!=n-1)

cout << pid << " ";

else

cout << pid;

qu［pos］.pop();   //淘汰的选手pid出队

}

cout << endl;

}

}

上述程序是AC代码，运行时间为920ms，占用的空间为2996KB，编译语言为C++。
3．2．8POJ3032——纸牌戏法


视频讲解


时间限制： 1000ms； 内存限制： 65536KB。
问题描述： 魔术师随机抽取一小叠纸牌，将其面朝下握住，然后执行以下步骤。
①  第1步： 将顶部的一张纸牌移到底部，新的顶部纸牌面朝上放在桌子上，该纸牌是黑桃1(A)。
②  第2步： 做两次移动，每次将顶部的一张纸牌移到底部，两次做完后将新的顶部纸牌面朝上放在桌子上，该纸牌是黑桃2。
③  第3步： 做3次移动，每次将顶部的一张纸牌移到底部，3次做完后将新的顶部纸牌面朝上放在桌子上，该纸牌是黑桃3。
④  以此类推，直到第n步做n次移动后新的顶部纸牌面朝上放在桌子上，该纸牌是黑桃n。
如果魔术师知道如何事先排列纸牌，则此技巧非常有用。编写程序在给定纸牌数量n(1≤n≤13)的情况下确定纸牌的初始顺序。
输入格式： 输入的第一行是一个正整数，表示测试用例数。每个测试用例由包含整数n的一行组成。
输出格式： 对于每个测试用例，输出一行为1~n的某个排列，以空格分隔，第一个整数为顶部纸牌的数字，以此类推。
输入样例： 

2

4

5

输出样例： 

2 1 4 3

3 1 4 5 2

解： 例如，当n=4时，求解结果序列是2143，魔术师的操作步骤如下。
①  第1步，将2放到队列末端变成1432，拿走1，剩下432。
②  第2步，将4、3分别放到底部末端，变成243，拿走2，剩下43。
③  第3步，把4放到末端，把3放到末端，再把4放到末端，变成34，拿走3，剩下4。
④  第4步，只有4，做4次，拿走4。
用队列模拟，按与上述相反的步骤操作，因为魔术师操作n步拿走的纸牌依次是1~n，所以按n~1的顺序进队，整个模拟过程如下： 
①  4进队。
②  3进队，出、进队做3遍，即4出队/4进队，3出队/3进队，4出队/4进队。
③  2进队，出、进队做2遍，即3出队/3进队，4出队/4进队。
④  1进队，出、进队做1遍，即2出队/2进队。
此时从队头到队尾是3412，反向便是求解结果2143。用queue<int>容器qu作为队列，对应的程序如下： 

#include <iostream>

#include <queue>

using namespace std;

const int MAXN=15;   //最大n 

queue<int>qu;

int ans［MAXN］;   //存放结果 

int main()

{int t,n,d;

scanf("%d",&t);   //测试用例的个数

while(t--)

{while (!qu.empty())

qu.pop();   //队列清空

scanf("%d",&n);

qu.push(n);

for(int i=n-1;i>=1;i--)

{qu.push(i);

for(int j=1;j<=i;j++)

{d=qu.front();

qu.pop();

qu.push(d);

}

}

for(int i=0;i<n;i++)//按出队顺序放在ans［1．．n］中

{ans［n-i］=qu.front();

qu.pop();

}

for(int i=1;i<n;i++)//输出结果ans

printf("%d ",ans［i］);

printf("%d＼n",ans［n］);

}

return 0;

}

上述程序是AC代码，运行时间为16ms，运行占用的空间为128KB，编译语言为C++。

3．2．9POJ2259——团队队列


视频讲解


时间限制： 2000ms； 内存限制： 65536KB。
问题描述： 在团队队列中每个成员都属于一个团队，如果一个成员进入队列，他首先从头到尾搜索队列，以检查他的一些队友(同一队的成员)是否已经在队列中，如果是，他会进入到该团队的后面； 如果不是，他会从尾部进入队列并成为新的最后一个成员。成员出队是按常规队列操作，按照出现在队列中的顺序从头到尾进行处理。请编写一个模拟这样的团队队列的程序。
输入格式： 包含一个或多个测试用例，每个测试用例都以团队个数t开始(1≤t≤1000)，然后是团队描述，每个描述包含属于团队的成员个数和成员编号列表，成员编号为0~999999的整数，一个团队最多可以包含1000个成员。然后是一系列命令，有以下3种不同的命令。
①  ENQUEUE p： 成员p进入队列。
②  DEQUEUE： 队列中的第一个成员出来并将其从队列中删除。
③  STOP： 当前测试用例结束。
输入以t=0结束。
输出格式： 对于每个测试用例，首先输出一行“Scenario #cas”，其中cas是测试用例的编号，然后对于每个DEQUEUE命令，以单独一行输出出队的成员。在每个测试用例之后输出一个空白行，即使是在最后一行之后。
输入样例： 

2

3 101 102 103

3 201 202 203

ENQUEUE 101

ENQUEUE 201

ENQUEUE 102

ENQUEUE 202

ENQUEUE 103

ENQUEUE 203

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

STOP

2

5 259001 259002 259003 259004 259005

6 260001 260002 260003 260004 260005 260006

ENQUEUE 259001

ENQUEUE 260001

ENQUEUE 259002

ENQUEUE 259003

ENQUEUE 259004

ENQUEUE 259005

DEQUEUE

DEQUEUE

ENQUEUE 260002

ENQUEUE 260003

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

STOP

0

输出样例： 

Scenario #1

101

102

103

201

202

203



Scenario #2

259001

259002

259003

259004

259005

260001

解： 采用如图3．8所示的结构模拟，每个团队用一个队列表示，由于团队的编号是1~1000，所以用termqu［1001］数组表示，即termqu［k］表示编号为k的团队队列。另外设置一个总队列totalqu，其元素为团队队列的编号。当一个团队队列中有一个成员时将其团队编号进入总队列，如果一个团队队列的成员数为0，则从总队列中删除。所以每个团队termqu［k］包含对应的团队队列和是否出现在总队列中的标志vis。每个成员用成员编号表示，进队后有一个对应的团队队列，设置数组termno，termno［p］=k表示成员编号p的团队队列的编号为k。


图3．8团队队列的结构


先初始化上述结构，处理各个命令如下。
①  ENQUEUE p： 将成员p进入团队编号为termno［p］的队列(termqu［termno［p］］)，如果该团队队列在总队列中不存在，将termno［p］进入总队列totalqu并且设置其vis为true。
②  DEQUEUE： 总队列中的队头为totalqu．front()团队队列，出队其中的一个成员并且输出，如果该团队队列为空，则从总队列totalqu中出队并且设置其vis为false。
对应的程序如下： 

#include <iostream>

#include <queue>

#include <string>

#include <cstring>

using namespace std;

const int MAXN=1000000;   //最大成员编号

int termno［MAXN］;   //每个成员所属团队的编号

int n;

queue<int>totalqu;   //总队列

struct

{queue<int> qu;   //队列

bool vis;   //表示这个团队是否在总队列中

}termqu［1001］;   //每个团队队列

void solve(int cas) //求解算法

{cout << "Scenario #" << cas << endl;

string com;

while (cin >> com && com!="STOP")

{if (com=="ENQUEUE")//ENQUEUE p

{int p;

cin >> p;

termqu［termno［p］］.qu.push(p);   //成员p进入termqu［termno［p］］队列

if (!termqu［termno［p］］.vis)//若p是该团队的第一个成员

{totalqu.push(termno［p］);   //将该团队编号添加到总队列中

termqu［termno［p］］.vis=true;   //置该团队在总队列中

}

}

else if (com=="DEQUEUE")//DEQUEUE

{cout << termqu［totalqu.front()］.qu.front() << endl;

termqu［totalqu.front()］.qu.pop();   //总队列中的第一个团队出队

if (termqu［totalqu.front()］.qu.empty())//该团队为空的情况 

{termqu［totalqu.front()］.vis=false;

totalqu.pop();

}

}

else break;   //STOP

}

}

void init() //初始化

{memset(termno,0,sizeof(termno));   //成员所属团队清0

while(!totalqu.empty())//总队列清空

totalqu.pop();

for(int i=1;i<=n;i++)//每个团队队列清空

{while(!termqu［i］.qu.empty())

termqu［i］.qu.pop();

termqu［i］.vis=false;

}

}

int main()

{int cas=1;   //测试用例编号

int t,p;

while(cin >> n && n != 0)//输入n(团队个数)

{init();

for(int i=1;i<=n;i++)//输入n个团队

{scanf("%d",&t);   //输入团队人数t

for(int j=1;j<=t;j++)//输入t个成员

{scanf("%d",&p);

termno［p］=i;

}

}

solve(cas++);   //求解

cout << endl;

}

return 0;

}

上述程序是AC代码，运行时间为469ms，运行占用的空间为4544KB，编译语言为C++。
3．2．10POJ2559——最大矩形面积


视频讲解


时间限制： 1000ms； 内存限制： 65536KB。
问题描述： 与本书中的实战3．5求柱状图的最大矩形面积类似。
输入格式： 输入包含几个测试用例。每个测试用例描述一个直方图，并以整数n(1≤n≤100000)开头，表示它所组成的矩形个数，然后跟随n个整数，即h1，h2,…，hn(0≤hi≤1000000000)，这些整数表示从左到右顺序的直方图矩形的高度，每个矩形的宽度为1。以输入n为0结束。
输出格式： 对于每个测试用例输出一行，指定直方图中最大矩形的面积。
输入样例： 

7 2 1 4 5 1 3 3

4 1000 1000 1000 1000

0

输出样例： 

8

4000

解： 采用单调栈st，ans表示最大矩形面积(初始为0)，求解思路参见本书中实战3．5的解法2，这里有两点修改。
(1) 在所有柱子高度输入完毕后，再对单调栈中的所有柱子做一次计算，而不是通过添加0高度的柱子自动触发计算。
(2) 每个柱子都进栈一次、出栈一次，栈中的每个柱子除了高度h成员外还带一个len成员表示该柱子对应矩形的宽度，在进栈和出栈过程中累加当前柱子的宽度，在出栈中求对应矩形的面积，比较求出ans。
以输入柱子高度heights［］={2,1,5,6,2,3}为例： 
①  i=0，［2,1］进栈(［2,1］中的前者2为高度，后者1为该柱子当前对应矩形的宽度)。st=(［2,1］)。
②  i=1，出栈［2,1］，tmp=0，栈顶柱子对应的宽度=1+tmp=1(出栈时tmp表示当前柱子的后面宽度)，求出面积=2×1=2。置tmp=1，将［1,1+tmp］=［1,2］进栈(进栈时tmp表示当前柱子的前面宽度)。st=(［1,2］)。
③  i=2，［5,1］进栈，st=(［1,2］，［5,1］)。
④  i=3，［6,1］进栈，st=(［1,2］，［5,1］，［6,1］)。
⑤  i=4，出栈［6,1］，tmp=0，栈顶柱子对应的宽度=1+tmp=1，求出面积=6×1=6。置tmp=1，出栈［5,1］，栈顶柱子对应的宽度=1+tmp=2，求出面积=5×2=10。置tmp=2，将［2,1+tmp］=［2,3］进栈。st=(［1,2］，［2,3］)。
⑥  i=5，［3,1］进栈。st=(［1,2］，［2,3］，［3,1］)。
⑦  最后计算，tmp=0，出栈［3,1］，栈顶柱子对应的宽度=1+tmp=1，求出面积=3×1=3。置tmp=1，出栈［2,3］，栈顶柱子对应的宽度=3+tmp=4，求出面积=2×4=8。置tmp=4，出栈［1,2］，栈顶柱子对应的宽度=2+tmp=6，求出面积=1×6=6。栈空结束。
得到最大面积=10。对应的程序如下： 

#include <iostream>

#include <stack>

using namespace std;

struct Node//栈元素类型

{long long h;   //柱子的高度

long long len;   //当前柱子高度的矩形宽度

};

stack<Node>st;

int main()

{long long tmp,ans,area,n;

Node q;

while (scanf("%lld",&n)!=EOF)

{if(n==0) break;

ans=0;

for (int i=0;i<n;i++)

{scanf("%lld",&q.h);   //输入一个柱子高度

q.len=1;

if(st.empty())//栈空时直接进栈

st.push(q);

else if (q.h<=(st.top()).h)//反序时

{tmp=0;   //tmp表示前一个柱子对应矩形的宽度

while (!st.empty() && q.h<=(st.top().h))

{st.top().len+=tmp;   //栈顶柱子较高，累加其矩形宽度

area=st.top().h*st.top().len;   //求矩形面积

if (area>ans) ans=area;   //求最大矩形面积

tmp=st.top().len;

st.pop();

}

q.len+=tmp;

st.push(q);

}

else st.push(q);

}

tmp=0;

while (!st.empty())//输入完毕做最后一次计算

{st.top().len+=tmp;

area=st.top().h*st.top().len;

if (area>ans) ans=area;

tmp=st.top().len;

st.pop();

}

cout << ans << endl;

}

}

上述程序是AC代码，运行时间为360ms，运行占用的空间为1304KB，编译语言为C++。
3．2．11POJ3984——迷宫问题


视频讲解


时间限制： 1000ms； 内存限制： 65536KB。
问题描述： 定义一个二维数组。

int maze［5］［5］ = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

}

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，注意只能横着走或竖着走，不能斜着走，要求编程找出从左上角到右下角的最短路线。
输入格式： 一个5×5的二维数组，表示一个迷宫。数据要保证有唯一解。
输出格式： 从左上角到右下角的最短路径，格式如样例所示。
输入样例： 

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

输出样例： 

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

解法1： 由于求的是最短路径，采用队列求迷宫问题的方法，与《教程》中3．2．7节的原理完全相同。在输出迷宫路径时，通过一个path数组将反向路径反向输出即得到正向路径。对应的程序如下： 

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

const int MAX=5;   //迷宫的最大行、列数

int dx［］={-1,0,1,0};   //x方向的偏移量

int dy［］={0,1,0,-1};   //y方向的偏移量

int mg［MAX］［MAX］;

int m=5,n=5;

struct Box//队列中的方块元素类型

{int i;   //方块的行号

int j;   //方块的列号

Box *pre;   //本路径中上一方块的地址

Box() {}//构造函数

Box(int i1,int j1)//重载构造函数

{i=i1;

j=j1;

pre=NULL;

}

};

void disppath(queue<Box *> &qu)//输出一条迷宫路径

{vector<Box> apath;   //存放一条迷宫路径

Box *b;

b=qu.front();   //从队头开始向入口方向搜索

while (b!=NULL)

{apath.push_back(Box(b->i,b->j));   //将搜索的方块添加到apath中

b=b->pre;

}

for (int i=apath.size()-1;i>=0;i--)//反向输出构成一条正向迷宫路径

printf("(%d, %d)＼n",apath［i］.i,apath［i］.j); 

}

void mgpath(int xi,int yi,int xe,int ye)//求一条从(xi,yi)到(xe,ye)的迷宫路径

{Box *b,*b1;

queue<Box *>qu;   //定义一个队列qu

b=new Box(xi,yi);   //建立入口的对象b

qu.push(b);   //入口对象b进队,其pre置为NULL

mg［xi］［yi］=-1;   //为避免来回找相邻方块置mg值为-1

while (!qu.empty())//队不空时循环

{b=qu.front();   //取队头方块b

if (b->i==xe && b->j==ye)//找到了出口,输出路径

{disppath(qu);   //输出一条迷宫路径 

return;

}

qu.pop();   //出队方块b

for (int di=0;di<4;di++)//循环扫描每个方位,把每个可走的方块进队

{int i=b->i+dx［di］;   //找b的di方位的相邻方块(i,j)

int j=b->j+dy［di］;

if (i>=0 && i<m && j>=0 && j<n && mg［i］［j］==0)

{b1=new Box(i,j);   //(i,j)方块有效且可走

b1->pre=b;   //将该相邻方块进队,并置其pre为前驱方块

qu.push(b1);

mg［i］［j］=-1;   //为避免来回找相邻方块置mg值为-1

}

}

}

}

int main()

{for (int i=0;i<MAX;i++)

for (int j=0;j<MAX;j++)

scanf("%d",&mg［i］［j］);

mgpath(0,0,4,4);

return 0;

}

上述程序是AC代码，运行时间为0ms，运行占用的空间为168KB，编译语言为C++。
解法2： 解法1中队列qu元素是创建的Box对象的指针，通过pre变量表示前驱关系，算法设计相对复杂，这里采用pre二维数组存放搜索中的前驱方块，例如pre［3］［4］．i=1，pre［3］［4］．j=2表示方块(3，4)的前驱方块是(1，2)，当找到出口时求最短路径。对应的程序如下： 

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

const int MAX=5;   //迷宫最大的行、列数

int dx［］={-1,0,1,0};   //x方向的偏移量

int dy［］={0,1,0,-1};   //y方向的偏移量

int mg［MAX］［MAX］;

int m=5,n=5;

struct Box//队列中的方块元素类型

{int i;   //方块的行号

int j;   //方块的列号

Box() {}//构造函数

Box(int i1,int j1)//重载构造函数

{i=i1;

j=j1;

}

};

Box pre［MAX］［MAX］;   //表示前驱关系

void disppath(int xi,int yi,int xe,int ye)//输出一条迷宫路径

{vector<Box> apath;   //存放一条迷宫路径

int i,j,i1,j1;

i=xe; j=ye;   //从(xe,ye)反推逆路径

while (i!=xi || j!=yi)

{apath.push_back(Box(i,j));   //将搜索的方块添加到apath中

i1=pre［i］［j］.i;

j1=pre［i］［j］.j;

i=i1; j=j1;

}

apath.push_back(Box(xi,yi));   //将入口添加到apath中

for (int i=apath.size()-1;i>=0;i--)//反向输出构成一条正向迷宫路径

printf("(%d, %d)＼n",apath［i］.i,apath［i］.j); 

}

void mgpath(int xi,int yi,int xe,int ye)//求一条从(xi,yi)到(xe,ye)的迷宫路径

{Box b,b1;

queue<Box>qu;   //定义一个队列qu

b=Box(xi,yi);   //建立入口的对象b

qu.push(b);   //入口对象b进队

mg［xi］［yi］=-1;   //为避免来回找相邻方块置mg值为-1

while (!qu.empty())//队不空时循环

{b=qu.front();   //取队头方块b

if (b.i==xe && b.j==ye)//找到了出口,输出路径

{disppath(xi,yi,xe,ye);   //输出一条迷宫路径

return;

}

qu.pop();   //出队方块b

for (int di=0;di<4;di++)//循环扫描每个方位,把每个可走的方块进队

{int i=b.i+dx［di］;//找b的di方位的相邻方块(i,j)

int j=b.j+dy［di］;

if (i>=0 && i<m && j>=0 && j<n && mg［i］［j］==0)

{b1=Box(i,j);   //(i,j)方块有效且可走

pre［i］［j］.i=b.i; pre［i］［j］.j=b.j;   //置其前驱方块为(b.i,b.j) 

qu.push(b1);   //将该相邻方块进队

mg［i］［j］=-1;   //为避免来回找相邻方块置mg值为-1

}

}

}

}

int main()

{for (int i=0;i<MAX;i++)

for (int j=0;j<MAX;j++)

scanf("%d",&mg［i］［j］);

mgpath(0,0,4,4);

return 0;

}

上述程序是AC代码，运行时间为0ms，运行占用的空间为168KB，编译语言为C++。
3．2．12POJ1686——算术式子是否等效


视频讲解


时间限制： 1000ms； 内存限制： 10000KB。
问题描述： 数学老师太懒了，没能在试卷中给问题打分，在试卷中学生给出了求解问题的复杂的公式，不同的学生可能给出不同的形式，但都是正确的答案，这使得评分非常困难。因此，数学老师需要计算机程序员的帮助。请编写一个程序读取不同的公式，并确定它们在算术上是否等效。
输入格式： 输入的第一行包含一个整数n(1≤n≤20)，它是测试用例的数量。在第一行之后，每个测试用例都有两行。一个测试用例由两个算术表达式组成，每个算术表达式位于单独的行中，最多80个字符。在输入中没有空行，表达式包含以下一项或多项： 
① 单字母变量(不区分大小写)。
② 一位数字。
③ 匹配的左、右括号。
④ 二元运算符+、-和*分别用于加、减和乘。
⑤ 上述标记之间的任意空白或制表符字符。
注意： 对于所有运算符，表达式在语法上都是正确的，并且从左到右具有相同的优先级。保证变量的系数和指数适合16位整数。
输出格式： 程序必须为每个测试用例输出一行，如果每个测试数据的输入表达式在算术上等效，则输出“YES”，否则输出“NO”，输出应全部使用大写字符。
输入样例： 

3

(a+b-c)*2

(a+a)+(b*2)-(3*c)+c

a*2-(a+c)+((a+c+e)*2)

3*a+c+(2*e)

(a-b)*(a-b)

(a*a)-(2*a*b)-(b*b)

输出样例： 

YES

YES

NO

参考博客： https://www．cnblogs．com/lxm940130740/p/3289003．html
解： 采用《教程》第3章中3．1．7节用栈求简单表达式值的思路，对于输入的两个算术表达式求出值分别为ans1和ans2，若两者相同，输出“YES”，否则输出“NO”。对应的程序如下： 

#include <iostream>

#include <cstdio>

#include <cstring>

#include <stack>

using namespace std;

#define MAXN 90

int priority(char c)//求运算符c的优先级

{if(c=='(')

return 0;

else if(c=='*')

return 2;

else

return 1;

}

void convert(char *exp,char *postexp)//转换为后缀表达式

{int len=strlen(exp),t=0;

char ch;

stack<char> st;   //定义一个栈

for(int i=0;i<len;i++)

if(exp［i］!=' ')

{ch=exp［i］;

if ((ch<='z' && ch>='a') || (ch>='0' && ch<='9'))

postexp［t++］=ch;

else

{if (st.empty() || ch=='(')

st.push(ch);

else if (ch==')')

{while (!st.empty() && st.top()!='(')

{postexp［t++］=st.top();

st.pop();

}

st.pop();

}

else

{while (!st.empty() && priority(ch)<=priority(st.top()))

{postexp［t++］=st.top();

st.pop();

}

st.push(ch);

}

}

}

while (!st.empty())

{postexp［t++］=st.top();

st.pop();

}

postexp［t］='＼0';

}

int calculate(char *postexp)//求后缀表达式值

{int len=strlen(postexp),a,b,c;

char ch;

stack<int> st;

for(int i=0; i<len; i++)

{ch=postexp［i］;

if (ch>='0' && ch<='9')

st.push(ch-'0');

else if (ch<='z' && ch>='a')

st.push(int(ch));

else

{a=st.top(); st.pop();

b=st.top(); st.pop();

switch(ch)

{

case '*':

c=b*a;

break;

case '+':

c=b+a;

break;

case '-':

c=b-a;

break;

}

st.push(c);

}

}

return st.top();

}

int main()

{char exp［MAXN］,postexp［MAXN］;

int n;

scanf("%d",&n);

getchar();

while(n--)

{gets(exp);

convert(exp,postexp);

int ans1=calculate(postexp);

gets(exp);

convert(exp,postexp);

int ans2=calculate(postexp);

if(ans1==ans2)

printf("YES＼n");

else

printf("NO＼n");

}

}

上述程序是AC代码，运行时间为0ms，运行占用的空间为104KB，编译语言为C++。