剑指offer—day1.用两个栈实现队列、包含min函数的栈

1.用两个栈实现队列

本题来源力扣

剑指 Offer 09. 用两个栈实现队列 - 力扣LeetCodehttps://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/题目描述 

用两个栈实现一个队列。队列的声明如下请实现它的两个函数 appendTail 和 deleteHead 分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素deleteHead 操作返回 -1 )

示例1

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

示例2

输入
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[  [],[],[5],[2],[],[]  ]
输出[null,-1,null,null,5,2]

示例解读

• CQueue为构造函数对类进行初始化但并不往里面加数据[ ]代表没有返回值
• appendTail在队尾增加元素没有返回值[ ]
• deleteHead删除队首元素若队内没有元素(示例2)则返回-1若有元素(示例1)则返回这个被删除的元素

 解题思路

由于队列先进先出的性质要确保最后的出栈操作时出栈顺序和入栈顺序一样要点

• 入栈操作不必过多关注
• 出栈操作是重点

具体过程如下

1. 准备两个栈(s1和s2)s1用于入数据s2用于出数据
2. 入数据时往s1入不用考虑其他
3. 出数据时先检查s2中有没有数据如果有则可以直接记录并出栈顶数据
4. 如果s2中没有数据检查s1如果s1中也没有数据返回-1
5. 如果s1中有数据则将s1中所有数据依次出栈并依次往s2入栈此时越晚在s1入栈的元素在s2中的位置就越接近栈底入栈越早的越在栈顶
6. 此时再重复步骤3

实现代码

class CQueue {
public:
    CQueue() {}
    
    void appendTail(int value) {  // 步骤2
        s1.push(value);
    }
    
    int deleteHead() {
        int ret;
        if(!s2.empty())   // 步骤3
        {
           ret = s2.top(); 
           s2.pop();
        }

        // no data in s2, check s1
        else                         // 步骤4
        {
            if(s1.empty())
            {
                return -1;  // if s1 is empty, there is no integer push ,return -1
            }

            // If there is data in s1the  will be exited and all will enter s2
            while(!s1.empty())        // 步骤5
            {
                int tmp = s1.top();
                s2.push(tmp);
                s1.pop();
            }

            ret = s2.top();          // 步骤6
            s2.pop();
        }

        return ret;
    }
private:
    // 步骤1
    stack<int> s1; // s1 is uesd to input integer
    stack<int> s2; // s2 is used to output integer
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

 

2. 包含min函数的栈

题目来源力扣

剑指 Offer 30. 包含min函数的栈 - 力扣LeetCodehttps://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/题目描述

定义栈的数据结构请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中调用 min、push 及 pop 的时间复杂度都是 O(1)

示例

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

解题思路

对于一个栈pop和push操作均为O(1)因此本题所考察的是如何实现O(1)的找最小值原生stack需要遍历时间复杂度为O(N)因此解题的思路是使用另外一个栈来动态保存栈的最小值

我们一共使用两个栈s1用于数据入栈s2用于存储当前栈的最小值有几点需要注意

• 每次入栈时都检查这个元素是否比s2的栈顶元素大如果是则说明s2的栈顶仍然保存s1中最小的那个元素此时这个元素就只往s1入栈不入s2。例如s1入栈顺序为231那么s2中入栈顺序为21
• 如果s1入栈顺序为211那么s2中需要将两个1全部入栈因为如果只入栈一个1那么s1pop()之后s2也要pop()此时s121 而s22就不匹配

具体过程如下

1. 准备两个栈(s1和s2)s1用于入数据s2用于动态保存s1中的最小值
2. 入栈时检查入栈元素和s2栈顶元素的大小(注意s2为空的情况)
3. 如果栈空或者入栈元素小于等于s2栈顶元素则s1和s2都入栈
4. 如果入栈元素大于s2栈顶元素则只入s1
5. 出栈时如果s1栈顶元素大于(这里只可能大于或者等于)s2栈顶元素则只出栈s1
6. 如果s1栈顶元素等于s2栈顶元素则s1和s2同时出栈
7. s2的栈顶一直保存s1的最小值故时间复杂度为O(1)

实现代码

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack()  {}
     
    void push(int x) {                    // 步骤2
        // if s2 is empty or the entered value isn't greater than the top element in s2,record it
        if(s2.empty() || s2.top() >= x)   // 步骤3
        {
            s1.push(x);
            s2.push(x);
        }

        // if the entered value is greater than the top element in s2, don't push it to s2 
        else                               // 步骤4   
        {
            s1.push(x); 
        }
    }
    
    // be careful when pop an elementcompare s1.top and s2.top firstly to check if it
    void pop() {                      
        if(s1.top() > s2.top()) // s1.top > s2.top, just pop s1  // 步骤5
        {
            s1.pop();
        }
        else                    // pop s1 and s2 both            // 步骤6
        {
            s1.pop();
            s2.pop();
        }
    }
    
    int top() {
        return s1.top();
    }
    
    int min() {                             // 步骤7
        return s2.top();
    }
 
private:                     // 步骤1
    stack<int> s1; // stack s1 is used store data
    stack<int> s2; // stack s2 is used to record the minimum element in s1
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */