栈和队列

本文主要是介绍栈和队列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• L232 用两个栈实现队列
• JS9 用两个栈实现队列
• L225 JO5 两个队列实现栈
• JS30 JO20最小栈设计：包含min函数的栈（使用非严格单调栈）
• JS59II 最大队列设计：使用单调队列（双向队列deque实现）
• JS31 JO21 栈的压入、弹出序列（辅助栈）
• L20 有效括号（字节常考!!!!!字符串+栈）

L232 用两个栈实现队列

#include<iostream>
#include<stack>
using namespace std;
// 用栈实现队列：使用两个栈——主栈和辅助栈
// 主栈顶——>队列头（弹出）；主栈底 <——队列尾（插入）
class MyQueue{
private:
    stack<int> myqueue;  // 主栈
public:
    MyQueue(){}
    // 队尾插入元素：将新元素放到栈低，没有返回值
    void push(int x){
        stack<int> tmp;
        // 将主栈中所有元素先搬到辅助栈
        while(!myqueue.empty()){
            tmp.push(myqueue.top());
            myqueue.pop();
        }
        // 将新元素压入主栈
        myqueue.push(x);
        // 将辅助栈的所有元素搬回主栈
        while(!tmp.empty()){
            myqueue.push(tmp.top());
            tmp.pop();
        }
    }
    // 弹出队头元素：将主栈顶元素弹出
    int pop(){
        int x = myqueue.top();
        myqueue.pop();
        return x;
    }
    /* 实际上弹出元素是没有返回值的
    void pop(){
        myqueue.pop();
    }
     */
    // 获得队头
    int front(){
        return myqueue.top();
    }
    // 判空
    bool empty(){
        return myqueue.empty();
    }
};
int main(){
    MyQueue que;
    que.push(1);
    que.push(2);
    que.push(3);
    cout << que.front() << endl;
    cout << que.empty() << endl;
    que.pop();
    cout << que.front() << endl;
    return 0;
}

JS9 用两个栈实现队列

class CQueue {
public:
    CQueue() {
    }
    
    void appendTail(int value) {
        stack<int> tmp;
        while(!myqueue.empty()){
            tmp.push(myqueue.top());
            myqueue.pop();
        }
        myqueue.push(value);
        while(!tmp.empty()){
            myqueue.push(tmp.top());
            tmp.pop();
        }
    }
    
    int deleteHead() {
        if(myqueue.empty()) return -1;
        int x = myqueue.top();
        myqueue.pop();
        return x;
    }
private:
    stack<int> myqueue;  // 主栈
};
/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

L225 JO5 两个队列实现栈

#include<iostream>
#include<queue>
using namespace std;
// 用队列实现栈：使用两个队列——主队列和辅助队列
// 主队列头——>栈顶（弹出）；主队列头 <——栈顶（插入）
class MyStack{
private:
    queue<int> mystack;
public:
    MyStack(){}
    // 栈顶插入元素：将新元素放到主队头，没有返回值
    void push(int x){
        queue<int> tmp;
        // 先将新元素进辅助队列
        tmp.push(x);
        // 然后将主队列中的元素搬到辅助队列
        while(!mystack.empty()){
            tmp.push(mystack.front());
            mystack.pop();
        }
        // 最后将辅助队列中的所有元素挪回主队列
        while(!tmp.empty()){
            mystack.push(tmp.front());
            tmp.pop();
        }
    }
    // 弹出栈顶元素
    void pop(){
        mystack.pop();
    }
    // 输出栈顶元素
    int top(){
        return mystack.front();
    }
    // 判断栈空
    bool empty(){
        return mystack.empty();
    }
};
int main(){
    MyStack stk;
    stk.push(1);
    stk.push(2);
    stk.push(3);
    cout << stk.top() << endl;
    cout << stk.empty() << endl;
    stk.pop();
    cout << stk.top() << endl;
    return 0;
}

