美文网首页19-23年 学习笔记
【 数据结构 & 算法 】—— 栈、队列、堆

【 数据结构 & 算法 】—— 栈、队列、堆

作者: Du1in9 | 来源:发表于2020-10-15 16:40 被阅读0次

< 思维导图 >

预备知识：STL stack（堆）

预备知识：STL queue（队列）

使用队列实现栈（栈、队列）（★）

  • LeetCode 225.Implement Stack using Queues.cpp
#include <stdio.h>
#include <queue>

class MyStack {
private:
    // 新建数据队列
    std::queue<int> _data;
public:
    MyStack() {        
    }
    void push(int x) {
        // 新建临时队列
        std::queue<int> temp_queue;
        // 将新元素导入临时队列
        temp_queue.push(x);
        // 若数据队列不为空，导入临时队列
        while(!_data.empty()){ 
            temp_queue.push(_data.front());
            _data.pop();
        }
        // 若临时队列不为空，导入数据队列
        while(!temp_queue.empty()){
            _data.push(temp_queue.front());
            temp_queue.pop();
        }
    }
    // 弹出数据队列头部元素 
    int pop() {
        int x = _data.front();
        _data.pop();
        return x;
    }
    // 返回数据队列头部元素
    int top() {
        return _data.front();
    }
    // 返回数据队列是否为空 
    bool empty() {
        return _data.empty();
    }
};
int main(){
    MyStack S;
    S.push(1);
    S.push(2);
    S.push(3);
    S.push(4);
    // 4，3，2，1 
    printf("%d\n", S.top());
    S.pop();
    // 3，2，1 
    printf("%d\n", S.top());
    S.push(5);
    // 5，3，2，1 
    printf("%d\n", S.top());    
    return 0;
}

使用栈实现队列（栈、队列）（★）

  • LeetCode 232.Implement Queue using Stacks.cpp
#include <stdio.h>
#include <stack>
    
class MyQueue {
private:
    // 新建数据栈 
    std::stack<int> _data;
public:
    MyQueue() {
    }
    void push(int x) {
        // 新建临时栈 
        std::stack<int> temp_stack;
        // 若数据栈不为空，导入临时栈
        while(!_data.empty()){
            temp_stack.push(_data.top());
            _data.pop();
        }
        // 将新元素导入临时栈 
        temp_stack.push(x);
        // 若临时栈不为空，导入数据栈
        while(!temp_stack.empty()){
            _data.push(temp_stack.top());
            temp_stack.pop();
        }
    }
    // 弹出数据栈头部元素
    int pop() {
        int x = _data.top();
        _data.pop();
        return x;
    }
    // 返回数据栈头部元素
    int peek() {
        return _data.top();
    }
    // 返回数据栈是否为空
    bool empty() {
        return _data.empty();
    }
};
int main(){
    MyQueue Q;
    Q.push(1);
    Q.push(2);
    Q.push(3);
    Q.push(4);
    // 4，3，2，1 
    printf("%d\n", Q.peek());
    Q.pop();
    // 4，3，2
    printf("%d\n", Q.peek());   
    return 0;
}

包含 min 函数的栈（栈）（★）

  • LeetCode 155.MinStack.cpp
#include <stdio.h>
#include <stack>

class MinStack {
private:
    std::stack<int> _data;
    std::stack<int> _min;
public:
    MinStack() {
    }
    void push(int x) {
        // 将数据压入数据栈 
        _data.push(x);
        // 将数据压入最小值栈 
        if (_min.empty()){
            _min.push(x);
        }
        else{
            if (x > _min.top()){
                x = _min.top();
            }
            _min.push(x);
        }
    }
    // 两栈同时弹出顶端数据 
    void pop() {
        _data.pop();
        _min.pop();
    }
    // 返回数据栈顶端数据 
    int top() {
        return _data.top();
    }
    // 返回最小值栈顶端数据 
    int getMin() {
        return _min.top();
    }
};

int main(){
    MinStack minStack;
    minStack.push(-2);
    // -2 
    printf("top = [ %d ]\n", minStack.top());
    printf("min = [ %d ]\n\n", minStack.getMin());  
    minStack.push(0);
    // -2，0 
    printf("top = [ %d ]\n", minStack.top());
    printf("min = [ %d ]\n\n", minStack.getMin());
    minStack.push(-5);
    // -2，0，-5 
    printf("top = [ %d ]\n", minStack.top());
    printf("min = [ %d ]\n\n", minStack.getMin());
    minStack.pop();
    // -2，0 
    printf("top = [ %d ]\n", minStack.top());
    printf("min = [ %d ]\n\n", minStack.getMin());  
    return 0;
}

