【从零开始学算法】day1 - 剑指offer学习计划

林不二 lv.1

发布时间：2023-08-18 11:52:34 351

剑指 Offer 09. 用两个栈实现队列

题目链接

题解

class CQueue {
private:
    stack<int> stack1, stack2;
public:
    CQueue() {}

    void appendTail(int value) {
        stack1.push(value);
    }

    int deleteHead() {
        if (stack2.empty()) {
            if (stack1.empty()) {
                return -1;
            }
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int value = stack2.top();
        stack2.pop();
        return value;
    }
};

解析

题目要求用栈实现队列，具体指的是在队尾加整数和在头部删除元素两个操作

如果将栈底看作队列的头部，栈顶看作队列的尾部，那么对于向队尾添加整数，可以直接使用栈的push方法对于在头部删除元素，栈并没有提供删除栈底元素的方法，需要添加一个辅助栈，即stack2 将stack1中的元素依次push到stack2中，stack2便成为了原先stack1的翻转，再进行stack2.pop就能实现删除至于将stack2重新装回stack1不在本题考虑范围内

补充与小结

作为学习计划的第一题，却看了官方题解后才写出来，刚上手对于输入输出都没看明白

输入：
["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
[[],[3],[],[],[]]
输出：[null,null,3,-1,-1]

在这里下面的数组是CQueue原始的模样，上面的数组是输入的命令而输出就是每输入一条命令，输出一个值

stack1和stack2定义在private中，通过成员函数访问

剑指 Offer 30. 包含min函数的栈

题目链接

题解

class MinStack {
    stack<int> stack1,stack2;
public:
    /** initialize your data structure here. */
    MinStack() {
        stack2.push(INT_MAX);
    }
    
    void push(int x) {
        stack1.push(x);
        stack2.push(::min(stack2.top(),x));
    }
    
    void pop() {
        stack1.pop();
        stack2.pop();
    }
    
    int top() {
        return stack1.top();
    }
    
    int min() {
        return stack2.top();
    }
};

解析

本题需要利用栈实现一个能返回栈中最小整数的函数

相对于重新从栈中查找，也可以设置一个辅助栈stack2用于存放每次入栈时最小的数即stack2.push(min(new,old))，之后在stack1元素出栈的同时，stack2中元素也出栈，保持二者的个数一致以及保证stack2栈顶的元素总是stack1中最小的元素

补充与小结

这题难度相较第一题较低

需要注意的就是要在构造函数中初始化stack2，INT_MAX是整型常量，表示最大整数

文章来源： https://blog.51cto.com/u_15796459/5731487

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。