栈和队列

First Post:
Last Update:

本章无需前置知识

栈和队列

很简单的数据结构

栈

栈是一种先进后出，是一种很简单的数据结构，此处会介绍简单的栈变形。

lzh先列个题表：

  1. Editor——模拟光标
  2. Largest Rectangle in a Historgram

以上都是可以用栈完成或栈所衍生出来的问题

Editor

维护一个整数编辑器，有以下五种操作，操作不超过1e6。

I x：在光标处插入整数x，插入后将光标移至x后；

D：删掉光标前的数

L：光标左移

R：光标右移

Q k： 询问在位置k之前的最大前缀和，k不得超过当前光标

这题是可能刚拿到时会有点懵，但是如果想想栈的方法，就会出现思路。

对顶栈

lzh发现，这题若只有插入删除功能，可能就用普通的链表就行了。但是这题有要求光标的左进 / 右进模拟，所以用一个对顶栈模拟更为容易形象——

首先，在一切开始前，lzh 建立了两个栈：k1和k2，再建立个前缀和数组sum与维护最大前缀和的数组f

I 操作

  1. 把x压入看k1栈
  2. 更新sum[top1] = sum[top1 - 1] + x
  3. 对f[top1] = max(f[top1 - 1], f)

D 操作： 把k1的栈顶出栈

L 操作： 弹出k1的栈顶，压入k2

R 操作

  1. 弹出k2的栈顶，压入k1
  2. 更新sum[top1] = sum[top1 - 1] + 1
  3. 对f[top1] = max(f[top1 - 1], f)

Q 操作：访问f[k]

input

8
I 2
I -1
I 1
Q 3
L
D
R
Q 2

output

2
3

Code

#include <iostream>

#define please return
#define ac 0;

using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;

int k1[N], k2[N];
int f[N];
int sum[N];
int top1, top2;

void init()
{
    top1 = top2 = 0;
    f[0] = -INF;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr); 

    init();
    
    char op;
    int m;
    
    cin >> m;
    while(m -- )
    {
        cin >> op;
        if(op == 'I')
        {
            int x;
            cin >> x;

            k1[ ++ top1] = x;
            sum[top1] = sum[top1 - 1] + x;
            f[top1] = max(f[top1 - 1], sum[top1]); 
        }
        else if(op == 'D')
        {
            if(!top1) continue;
            top1 -- ;
        }
        else if(op == 'L')
        {
            if(!top1) continue;
            k2[++ top2] = k1[top1];
            top1 -- ;
        }
        else if(op == 'R')
        {
            if(!top2) continue;
            k1[++ top1] = k2[top2];
            top2 -- ;
            sum[top1] = sum[top1 - 1] + k1[top1];
            f[top1] = max(f[top1 - 1], sum[top1]);
        }
        else if(op == 'Q')
        {
            int k;
            cin >> k;
            cout << f[k] << endl;
        }
        // else if(op == 'O')		//可以看看实际效果
        // {
        //     for(int i = 1; i <= top1; i ++ )
        //     {
        //         cout << k1[i]<< ' ';
        //     }
        //     cout << '^' << ' '
        //     for(int i = top2; i > 0; i -- )
        //     {
        //         cout << k2[i] << ' ';
        //     }
        //     cout << endl;
        // }
    }
    
    please ac
}·

Largest Rectangle in a Historgram

如图所示，在一条水平线上方有若干个矩形（宽度默认为1），求包含于这些矩形的并集内部的最大矩形的面积（在下图中，答案为阴影部分的面积），矩形个数 ≤ 1e5。

img

输入描述

输入包含几个测试用例。每个测试用例描述一个直方图，并以整数n开始，表示由矩形组成的数量。可以假设1≤n≤100000。然后取n个整数h1…hn，其中0≤hi≤1000000000。这些数字表示直方图中从左到右的矩形的高度。每个矩形的宽度为1。最后一个测试用例的输入后面跟着一个0。

输出描述

对于单行上的每个测试用例输出，指定直方图中最大矩形的面积。记住，这个矩形必须在公共基线上对齐。

单调栈

这题需要单调栈来维护的，什么是单调栈呢？如下：

cin >> a;
while(k.top() > a) k.pop(); // k是单调递增栈
k.push(a);

单调栈维护矩形的高

input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

output

8
4000

code

#include <iostream>
#include <stack>

#define please return
#define ac 0;

using namespace std;
using ll = long long;

const int N = 1e5 + 10;

struct Node{
    int h, w;
};

stack<Node> k;

signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int n;
    while(cin >> n, n)
    {
        ll ans = 0;
        stack<Node> k;

        k.push({0,0});		// 方便初动
        for(int i = 0; i <= n; i ++ )
        {
            int h, w = 1;
            if(i != n) cin >> h;
            else h = 0;				// 在最后的最后在栈中放入0，以便清栈
            if(h >= k.top().h)
                k.push({h, w});
            else
            {
                w = 0;
                while(k.top().h > h)
                {
                    w += k.top().w;
                    ans = max(ans, (ll)w * k.top().h);
                    k.pop();
                }
                k.push({h, w + 1});
            }
        }

        cout << ans << endl;
    }

    please ac
}

队列

队列是一种先进先出的数据结构，像排队一样

队列与栈一样，是一种很简单的数据结构，我们可以手写而不去调用C++ STL中的,原因有二——一是手写的灵活，二是快。

跟栈一样，队列也有其相应的变形。这里先列出本文的题表：

  1. Team Queue
  2. 简单的滑动窗口类问题

以上是可以使用队列解决的问题

Team Queue

这是一道简单的模拟题哦，就拿这道开刀吧。

