1. 栈的基本概念

栈(Stack)是一种线性存储结构。生活中的一个例子如一盘碟子。

  1. 栈中的数据元素遵守”先进后出”(First In Last Out)的原则，简称FILO结构。
  2. 只能在栈顶进行插入(push，入栈，也叫压栈)和删除(pop，出栈，也叫弹栈)操作。
  3. 允许元素插入与删除的一端称为栈顶(top)，另一端称为栈底。 stack-plate.jpg

栈的表示如下： stack_representation

1.1 入栈（push）示例

原来栈中有A、B、C、D四个数据元素，D在栈顶，现在需要插入一个新的数据E。

stack_push_operation

1.2 出栈（pop）示例

原来栈中有A、B、C、D、E四个数据元素，现在需要删除栈顶的元素E。

stack_pop_operation

2. 代码示例

C++标准库中提供了stack容器类，可以直接使用。主要函数如下：

  1. top()：返回一个栈顶元素的引用。
  2. push(const T& obj)：可以将对象副本压入栈顶。
  3. pop()：弹出栈顶元素。
  4. size()：返回栈中元素的个数。
  5. empty()：在栈中没有元素的情况下返回 true。

使用示例如下。

#include <iostream>
#include <stack>
using namespace std;

int main()
{
  stack<int> stack1; //empty stack of integer type
  stack1.push(100);
  stack1.push(200);
  stack1.push(300);
  stack1.push(400);
  stack1.push(500);

  stack1.pop();
  stack1.pop();

  stack1.push(600);

  while (!stack1.empty())
  {
    cout << stack1.top() << " ";
    stack1.pop();
  }
}

输出结果为：600 300 200 100

3. 作业

1、

【NOIP 2018 普及组初赛 q15】下图中所使用的数据结构是（ ）。
A. 哈希表   B. 栈   C. 队列   D. 二叉树  

2、

【CSP 2020 提高组第一轮 q04】今有一空栈 S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进行：进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈底元素为（ ）。
A. b   B. a   C. d   D. c  

3、

【NOIP 2017 普及组初赛 q16】对于入栈顺序为 a, b, c, d, e, f, g 的序列，下列（ ）不可能是合法的出栈序列。
A. a, b, c, d, e, f, g   B. a, d, c, b, e, g, f  
C. a, d, b, c, g, f, e   D. g, f, e, d, c, b, a  

4、

【NOIP 2017 普及组初赛 q13】向一个栈顶指针为 hs 的链式栈中插入一个指针 s 指向的结点时，应执行（ ）。
A. hs->next = s;  
B. s->next = hs; hs = s;  
C. s->next = hs->next; hs->next = s;  
D. s->next = hs; hs = hs->next;  

5、

【NOIP 2015 普及组初赛 q15】今有一空栈 S，对下列待进栈的数据元素序列 a，b，c，d，e，f 依次进行进栈，进栈，出栈，进栈， 进栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为:
A. f   B. c   C. a   D. b  

6、

【NOIP 2012 普及组初赛 q12】如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a，b，c，另有元素d已经出栈，则可能的入栈顺序是（ ）。
A. a, d, c, b   B. b, a, c, d  
C. a, c, b, d   D. d, a, b, c  

7、

【NOIP 2010 普及组初赛 q15】元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的不可能是（ ）。
A. R1   B. R2   C. R4   D. R5   

8、设栈最大长度为3，入栈序列为1、2、3、4、5、6，则不可能的出栈序列是（　　　）。
A）1、2、3、4、5、6             B）2、1、3、4、5、6
C）3、4、2、1、5、6             D）4、3、2、1、5、6

9、设TOP为链栈的栈顶指针，则空栈的条件是（　）。   
A）n==0     B）TOP->next==0     C）TOP==NULL    D）TOP->next==NULL

10、有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C第一个出栈，D第二个出栈的次序有哪几个？ 

11、设栈的输入序列是1，2，…，n，若输出序列的第一个元素是n，则第i个输出元素是（　）。   
A）n-i+1            B）i                C）n-i              D）前面都不正确

12、栈应用的典型事例是（　　）。   
A）排队     B）查找 C）归并  D）用“算符优先法”进行表达式求值

13、一般情况下，将递归算法转换成等价的非递归算法应该设置（　　）。   
A）栈           B）队列         C）堆栈或队列       D）数组