这道题我们采用数组来模拟堆栈和队列。
简单说一下大致思路，我们用栈来存1234.....，队列来存输入的一组数据，栈与队列进行匹配，相同就pop
机翻
1、条件准备
stk是栈，que是队列。
tt指向的是栈中下标，front指向队头，rear指向队尾。
初始化栈顶为0，队头为0，队尾为-1
#include<iostream>
using namespace std;#define MAXSIZE 1010
#define ERROR -1int stk[MAXSIZE],tt=0;
int que[MAXSIZE],front=0,rear=-1;
主函数加快cin,cout，将解决问题的步骤用solve（）来实现
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();return 0;
}
2、solve函数
先输入栈的最大空间，每组数据个数，有多少组。
将具体解决方法放入judge函数写，该函数会判断并输出yes,no
到下一组前要清空栈和队列。
void solve()
{int stksize,squsize,num;cin>>stksize>>squsize>>num;while(num--){ judge(stksize,squsize);
//传栈最大空间，每组数据长度tt=0;front=0,rear=-1;}}
3、judge函数
flag是判断最后该输出yes还是no
从1到squsize遍历，因为栈是按这个顺序放元素的，每次遍历入栈，并读一个数据到队列。
如果栈空间超过stksize了，则输出NO
如果队头元素与栈顶元素匹配，则pop
遍历完后看看队列还有没有没匹配的，有的话与栈中元素匹配，这时栈顶必须与队头匹配，不匹配则为NO
void judge(int stksize, int squsize)
{int flag = 1;//标记是yes还是nofor (int i = 1; i <= squsize; i++){ stk[++tt] = i; //放入栈中cin >> que[++rear]; //读取数据if (tt > stksize) //栈空间超出限制flag = 0;while (tt && stk[tt] == que[front]){ //栈顶与队头元素匹配，poptt--;front++;}}while (front <= rear){ //最后剩余栈中的元素进行匹配if (stk[tt] != que[front]) flag = 0;tt--, front++;}if (flag) //输出cout << "YES" << endl;elsecout << "NO" << endl;
}
4、总结
用数组模拟栈队列在写算法题中也是常用的，因为结构体没数组这样找快。
当然这道题也可以写成栈与队列结构体的形式，只需把其中某些代码改动即可。
完整代码如下：
#include <iostream>
using namespace std;#define MAXSIZE 1010
#define ERROR -1int stk[MAXSIZE], tt = 0;
int que[MAXSIZE], front = 0, rear = -1;void judge(int stksize, int squsize)
{int flag = 1;for (int i = 1; i <= squsize; i++){stk[++tt] = i;cin >> que[++rear];if (tt > stksize)flag = 0;while (tt && stk[tt] == que[front]){tt--;front++;}}while (front <= rear){if (stk[tt] != que[front]) flag = 0;tt--, front++;}if (flag)cout << "YES" << endl;elsecout << "NO" << endl;
}void solve()
{int stksize, squsize, num;cin >> stksize >> squsize >> num;while (num--){judge(stksize, squsize);tt = 0;front = 0, rear = -1;}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();return 0;
}