原题情境：中午排队吃饭，队列中有n个小组，每个小组有若干人。当一个人来到队伍时，如果有自己的组员自然是要插入该组的队尾，否则就排在队伍的最后边。给定不超过2e5个入队指令和出队指令，最后输出出队顺序。

在任何时刻，同一个小组的人都会站在一起，所以队伍中小组的状态就只有两种——有无这个小组，所以我们可以用队列Q来维护小组在队列中的位置，用队列g[N]来存储小组成员的顺序，然后是单纯的模拟。

输入描述：

有多次样例输入

第1行输入组数T（1≤T≤1000）如果T=0，结束程序

第2~T+1行输入组员个数n和n个小组成员编号num （n<1000, num< 1000000）

第n+2行开始输入指令：

  • ENQUEUE num 将num入队
  • DEQUEUE 将队头出队
  • STOP 结束样例操作

输出描述

对于第k组样例，第一行应该这么说：Scenario #k

接下来输出该样例的出队顺序

Input

2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0

Output

Scenario #1
101
102
103
201
202
203

Scenario #2
259001
259002
259003
259004
259005
260001

Code

#include <iostream>
#include <queue>
#include <cstring>

#define please return
#define ac 0;
#define loop while(1)

using namespace std;

const int N = 1e3 + 10, M = 1e6 + 10;

int Q[N], hh, tt;
queue<int> g[N];
int st[M];      //记录成员所属组
int k;

void init()
{
    memset(Q, 0, sizeof Q);
    hh = 0, tt = -1;
    memset(st, 0, sizeof st);
    for(int i = 0; i < N; i ++ )
        while(g[i].size())g[i].pop();
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int n;
    while(cin >> n, n)
    {
        init();
        cout << "Scenario #" << ++ k << '\n';

        for(int i = 1; i <= n; i ++ )
        {
            int T;
            cin >> T;
            while(T -- )
            {
                int num;
                cin >> num;
                st[num] = i;
            }
        }
        
        string op;
        while(cin >> op, op != "STOP")
        {
            if(op == "ENQUEUE")
            {
                int x;
                cin >> x;
                int t = st[x];
                if(g[t].empty())
                {
                    Q[++ tt] = t;
                }
                g[t].push(x);
            }
            else
            {
                if(hh <= tt)
                {
                    int t = Q[hh];
                    cout << g[t].front() << '\n';
                    g[t].pop();
                    if(g[t].empty())hh ++ ;
                }
            }
        }
        cout << endl;
    }
    please ac
}

滑动窗口类

这是一类问题，这里只讲长度的区间最大值问题

我们这先来个引例：

给出一段数列V，求出每段长度为k的区间里的最大值

这里要是没有时间限制，大家大可暴力解决此题，然额呢，既然来看此文的肯定不能接受这种O(n^2)复杂度的算法，所以此类固定长度的子序列中的最大值问题是可以使用队列解决，不过普通的队列是解决不了的，这里就需要单调队列了。

单调队列

跟单调栈一样，同样是对队列加了约束条件——

cin >> a;
while(q.back() > a)q.pop_back(); 	//单调递增的队列
q.push_back(a);

从上式的代码来看，好像和单调栈没啥区别，但可不要忘记队列是可以从队头出队列的，可以保证队列像滑动的窗口一样，本题是要求我们固定长度的区间最大值，即长度固定，那么我们可以用单调队列维护区间长度。还有一点我们还没有讲明白，那就是为什么单调队列可以O(n)解决此类问题。

我们可以任取两点i 、j且i < j， 如果V[i] < V[j]，那么i就可以出队列了，因为i<j，会比j先出队列，而V[j]又比V[i]大，对结果贡献更大。所以当j出现后，i就是完全无用的位置了。

以上得出的结论，我们已经可以完成此道引例：

#include <iostream>

#define please return
#define ac 0;

using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;

int q[N], hh, tt;
int a[N];
int mx[N];
int n, len;

void init()
{
    hh = 1, tt = 0;
}

void findMax()
{
    init();
    for(int i = 1; i <= n; i ++ )
    {
        while(a[q[tt]] < a[i])tt -- ;
        q[++ tt] = i;
        while(q[tt] - q[hh] + 1 > len)hh ++ ;
        if(i >= len) mx[i - len + 1] = a[q[hh]];
    }
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);

    cin >> n >> len;
    a[0] = INF;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    a[n + 1] = INF;

    findMax();

    for(int i = 1; i <= n - len + 1; i ++ ) cout << mx[i] << ' ';

    please ac
}

可以看出，每个元素只进出一次队列，故其时间复杂度为O(n)。

例题

输入一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。 例如 1,-3,5,1,-2,3 当m=4时，S=5+1-2+3=7 当m=2或m=3时，S=5+1=6

输入描述

第一行两个数n,m（n,m≤300000） 第二行有n个数，要求在n个数找到最大子序和

输出描述

一个数，数出他们的最大子序和

Input

6 4
1 -3 5 1 -2 3

Output

7

Code

#include <iostream>
#include <deque>

#define please return
#define ac 0;

using namespace std;

const int N = 1e7 + 10;

deque<int> q;	//就当作是单调队列吧

int s[N];

signed main()
{
    int n, l;
    cin >> n >> l;
    for(int i = 1; i <= n; i ++ ){
        int a;
        cin >> a;
        s[i] = s[i - 1] + a;
    }

    int ans = -0x3f3f3f3f;
    q.push_back(0);
    for(int i = 1; i <= n; i ++ ){
        while(q.size() && s[q.back()] >= s[i])q.pop_back();
        q.push_back(i);
        while(q.size() && i - q.front() > l) q.pop_front();
        ans = max(ans, s[i] - s[q.front()]);
        
    }

    cout << ans << endl;
    
    please ac
}