這道題我們采用數(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ù)個(gè)數(shù)，有多少組。

將具體解決方法放入judge函數(shù)寫，該函數(shù)會(huì)判斷并輸出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)闂Ｊ前催@個(gè)順序放元素的，每次遍歷入棧，并讀一個(gè)數(shù)據(jù)到隊(duì)列。

如果棧空間超過stksize了，則輸出NO

如果隊(duì)頭元素與棧頂元素匹配，則pop

遍歷完后看看隊(duì)列還有沒有沒匹配的，有的話與棧中元素匹配，這時(shí)棧頂必須與隊(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)   //?？臻g超出限制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)體的形式，只需把其中某些代碼改動(dòng)即可。

完整代碼如下：

#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;
}