栈、队列

栈

栈是一种先进后出的数据结构

初始化

#include <iostream>
using namespace std;

const int N = 100010;

int stk[N], tt;

入栈

void push(int x) {
    stk[++tt] = x;
}

出栈

void pop() {
    tt--;
}

判断栈是否为空

bool empty() {
    return tt <= 0;
}

取栈顶元素

int getTop() {
    return stk[tt];
}

队列

队列是一种先进先出的数据结构

初始化

#include <iostream>

using namespace std;

const int N = 100010;

int q[N], hh, tt = -1;

入队

/**
 * @brief 将x入队（入队元素放队尾）
 * @param x 
 */
void push (int x) {
    q[++tt] = x;
}

出队

/**
 * @brief 对头元素出队
 */
void pop () {
    hh++;
}

判断队列是否为空

/**
 * @brief 判断队列是否为空
 * @return true 
 * @return false 
 */
bool empty () {
    return hh > tt;
}

获得队首元素

/**
 * @brief 获得队首元素
 * @return int 
 */
int front () {
    return q[hh];
}

获得队尾元素

/**
 * @brief 获得队首元素
 * @return int 
 */
int front () {
    return q[hh];
}

单调栈

单调栈：就是在操作栈的时候保持栈内元素保持单调（单调递增或单调递减）
主要针对的问题：在一个数组中找到每个数左边比它小的最近的那个数

给定一个长度为 $N$ 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 $-1$ 。

输入样例

5
3 4 2 7 5

输出样例

-1 3 -1 2 2

暴力枚举

for (int i = 0; i < n; i++) {
    bool flag = false;
	for (int j = i - 1; j >= 0; j--) {
        if (a[j] < a[i]) {
            cout << a[j] << ' ';
            flag = true;
        }
    }
    if (!flag)
        cout << "-1" << ' ';
}

时间复杂度 $O(n^2)$

使用单调栈

/**
 * @file monotoneStack.cpp
 * @author Rick (Kay_Rick@outlook.com)
 * @version 1.0
 * @date 2020-09-07 23:44:59
 * @brief 单调栈
 * 
 * @copyright Copyright (c) 2020 Rick, All Rights Reserved.
 * 
 */
#include <iostream>
#include <stack>

using namespace std;

int n;
stack<int> stk;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        while (!stk.empty() && stk.top() >= x)
            stk.pop();
        // 说明找到了当前合适的元素
        if (!stk.empty())
            cout << stk.top() << ' ';
        // 没有找到
        else
            cout << "-1" << ' ';
        stk.push(x);
    }
    return 0;
}

单调队列

单调队列：就是在操作队列的时候保持队列内元素保持单调（单调递增或单调递减）
主要针对的问题：固定滑动窗口中求最值
$deque$ ：双端队列，队头队尾都可加入元素和删除元素

有一个大小为 $k$ 的滑动窗口，它从数组的最左边移动到最右边。每次滑动窗口向右移动一个位置，您的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

窗口位置	最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

/**
 * @file monotoneQueue.cpp
 * @author Rick (Kay_Rick@outlook.com)
 * @version 1.0
 * @date 2020-09-07 23:48:29
 * @brief 单调队列
 * 
 * @copyright Copyright (c) 2020 Rick, All Rights Reserved.
 * 
 */
#include <deque>
#include <iostream>

using namespace std;

const int N = 1000010;
// 序列长度为n、滑动窗口长度为k
int n, k;
int nums[N];
// 使用双端队列：队头和队尾都可加入元素和删除元素
deque<int> qu;

