栈&队列

一、栈&队列总结

• 栈/队列的应用
  • 接雨水
  • 验证栈序列
  • 滑动窗口的最大值
• 栈/队列的特殊实现
  • 用两个栈实现队列
  • 用两个队列实现栈
• 特殊栈/队列
  • 最大队
  • 最小栈

二、栈&队列题目

接雨水

题目描述：

方法1：暴力法

对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。

方法2：栈的应用

每遇到一次当前元素比栈顶元素大，说明可能有可以积水的坑；
弹出栈顶元素作为mid，当前元素为r，此时的栈顶元素为l，以此计算当前坑的容积。

int trap(vector<int>& height)
{
    int ans = 0;
    stack<int> st;
    for (int i = 0; i < height.size(); i++){
        while (!st.empty() && height[st.top()] < height[i]) {
            int mid = st.top(); st.pop();
            if (st.empty())
                break;
            
            int l = st.top(), r = i;
            int curWidth = r - l - 1;
            int curHeight = min(height[l], height[r]) - height[mid];
            ans += curWidth * curHeight;
        }
        st.push(i);
    }
    return ans;
}

验证栈序列

思路：
遍历pushed数组，在遍历的过程中将pushed数组元素压入栈中；
如果当前栈顶元素与poped数组索引j相同，循环弹出；
最后遍历完数组之后，查看索引j是否到达poped数组最后，如果没有，返回false。

class Solution {
public:
   bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
       stack<int> s;
       int j = 0;
       for(int i=0; i<pushed.size(); i++){
           s.push(pushed[i]);
           while (!s.empty() && s.top() == popped[j]) {
               j++;
               s.pop();
           }
       }
       if (j < popped.size()) {
           return false;
       }
       return true;
   }
};

滑动窗口的最大值

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res;
    deque<int> q; // 队列的队首元素 始终 指向滑动窗口最大的数
    q.push_back(0);
    for (int i=1; i<k; i++) {
        while (!q.empty() && nums[i] > nums[q.back()]) {
            q.pop_back();
        }
        q.push_back(i);
    }
    res.push_back(nums[q.front()]);
    
    for (int i=k; i<nums.size(); i++) {
        // 如果队首元素不在滑动窗口范围内
        if(i - q.front() == k){
            q.pop_front();
        }
        
        // 处理移动窗口的新数据
        while (!q.empty() && nums[i] > nums[q.back()]) {
            q.pop_back();
        }
        q.push_back(i);
        
        res.push_back(nums[q.front()]);
    }
    return res;
}

栈 & 队列的特殊实现

用栈实现队列

typedef struct {
    Stack* s1; // 负责进数据
    Stack* s2; // 负责出数据
} MyQueue;
MyQueue* myQueueCreate() {
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    q->s1 = createStack();
    q->s2 = createStack();
    return q;
}
bool myQueueEmpty(MyQueue* obj) {
    return isEmpty(obj->s1) && isEmpty(obj->s2);
}
void myQueuePush(MyQueue* obj, int x) {
    push(obj->s1, x);
}
int myQueuePop(MyQueue* obj) {
    if(myQueueEmpty(obj)){
        return INT_MIN;
    }

    if(isEmpty(obj->s2)){ 
        while(!isEmpty(obj->s1)){
            push(obj->s2, pop(obj->s1));
        }
    }

    return pop(obj->s2);
}

用队列实现栈

typedef struct {
    Queue* q1;
    Queue* q2;
} MyStack;
MyStack* myStackCreate() {
    MyStack* s = (MyStack*)malloc(sizeof(MyStack));
    s->q1 = createQueue();
    s->q2 = createQueue();
    return s;
}
void myStackPush(MyStack* obj, int x) {
    if (!isEmpty(obj->q1)) {
        enqueue(obj->q1, x);
    }else {
        enqueue(obj->q2, x);
    }
}
int myStackPop(MyStack* obj) {
    if (!isEmpty(obj->q1)) {
        while (obj->q1->size > 1) {
            enqueue(obj->q2, dequeue(obj->q1));
        }
        return dequeue(obj->q1);
    }else{
        while (obj->q2->size > 1) {
            enqueue(obj->q1, dequeue(obj->q2));
        }
        return dequeue(obj->q2);
    }
}

特殊栈 & 队列

最小栈

#define MAX 12048
typedef struct {
    int data[MAX];
    int top;
    int min[MAX];
} MinStack;

MinStack* minStackCreate() {
    MinStack* s = (MinStack*)malloc(sizeof(MinStack));
    s->top = -1;
    return s;
}
int minStackGetMin(MinStack* obj) {
    return obj->min[obj->top];
}
void minStackPush(MinStack* obj, int x) {
    if(obj->top == -1){
        obj->min[++obj->top] = x;
    }else{
        int curMinVal = minStackGetMin(obj);
        if (x < curMinVal) {
            obj->min[++obj->top] = x;
        }else{
            obj->min[++obj->top] = curMinVal;
        }
    }
    obj->data[obj->top] = x;
}
void minStackPop(MinStack* obj) {
    obj->top--;
}
int minStackTop(MinStack* obj) {
    return obj->data[obj->top];
}

void minStackFree(MinStack* obj) {
    free(obj);
}

class MinStack {
private:
    stack<int> data;
    stack<int> minStack; // 栈顶是最小值
public:
    MinStack() {
    }
    void push(int x) {
        data.push(x);
        if (minStack.empty() || x <= minStack.top()) {
            minStack.push(x);
        }
    }
    void pop() {
        if (minStack.top() == data.top()) {
            minStack.pop();
        }
        data.pop();
    }
    int top() {
        return data.top();
    }
    int getMin() {
        return data.top();
    }
};

最大队

class MaxQueue {
private:
    queue<int> que;
    deque<int> dq; // 队首是最大值
public:
    MaxQueue() {
    }
    
    int max_value() {
        if(dq.empty()) return -1;
        return dq.front();
    }
    
    void push_back(int value) {
        que.push(value);
        
        while (!dq.empty() && value > dq.back()) 
            dq.pop_back();
        dq.push_back(value);
    }
    
    int pop_front() {
        if(que.empty()) return -1;
        int val = que.front();
        que.pop();
        
        if (val == dq.front()) dq.pop_front();

        return val;
    }
};