十三、判斷出棧序列

文章目錄

• 十三、判斷出棧序列
• • 題目描述
  • 解題思路
  • 上機(jī)代碼

題目描述

請判斷：指定的序列能否僅由 入棧 和 出棧 操作得到。

輸入：
有若干組數(shù)據(jù)輸入
每組數(shù)據(jù)中，第一行為兩個個整數(shù) n 和 m。n 表示需要依次從 1~n 入棧，m 表示這組數(shù)據(jù)有 m 個出棧序列需要判斷，當(dāng) n=0 且 m=0 時停止。
接下來有 m 行，每行表示一個出棧序列

輸出：
對每一個出棧序列，如果能正常出棧，則輸出 Yes，否則輸出 No。

sample：

input:
5 2
1 2 3 4 5
5 4 1 2 3
6 1
6 5 4 3 2 1
0 0

output:
Yes
No

Yes

測試輸入期待的輸出時間限制內(nèi)存限制額外進(jìn)程

測試用例 1	5 2 1 2 3 4 5 5 4 1 2 3 6 2 6 5 4 3 2 1 3 2 5 6 4 1 0 0	Yes No Yes Yes	1秒	64M	0

解題思路

定義兩個數(shù)組 a 和 b，a 數(shù)組用來存儲初始序列，即 1—n，b 數(shù)組用來存儲待判斷的序列

將 a、b數(shù)組從頭進(jìn)行比較

• 元素相同則繼續(xù)向后比
• 元素不同且棧空，則將元素 a[i] 壓棧
• 元素不同棧非空，且棧頂元素和 b[j] 相等，則彈棧

最后判斷棧是否為空，為空則序列符合要求，非空則不符合要求。

上機(jī)代碼

#include<cstdio> #include<cstring> #include<stack> #include<cstdlib> using namespace std; int a[1010] = { 0 }, b[1010] = { 0 }; int main() {int n = 0, m = 0;int flag = 0; //flag用來控制格式while (~scanf("%d%d", &n, &m) && n+m){if (flag)printf("\n");for (int i = 1; i <= n; i++){a[i] = i;}while (m--){for (int j = 1; j <= n; j++){scanf("%d", &b[j]);}stack<int>s;int x = 1, y = 1;while (y <= n){if (a[x] == b[y]) //相同則繼續(xù)向后判斷{x++;y++;}else if (!s.empty() && s.top() == b[y]) //棧頂元素與輸入元素相同則彈棧{y++;s.pop();}else if (x <= n) //初始數(shù)據(jù)壓棧{s.push(a[x]);x++;}elsebreak;}if (s.empty())printf("Yes\n");elseprintf("No\n");}flag = 1;}//system("pause")return 0; }

總結(jié)

以上是生活随笔為你收集整理的十三、判断出栈序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。