int main() {
    cin >> n >> k;

    for (int i = 0; i < n; i++)
        cin >> nums[i];

    for (int i = 0; i < n; i++) {
        // 判断队头是否已经滑出窗口
        if (!qu.empty() && i - k + 1 > qu.front())
            qu.pop_front();
        // 加入队列中的元素要满足单调
        while (!qu.empty() && nums[qu.back()] >= nums[i])
            qu.pop_back();
        // 队列中存的是元素下标
        qu.push_back(i);
        // 队头是最小值
        if (i >= k - 1)
            cout << nums[qu.front()] << ' ';
    }
    cout << endl;
    qu.clear();

    for (int i = 0; i < n; i++) {
        if (!qu.empty() && i - k + 1 > qu.front())
            qu.pop_front();
        while (!qu.empty() && nums[qu.back()] <= nums[i])
            qu.pop_back();
        qu.push_back(i);
        if (i >= k - 1)
            cout << nums[qu.front()] << ' ';
    }

    return 0;
}

栈实现队列

队列是一种先进先出的数据结构，栈是一种先进后出的数据结构。我们使用两个栈 s1, s2 就能实现一个队列的功能。

当调用 push 让元素入队时，只要把元素压入 s1 即可，比如说 push 进 3 个元素分别是 1,2,3

那么如果这时候使用 peek 查看队头的元素怎么办呢？按道理队头元素应该是 1，但是在 s1 中 1 被压在栈底，现在就要轮到 s2 起到一个中转的作用了：当 s2 为空时，可以把 s1 的所有元素取出再添加进 s2，这时候 s2 中元素就是先进先出顺序了。

对于 pop 操作，只要操作 s2
如果两个栈都为空的话，就说明队列为空

/**
 * @file MyQueue.cpp
 * @author Rick (Kay_Rick@outlook.com)
 * @version 1.0
 * @date 2020-09-08 15:53:57
 * @brief 使用栈实现队列
 * 
 * @copyright Copyright (c) 2020 Rick, All Rights Reserved.
 * 
 */
#include <iostream>
#include <stack>

using namespace std;

class MyQueue {
  private:
    stack<int> s1, s2;

  public:
    /**
     * @brief 添加元素到队尾
     * @param x 
     */
    void push(int x) {
        s1.push(x);
    }

    /**
     * @brief 返回队头元素
     * @return int 
     */
    int peek() {
        // s2为空的时候，把s1全部导入s2中
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        return s2.top();
    }

    /**
     * @brief 删除队头元素
     */
    void pop() {
        // 保证s2非空
        peek();
        s2.pop();
    }

    /**
     * @brief 判断队列是否为空
     * @return true 
     * @return false 
     */
    bool empty() {
        return s1.empty() && s2.empty();
    }
};

队列实现栈

如果说双栈实现队列比较巧妙，那么用队列实现栈就比较简单粗暴了，只需要一个队列作为底层数据结构

push ：直接将元素加入队列，同时记录队尾元素，因为队尾元素相当于栈顶元素

每次 pop：把队列前面的都取出来再加入队尾，让之前的队尾元素排到队头，这样就可以取出

/**
 * @file MyStack.cpp
 * @author Rick (Kay_Rick@outlook.com)
 * @version 1.0
 * @date 2020-09-08 17:16:37
 * @brief 使用队列实现栈
 * 
 * @copyright Copyright (c) 2020 Rick, All Rights Reserved.
 * 
 */

#include <iostream>
#include <queue>

using namespace std;

class MyStack {
    private:
        queue<int> q;
        int top_element;
    public:
        /**
         * @brief 添加元素到栈顶
         * @param x 
         */
        void push(int x) {
            q.push(x);
            top_element = x;
        }

        /**
         * @brief 返回栈顶元素
         * @return int 
         */
        int top() {
            return top_element;
        }

        /**
         * @brief 删除栈顶元素 (把队列前面的都取出来再加入队尾，让之前的队尾元素排到队头)
         */
        void pop() {
            int size = q.size();
            while (size > 1) {
                q.push(q.front());
                q.pop();
                size--;
            }
            // 删除栈顶元素
            q.pop();
            // 更新栈指针为队尾
            top_element = q.back();
        }

        /**
         * @brief 判断栈是否为空
         * @return true 
         * @return false 
         */
        bool empty() {
            return q.empty();
        }
};

栈

初始化

入栈

出栈