使用队列实现栈（栈、队列）（★★）

  • poj1363.cpp
#include <stdio.h>
#include <stack>
#include <queue>

// 检查队列 order 是否合法 
bool check_is_valid_order(std::queue<int> &order){
    // S 为模拟栈 
    std::stack<int> S;
    int n = order.size();
    for (int i = 1; i <= n; i++){
        // 将 1 到 n 依次压入栈 
        S.push(i);
        // 如果 S 不为空，且栈顶等于队列顶 
        while(!S.empty() && order.front() == S.top()){
            S.pop();
            order.pop();
        }
    }
    // 如果最后 S 不为空，则不合法 
    if (!S.empty()){
        return false;
    }
    // 如果最后 S 为空，则合法
    return true;
}

int main(){
    int n, train;
    // 输入队列长度 n 
    scanf("%d", &n); 
    std::queue<int> order; 
    // 输入元素 train，存入队列 order
    for (int i = 0; i < n; i++){
        scanf("%d", &train);
        order.push(train);
    }
    // 检查队列 order 是否合法
    if (check_is_valid_order(order)){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}

简单的计算器（栈）（★★★）

  • LeetCode 224.Basic Calculator.cpp
#include <stdio.h>
#include <string>
#include <stack>

class Solution {
private:
    // 带入数字和运算符进行计算 
    void compute(std::stack<int> &number_stack,
                 std::stack<char> &operation_stack){
        // 如果只有一个数字 
        if (number_stack.size() < 2){
            return;
        }
        // 取出、弹出数字 
        int num2 = number_stack.top();
        number_stack.pop();
        int num1 = number_stack.top();
        number_stack.pop();
        // 运算、弹出运算符 
        if (operation_stack.top() == '+'){
            number_stack.push(num1 + num2);
        }
        else if(operation_stack.top() == '-'){
            number_stack.push(num1 - num2);
        }
        operation_stack.pop();
    }
public:
    int calculate(std::string s) {
        static const int STATE_BEGIN = 0;
        static const int NUMBER_STATE = 1;
        static const int OPERATION_STATE = 2;
        std::stack<int> number_stack;
        std::stack<char> operation_stack;
        int number = 0;
        int STATE = STATE_BEGIN;
        int compuate_flag = 0;
        for (int i = 0; i < s.length(); i++){
            // 跳过空格字符 
            if (s[i] == ' '){
                continue;
            }
            switch(STATE){
            case STATE_BEGIN:
                // 若是字符 0123456789 
                if (s[i] >= '0' && s[i] <= '9'){
                    STATE = NUMBER_STATE;
                }
                // 若是字符 +-()
                else{
                    STATE = OPERATION_STATE;
                }
                i--;
                break;
            case NUMBER_STATE:
                // 字符数字转换为整型数字 
                if (s[i] >= '0' && s[i] <= '9'){
                    number = number * 10 + s[i] - '0';
                }
                //  存入数字 
                else{
                    number_stack.push(number);
                    if (compuate_flag == 1){
                        compute(number_stack, operation_stack);
                    }
                    number = 0;
                    i--;
                    STATE = OPERATION_STATE;
                }
                break;
            case OPERATION_STATE:
                // 存入运算符 
                if (s[i] == '+' || s[i] == '-'){
                    operation_stack.push(s[i]);
                    compuate_flag = 1;
                }
                // 改变运算开关 
                else if (s[i] == '('){
                    STATE = NUMBER_STATE;
                    compuate_flag = 0;
                }
                else if (s[i] == ')'){
                    compute(number_stack, operation_stack);
                }
                else if (s[i] >= '0' && s[i] <= '9'){
                    STATE = NUMBER_STATE;                   
                    i--;
                }
                break;
            }
        }
        // 返回最后运算结果 
        return number_stack.top();
    }
};
int main(){ 
    std::string s = "1+121 - (14+(5-6) )";
    Solution solve;
    printf("1+121-(14+(5-6)) = %d\n", solve.calculate(s));
    return 0;
}

预备知识：STL 优先级队列（二叉堆）

数组中第 K 大的数（堆）（★）

  • LeetCode 215.Kth Largest Element in an Array.cpp
#include <stdio.h>
#include <vector>
#include <queue>

class Solution {
public: 
    int findKthLargest(std::vector<int>& nums, int k) { 
        // 最小堆，堆顶为最小值 
        std::priority_queue<int, std::vector<int>, std::greater<int> > Q;
        // 遍历 nums 数组 
        for (int i = 0; i < nums.size(); i++){
            // 使堆里元素个数为 k  
            if (Q.size() < k){
                Q.push(nums[i]);
            }
            // 使堆里为数组最大的 k 个数 
            else if (Q.top() < nums[i]){ 
                Q.pop();
                Q.push(nums[i]);
            }
        }
        // 返回堆顶元素 
        return Q.top();
    }
};
int main(){
    std::vector<int> nums;
    nums.push_back(3);
    nums.push_back(2);
    nums.push_back(1);
    nums.push_back(5);
    nums.push_back(6);
    nums.push_back(4);
    Solution solve;
    printf("数组 [3, 2, 1, 5, 6, 4] 第 2 大的数为：%d\n", solve.findKthLargest(nums, 2));   
    return 0;
}

寻找中位数（堆）（★★★）

  • LeetCode 295.Find Median from Data Stream.cpp
#include <stdio.h>
#include <queue>

class MedianFinder {
private:
    // 最大堆构造 
    std::priority_queue<double, std::vector<double>, std::less<double> > big_queue;
    // 最小堆构造 
    std::priority_queue<double, std::vector<double>, std::greater<double> > small_queue;
public:
    MedianFinder() {
    }
    void addNum(double num) {
        // 如果最大堆空，push 到最大堆 
        if (big_queue.empty()){
            big_queue.push(num);
            return;
        }
        // 如果最大堆、最小堆个数相同 
        if (big_queue.size() == small_queue.size()){
            // 若小于最大堆堆顶，push 到最大堆 
            if (num < big_queue.top()){
                big_queue.push(num);
            }
            // 若大于最小堆堆顶，push 到最小堆 
            else{
                small_queue.push(num);
            }
        }
        // 如果最大堆个数 > 最小堆个数  
        else if(big_queue.size() > small_queue.size()){
            // 若大于最大堆堆顶，push 到最小堆
            if (num > big_queue.top()){
                small_queue.push(num);
            }
            // 若小于最大堆堆顶 
            else{
                // 最大堆堆顶 push 到最小堆堆顶 
                small_queue.push(big_queue.top());
                // 替换最大堆堆顶
                big_queue.pop();
                big_queue.push(num);
            }
        }
        // 如果最大堆个数 < 最小堆个数 
        else if(big_queue.size() < small_queue.size()){
            // 若小于最小堆堆顶，push 到最大堆
            if (num < small_queue.top()){
                big_queue.push(num);
            }
            // 若大于最小堆堆顶
            else{
                // 最小堆堆顶 push 到最大堆堆顶
                big_queue.push(small_queue.top());
                // 替换最小堆堆顶
                small_queue.pop();
                small_queue.push(num);
            }
        }
    }
    // 寻找中位数函数 
    double findMedian(){
        // 若两堆个数相同，返回平均数 
        if (big_queue.size() == small_queue.size()){
            return (big_queue.top() + small_queue.top()) / 2;
        }
        // 若最大堆个数多，返回最大堆堆顶 
        else if (big_queue.size() > small_queue.size()){
            return big_queue.top();
        }
        // 若最小堆个数多，返回最小堆堆顶
        return small_queue.top();
    }
};
int main(){
    MedianFinder M;
    double test[] = {1.2, 3.4, 4.5, 2.3, 5.6, 8.9};
    for (int i = 0; i < 6; i++){
        M.addNum(test[i]);
    }
    printf("数组 [1.2, 3.4, 4.5, 2.3, 5.6, 8.9] 的中位数为：%lf\n", M.findMedian());
    return 0;
}

相关文章

网友评论

    本文标题：【 数据结构 & 算法 】—— 栈、队列、堆

    本文链接：https://www.haomeiwen.com/subject/palbpktx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    19-23年 学习笔记

    关于我们|服务条款|联系我们|【 数据结构 & 算法 】—— 栈、队列、堆|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！