這道題我們采用數(shù)組來模擬堆棧和隊(duì)列。
簡單說一下大致思路，我們用棧來存1234.....，隊(duì)列來存輸入的一組數(shù)據(jù)，棧與隊(duì)列進(jìn)行匹配，相同就pop
機(jī)翻
1、條件準(zhǔn)備
stk是棧，que是隊(duì)列。
tt指向的是棧中下標(biāo)，front指向隊(duì)頭，rear指向隊(duì)尾。
初始化棧頂為0，隊(duì)頭為0，隊(duì)尾為-1
#include<iostream>
using namespace std;#define MAXSIZE 1010
#define ERROR -1int stk[MAXSIZE],tt=0;
int que[MAXSIZE],front=0,rear=-1;
主函數(shù)加快cin,cout，將解決問題的步驟用solve（）來實(shí)現(xiàn)
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();return 0;
}
2、solve函數(shù)
先輸入棧的最大空間，每組數(shù)據(jù)個數(shù)，有多少組。
將具體解決方法放入judge函數(shù)寫，該函數(shù)會判斷并輸出yes,no
到下一組前要清空棧和隊(duì)列。
void solve()
{int stksize,squsize,num;cin>>stksize>>squsize>>num;while(num--){ judge(stksize,squsize);
//傳棧最大空間，每組數(shù)據(jù)長度tt=0;front=0,rear=-1;}}
3、judge函數(shù)
flag是判斷最后該輸出yes還是no
從1到squsize遍歷，因?yàn)闂Ｊ前催@個順序放元素的，每次遍歷入棧，并讀一個數(shù)據(jù)到隊(duì)列。
如果?？臻g超過stksize了，則輸出NO
如果隊(duì)頭元素與棧頂元素匹配，則pop
遍歷完后看看隊(duì)列還有沒有沒匹配的，有的話與棧中元素匹配，這時棧頂必須與隊(duì)頭匹配，不匹配則為NO
void judge(int stksize, int squsize)
{int flag = 1;//標(biāo)記是yes還是nofor (int i = 1; i <= squsize; i++){ stk[++tt] = i; //放入棧中cin >> que[++rear]; //讀取數(shù)據(jù)if (tt > stksize) //棧空間超出限制flag = 0;while (tt && stk[tt] == que[front]){ //棧頂與隊(duì)頭元素匹配，poptt--;front++;}}while (front <= rear){ //最后剩余棧中的元素進(jìn)行匹配if (stk[tt] != que[front]) flag = 0;tt--, front++;}if (flag) //輸出cout << "YES" << endl;elsecout << "NO" << endl;
}
4、總結(jié)
用數(shù)組模擬棧隊(duì)列在寫算法題中也是常用的，因?yàn)榻Y(jié)構(gòu)體沒數(shù)組這樣找快。
當(dāng)然這道題也可以寫成棧與隊(duì)列結(jié)構(gòu)體的形式，只需把其中某些代碼改動即可。
完整代碼如下：
#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;
}
