Loading [MathJax]/jax/output/HTML-CSS/jax.js

栈、队列的总结

作者： 作者的头像   时来天地皆同力 ,  2022-09-29 12:09:46 ,  所有人可见 ,  阅读 210

1


1

栈、队列的总结

0. 前言

这篇文章主要是对栈、队列的总结, 从数组模拟栈和队列开始, 到单调栈和单调队列(双端队列), 然后分别列举出一道有关单调栈和单调队列的题目, 再到模拟循环队列, 以及用栈实现队列和队列实现栈。

1. 用数组模拟栈和队列

用数组模拟栈:
用数组模拟栈, 主要需要注意的是队头的指针, 下标从1开始存数。tt等于0时, 代表栈中无元素。
代码如下: 

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int st[N], tt = 0;

int main() {
    int m;
    cin >> m;
    string s;
    int x;
    while (m--) {
        cin >> s;
        if (s == "push") {
            cin >> x;
            st[++tt] = x;
        } else if (s == "pop") tt--;
        else if (s == "query") printf("%d\n", st[tt]);
        else {tt == 0 ? printf("YES\n") : printf("NO\n");}
    }
    return 0;
}

用数组模拟队列:

初始时刻头指针大于尾指针代表队列为空。赋值方式为先加1再赋值。

代码如下: 

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

const int N = 1e5 + 5;
int q[N];

int hh = 0, tt = -1;

int main() {
    int m;
    cin >> m;
    while (m--) {
        string s;
        cin >> s;
        int x;
        if (s == "push") {
            cin >> x;
            q[++tt] = x;
        } else if (s == "pop") {
            hh++;
        } else if (s == "empty") {
            hh > tt ? printf("YES\n") : printf("NO\n");
        } else printf("%d\n", q[hh]);
    }
    return 0;  
}

2. 单调栈和单调队列

单调栈

单调栈, 常用来求某一个数左边或右边离它最近且小于(大于)它的数。从这个题目还可以趁机说明一个问题, 在很多题目中while里面常常会有两个条件, 同时满足的话会执行某种操作。当跳出该循环时, 其中两个条件至少有一个不满足, 这时候会针对每一种条件不满足的情况做讨论。每个if语句里面又可以干一些事情。这里跳出while循环时, 有两种情况, 一种是左边没有比它小的数, 输出-1; 一种是找到了答案, 那就输出答案。

求数组中每一个数左边离它最近的数是哪一个代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], st[N];
int h = 0;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) scanf("%d ", &a[i]);
    for (int i = 0; i < n; i++) {
        // 栈顶元素小于a[i], 则栈中其它元素也小于a[i],
        while (h > 0 && st[h] >= a[i]) h--;   // 这是一个单调递增栈
        if (h == 0) printf("-1 ");
        else printf("%d ", st[h]);
        st[++h] = a[i];
    }
    return 0;
}

单调队列

单调队列, 本质上是一个双端队列。队列中存的是数据的下标。队头元素对应的a数组中的值是窗口中所有值中最小的。当滑动窗口的起始位置大于队头元素时。弹出队头元素, 让弹出后的队头元素代表的下标在滑动窗口范围之内。

求滑动窗口内的最大值代码如下: 

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

const int N = 1e6 + 5;
int q[N], a[N];
int h = 0, t = -1;  // 队头和队尾指针

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    for (int i = 0; i < n; i++) {

        /*以下三行代码就为维护单调队列的代码*/
        if (t >= h && i - k + 1 > q[h]) h++;  // 移动滑动窗口
        while (t >= h && a[q[t]] >= a[i]) t--; // 把队列中所有大于a[i]的数全部踢掉
        q[++t] = i;  // 入队

        if (i >= k - 1) printf("%d ", a[q[h]]);  // 当长度滑到k的时候才输出队头
    }
    printf("\n");
    h = 0, t = -1;  // 重新定义队列的头尾指针
    for (int i = 0; i < n; i++) {
        if (t >= h && i - k + 1 > q[h]) h++;
        while (t >= h && a[q[t]] <= a[i]) t--;
        q[++t] = i;
        if (i >= k - 1) printf("%d ", a[q[h]]);
    }

    return 0;
}

3. 循环双端队列

循环双端队列

需要注意的是循环队列的话, 是左闭右开区间, 和STL内置函数区间一样。

设计循环双端队列(力扣641)代码入下: 

class MyCircularDeque {
public:
    vector<int> q;
    int front = 0, rear = 0;  // 定义队头和队尾

    // 本题所设计的双端队列和vector容器一样也是左闭右开区间
    MyCircularDeque(int k) {
        q.resize(k + 1);  // 定义vector的长度, k + 1个长度表示 k 种状态
    }

    int mod(int num) {
        return (num + q.size()) % q.size();
    }

    bool insertFront(int value) {
        if (isFull()) return false;
        front = mod(front - 1);
        q[front] = value;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) return false;
        q[rear] = value;
        rear = mod(rear + 1);
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) return false;
        front = mod(front + 1);
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) return false;
        rear = mod(rear - 1);
        return true;
    }

    int getFront() {
        if (isEmpty()) return -1;
        return q[front];
    }

    int getRear() {
        if (isEmpty()) return -1;
        return q[mod(rear - 1)];
    }

    bool isEmpty() {
        return front == rear;
    }

    bool isFull() {
        return rear == mod(front - 1);
    }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */

4. 用队列模拟栈

比较麻烦的是实现pop函数。思路是把队列里面除最后一个元素外的所有元素全部弹出再压入。这样最后一个元素就到了队头, 也就是栈顶, 输出即可。

用队列模拟栈(力扣225)代码如下:

class MyStack {
public:
    queue<int> que;

    void push(int x) {
        que.push(x);
    }

    int pop() {
        int size = que.size();
        size--;
        while (size--) {
            que.push(que.front());
            que.pop();
        }
        int res = que.front();
        que.pop();
        return res;
    }

    int top() {
        return que.back();
    }

    bool empty() {
        return que.empty();
    }
};

5. 用栈模拟队列

用两个栈来实现这一操作。每次把数压入In栈中, 弹出时要看Out栈有没有元素, 有的话直接弹出栈顶, 否则把In栈中的所有元素全压入Out栈中。

用队列模拟栈(力扣232)代码如下:

class MyQueue {
public:
    stack<int> In;
    stack<int> Out;
    // MyQueue() {

    // }

    void push(int x) {
        In.push(x);
    }

    int pop() {
        if (Out.empty()) {
            while (!In.empty()) {
                Out.push(In.top());
                In.pop();
            }
        }
        int res = Out.top();
        Out.pop();
        return res;
    }

    int peek() {
        int res = this->pop();
        Out.push(res);
        return res;
    }

    bool empty() {
        return In.empty() && Out.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

0 评论

1024
x