知识点：

栈是一种线性的数据结构，他满足后进先出（LIFO）。

栈作为一种线性的数据结构，显然它具有唯一的起始节点，唯一的尾结点，并且除首尾之外都具有唯一的直接前驱与唯一的直接后继。

一定要搞清楚逻辑关系，这样在栈的实现上会简单很多。

判断题：

1-1通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。 （F）(2分)

解析：数据结构的题目一定要画图，首先连续进栈，此时栈为（1，2），然后出栈输出2，之后进栈，栈变为（1,3），之后就是连续的出栈操作，输出3,1。

因此输出应该是2，3，1。

1-2若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1。（F） (2分)

解析：在栈当中要特别注意，元素在进栈之后可以马上出栈，也就是PUSH与POP可以连续进行，因此如果第一个元素不是N的时候第j个输出元素时不确定的。

1-3若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。（T） (2分)

解析：这里我们要非常了解栈的性质，就是栈是后件先出的数据结构，因此我们注意到如果第一个元素首先输出的是3，那么3出栈之后栈内的情况就是（1,2），因此后面无论怎么输出2都应该先比1输出。

选择题：

2-1给定一个堆栈的入栈序列为{ 1, 2, ⋯, n }，出栈序列为{ p​1​​, p​2​​, ⋯, p​n​​ }。如果p​2​​=n，则存在多少种不同的出栈序列？(2分

• 1
• 2
• n−1
• n

解析：在这里还是要考虑PUSH与POP可以连续进行，因此如果第二个元素是n的时候，第一个元素是谁都行，也就是n-1种情况。

2-2设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是： (2分)

• 1
• 3
• 5
• 1或者5

解析：因为第一个出栈元素是4因此在4出栈之后栈的情况是（1,2,3）,如果此时我们进行三次出栈操作，那么最后进栈又出栈的就是5，如果我们进行两次出栈，然后5进栈再立马出栈，这个时候最后一个出栈元素就是1.

2-3从栈顶指针为ST的链栈中删除一个结点且用X保存被删结点的值，则执行： (2分)

• X= ST->data;
• X= ST; ST = ST->next;
• X= ST->data; ST = ST->next;
• ST = ST->next; X= ST->data;

解析：因为ST指向栈顶元素，因此我们要先保存栈顶元素，x=ST->data，之后栈顶指针向后，ST=ST->next，如果链表掌握的比较好理解这里应该不是问题吧。

2-4设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b、d、c、f、e、a、g，则栈S的容量至少是： (2分)

• 1
• 2
• 3
• 4

解析：这样的题切忌急躁，慢慢画图，一步一步来。

这里就是要区别栈与队列的性质，栈是后进先出，队列是先进后出（不考虑优先队列与双端队列）。

以下解析来自百度：

由于队列是先进先出线性表，队列Q的出队顺序为b、d、c、f、e、a，则入队顺序必定也是b、d、c、f、e、a，这一顺序就是栈S的出栈顺序。又由于入栈顺序为a、b、c、d、e、f，因此入栈和出栈顺序是：a、b入栈，b出栈，c、d入栈，d、c出栈、e、f入栈，f、e、a出栈，因此栈中驻留元素最多是3个，因此栈S的容量至少应该为3。

2-5假设有5个整数以1、2、3、4、5的顺序被压入堆栈，且出栈顺序为3、5、4、2、1，那么为了获得这样的输出，堆栈大小至少为： (2分)

• 2
• 3
• 4
• 5

解析：同上慢慢画图慢慢来就行了，考察的还是栈的性质。

2-6若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是？ (2分)

• b c a e f d
• c b d a e f
• d c e b f a
• a f e d c b

解析：根据题意与栈的性质，我们发现第四个fed要进行三次连续的退栈。

2-7设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是？ (2分)

• 3 2 1 5 4
• 5 1 2 3 4
• 4 5 1 3 2
• 4 3 1 2 5

解析：还是那句话，咱画画图，不急来得及。别忘了PUSH与POP可以连续交替进行。

2-8有六个元素以6、5、4、3、2、1的顺序进栈，问哪个不是合法的出栈序列？ (2分)

• 2 3 4 1 5 6
• 3 4 6 5 2 1
• 5 4 3 6 1 2
• 4 5 3 1 2 6

解析：同上。

2-9若一个栈的入栈序列为1、2、3、…、N，输出序列的第一个元素是i，则第j个输出元素是： (2分)

• i−j−1
• i−j
• j−i−1
• 不确定

解析：前面有一个一样的判断。

2-10若一个栈的入栈序列为1、2、3、…、N，其输出序列为p​1​​、p​2​​、p​3​​、…、p​N​​。若p​1​​=N，则p​i​​为： (2分)

• i
• n−i
• n−i+1
• 不确定

解析：为什么这个就是唯一确定得了呢？因为第一个是n的时候，这个时候栈的情况是唯一确定的（栈的性质画画图），因此后面的出栈的顺序与入栈的顺序相反。

2-11将5个字母ooops按此顺序入栈，则有多少种不同的出栈顺序可以仍然得到ooops？ (2分)

• 1
• 3
• 5
• 6

解析：因为最后输出与这五个字母一样，也就是p与o都是进栈之后立马出栈，因此我们考虑三个o即可。

用P1表示第一个o进栈，O1表示第一个o出栈，以此类推。

P1 O1 P2 O2 P3 O3

P1 P2 O2 O1 P3 O3

P1 O1 P2 P3 O3 O2

P1 P2 P3 O3 O2 O1

P1 P2 O2 P3 O3 O1

2-12栈的插入和删除操作在（ ）进行。 (2分)

• 栈顶
• 栈底
• 任意位置
• 指定位置

编程题：

7-2 堆栈操作合法性 (20 分)

假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序列是否合法。

输入格式:

输入第一行给出两个正整数N和M，其中N是待测序列的个数，M（≤50）是堆栈的最大容量。随后N行，每行中给出一个仅由S和X构成的序列。序列保证不为空，且长度不超过100。

输出格式:

对每个序列，在一行中输出YES如果该序列是合法的堆栈操作序列，或NO如果不是。

输入样例：

4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX

输出样例：

YES
NO
NO
NO

AC代码：

#include <bits/stdc++.h>
using namespace std;int main()
{ios::sync_with_stdio(false);int n, m;cin >> n >> m;for(int i = 0; i < n; i++){string s;cin >> s;stringstream ss(s);char x;int res = 0;bool flag = true;while(ss >> x && flag){if(x == 'S'){if(res < m)res++;elseflag = false;}else{if(res > 0)res--;elseflag = false;}}if(flag && !res)cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}

解析：根据栈的性质慢慢来就行了。