JS30 JO20最小栈设计：包含min函数的栈（使用非严格单调栈）

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
// 最小栈的实现
class MinStack{
public:
    stack<int> mainstack, minstack;
    MinStack(){}
    // 入栈push
    void push(int x){
        // 入主栈
        mainstack.push(x);
        // 判断是否要入最小栈：最小栈为空或新元素小于最小栈栈顶元素
        if(minstack.empty() || x <= minstack.top()){
            minstack.push(x);
        }
    }
    // 出栈pop
    void pop(){
        // 判断最小栈是否要弹出元素:主栈栈顶元素与最小栈栈顶元素同
        if(mainstack.top() == minstack.top()){
            minstack.pop();
        }
        // 主栈弹出栈顶元素
        mainstack.pop();
    }
    // 获取栈顶元素
    int top(){
        return mainstack.top();
    }
    // 获得最小值
    int min(){
        return minstack.top();
    }
};
int main(){
    MinStack stk;
    stk.push(-2);
    stk.push(0);
    stk.push(-3);
    cout << stk.min()<< endl;
    stk.pop();
    cout << stk.top() << endl;
    cout << stk.min() << endl;
    return 0;
}

JS59II 最大队列设计：使用单调队列（双向队列deque实现）

#include<deque>
#incllude<queue>
using namespace std;
class MaxQueue {
    queue<int> mainque;
    deque<int> maxdeq;
public:
    MaxQueue() {
    }
    //当双向队列 deque 为空，则返回 -1 ；否则，返回 deque 首元素；
    int max_value() {
        return maxdeq.empty() ? -1 : maxdeq.front();
    }
    
    // （1）将元素 value 入队 queue
    // （2）将deque中队尾所有小于value的元素弹出（以保持 deque 非单调递减），并将元素 value 入队 deque
    void push_back(int value) {
        mainque.push(value);
        while(!maxdeq.empty() && value > maxdeq.back()){
            maxdeq.pop_back();
        }
        maxdeq.push_back(value);
    }
    //（1）若队列 queue 为空，则直接返回 -1；
    //（2）否则，将 queue 首元素出队；
    // (3) 若 deque 首元素和 queue 首元素 相等 ，则将 deque 首元素出队（以保持两队列 元素一致 ）
    int pop_front() {
        if(mainque.empty()) return -1;
        int val = mainque.front();
        if(val == maxdeq.front()){
            maxdeq.pop_front();
        }
        mainque.pop();
        return val;
    }
};
/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

JS31 JO21 栈的压入、弹出序列（辅助栈）

class Solution {
public:
/*
整体思路：
借用一个辅助栈 stack，模拟 压入 / 弹出操作的排列。根据是否模拟成功，即可得到结果。
复杂度：
时间复杂度：O(n)。 n 为入栈序列的长度
空间复杂度：O(n)。 辅助栈最多存储 n 个元素
算法流程
    • 建立一个辅助栈
    • 遍历入栈序列
    • 元素入栈
    • 若辅助栈栈顶元素等于弹出序列元素，则执行出栈操作
返回结果
*/
    // poped是弹出元素顺序
    // 逐个将pushed的元素压入栈，并判断该元素是否与poped的目前弹出元素相同，如果相同则从栈中又pop出该元素

    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> tmp;
        int index = 0; // popped当前弹出元素
        for(int i = 0; i< pushed.size(); ++i){
            tmp.push(pushed[i]);
            while(!tmp.empty()&&tmp.top()==popped[index]){
                tmp.pop();
                index++;
            }
        }
        return tmp.empty();
    }
};

L20 有效括号（字节常考!!!!!字符串+栈）

class Solution {
public:
    bool isValid(string s) {
        // 用栈检查括号有效性:
        if(s.size()%2 !=0) return false;  // 长度不是偶数，肯定出错
        stack<char> tmp;
        for(int i=0; i<s.size();++i){
            if(s[i]=='(' || s[i]=='{' || s[i]=='['){
                // 如果是左括号压入栈
                tmp.push(s[i]);
            }else if(s[i]==')'){
                if(tmp.empty() || tmp.top() != '(') return false;
                tmp.pop();
            }else if(s[i]=='}'){
                if(tmp.empty() || tmp.top() != '{') return false;
                tmp.pop();
            }else {
                if(tmp.empty() || tmp.top() != '[') return false;
                tmp.pop();
            }
        }
        // 左括号栈为空，则返回True，否则false
        return tmp.empty();

    }
};

这篇关于栈和队列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！