第1课 栈

• 定义:

「栈(stack)是限定仅在表尾进行插入和删除操作的线性表。」

• 特点:

其插入和删除操作都限制在表的一端进行，这一端被称为“「栈顶(top)」”，相对的另一端称为“「栈底(bottom)」”。插入操作称为“「进栈(PUSH)」”或者“压栈”，删除操作称为“「出栈(POP)」”。栈的特点是“先进后出(「FILO，First In Last Out」)”

存储方式

• 顺序栈
• 链式栈

顺序栈

其实就是用数组模拟栈的操作 如果我们有N个元素要入栈, 一般定义栈的大小为N+1

• 初始化:

const int N=188;
int s[N+1];
int top = 0;

• 空栈

if(top == 0)
    ;

• 满栈

if(top == N)
    ;

• 入栈

void push(int x)
{
    if(top < N) {
        top++;
        s[top] = x;
    }
}

• 出栈

int pop() {
    int data = s[top];
    if(top > 0) {
        top--;
    }

    return data;
}

链栈

STL stack

stack是堆栈容器，是一种“先进后出”的容器。stack是简单地装饰 deque 容器而成为另外的一种容器。

初始化

#include <stack>
using namespace std;

stack <int> s;

基本操作

s.empty() 堆栈为空则返回真

s.pop() 移除栈顶元素

s.push() 在栈顶增加元素

s.size() 返回栈中元素数目

s.top() 返回栈顶元素

示例:

// stack::empty
#include <iostream>
#include <stack>
using namespace std;

int main ()
{
  stack<int> mystack;
  int sum (0);

  for (int i=1;i<=10;i++)
    mystack.push(i);

  while (!mystack.empty()) {
     sum += mystack.top();
     mystack.pop();
  }

  cout << "total: " << sum << endl;

  return 0;
}

例题 1 NOIP 2018 15题

15. 下图中所使用的数据结构是（ ）。

A. 哈希表   B. 栈    C. 队列    D. 二叉树

出栈顺序

判断方法

1. 对于出栈序列中的每一个数字，在它后面的、比它小的所有数字，一定是按递减顺序排列的。

假如入栈顺序为1234，给定一个出栈序列，如2431，它是合法的。

假如出栈序列为4123，显然不满足上述要求，因为对于4，它后面比它小的数字序列为123，递增，所以不是合法出栈序列。

2. 直接模拟进栈 出栈的过程可以简单的判断出栈顺序.

例题 2 2017 16题

16. 对于入栈顺序为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

例题 3 P4387 【深基15.习9】验证栈序列

题目描述

给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 n(n≤100000)。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。为了防止骗分，每个测试点有多组数据。

输入格式

第一行一个整数 q，询问次数。

接下来 q 个询问，对于每个询问：

第一行一个整数 n 表示序列长度；

第二行 n 个整数表示入栈序列；

第三行 n 个整数表示出栈序列；

输出格式

对于每个询问输出答案。

输入输出样例

• 输入 #1复制

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

• 输出 #1复制

Yes
No

分析

前面选择题做完后, 我们已经会判断出栈序列是否正确, 那么现在用程序模拟下吧.

a[]: 入栈数组 b[]: 出栈数组 ai 和 bi 分别是a[] 和 b[]数组的当前下标

1. 首先将入栈序列的第 ai 个元素压到 “stack”中，
2. 判断（注意用while判断，因为可能连续弹出）“stack”中的栈顶元素是否和出栈序列中的第 bi 个元素一致（栈为空就不用判断了）如果一致则弹出栈顶元素，bi++；如果不一致则ai++, 重复 1.
3. 最后如果“stack”为空或指针bi到达出栈序列的末尾就输出Yes，否则输出No

参考代码

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

const int MAXN = 100000 + 10;

int q, n, a[MAXN], b[MAXN];
stack <int> s;

int main()
{
 cin >> q;
 while(q--) {
  cin >> n;
  for(int i = 1; i <= n; i++)
   cin >> a[i];

  for(int i = 1; i <= n; i++)
   cin >> b[i];

  int bi = 1;
  while(!s.empty())
   s.pop();

  for(int i = 1; i <= n; i++) {
   s.push(a[i]);

   while (!s.empty() && s.top() == b[bi]) {
    s.pop();
    bi++;
   }
  }

  if(s.empty())
   cout << "Yes" << endl;
  else
   cout << "No" << endl;
 }

 return 0;
}

匹配问题

例题 4  P1241 括号序列

题目描述

定义如下规则序列(字符串)：

1．空序列是规则序列；

2．如果S是规则序列，那么(S)和[S]也是规则序列；

3．如果A和B都是规则序列，那么AB也是规则序列。

例如，下面的字符串都是规则序列：

()，[]，(())，([])，()[]，()[()]

而以下几个则不是：

(，[，]，)(，())，([()

现在，给你一些由‘(’，‘)’，‘[’，‘]’构成的序列，你要做的，是补全该括号序列，即扫描一遍原序列，对每一个右括号，找到在它左边最靠近它的左括号匹配，如果没有就放弃。在以这种方式把原序列匹配完成后，把剩下的未匹配的括号补全。

输入格式

输入文件仅一行，全部由‘(’，‘)’，‘[’，‘]’组成，没有其他字符，长度不超过100。

输出格式

输出文件也仅有一行，全部由‘(’，‘)’，‘[’，‘]’组成，没有其他字符，把你补全后的规则序列输出即可。

输入输出样例

• 输入 #1

([()

• 输出 #1

()[]()

说明/提示

将前两个左括号补全即可。

分析

栈常用来解决匹配问题.

模拟来做下面的要求:

你要做的，是补全该括号序列，即扫描一遍原序列，对每一个右括号，找到在它左边最靠近它的左括号匹配，如果没有就放弃。在以这种方式把原序列匹配完成后，把剩下的未匹配的括号补全。

参考代码

#include<bits/stdc++.h>
using namespace std;

stack <int> s;
string str;
bool ok[1000];

int main()
{
 cin >> str;

 for(int i = 0; i < str.size(); i++)
 {
  if(str[i] == ']')
  {
   if(s.empty())
    continue;

   int k = s.top();
   if(str[k] == '[')
   {
    ok[k] = ok[i] = 1;
    s.pop();
   }
  }
  else if(str[i] == ')')
  {
   if(s.empty())
    continue;

   int k = s.top();
   if(str[k] == '(')
   {
    ok[k] = ok[i] = 1;
    s.pop();
   }
  }
  else
   s.push(i);
 }

 for(int i = 0;i < str.size();i ++)
 {
  if(ok[i])
   cout << str[i];
  else
  {
   if(str[i] == '(' || str[i] == ')')
    printf("()");
   else
    printf("[]");
  }
 }
 return 0;
}

题单

1. P4387 【深基15.习9】验证栈序列
2. UVA514 铁轨 Rails
3. P1044 栈
4. P1739 表达式括号匹配
5. P1241 括号序列
6. UVA673 平衡的括号 Parentheses Balance