1.用两个栈实现队列

本题来源：力扣

剑指 Offer 09. 用两个栈实现队列 - 力扣（LeetCode）https://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) {  // 步骤2s1.push(value);}int deleteHead() {int ret;if(!s2.empty())   // 步骤3{ret = s2.top(); s2.pop();}// no data in s2, check s1else                         // 步骤4{if(s1.empty()){return -1;  // if s1 is empty, there is no integer push ,return -1}// If there is data in s1，the  will be exited and all will enter s2while(!s1.empty())        // 步骤5{int tmp = s1.top();s2.push(tmp);s1.pop();}ret = s2.top();          // 步骤6s2.pop();}return ret;}
private:// 步骤1stack s1; // s1 is uesd to input integerstack 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函数的栈 - 力扣（LeetCode）https://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入栈顺序为2，3，1，那么s2中入栈顺序为2，1
• 如果s1入栈顺序为2，1，1，那么s2中需要将两个1全部入栈，因为如果只入栈一个1，那么s1pop()之后，s2也要pop()，此时s1：2，1 而s2：2，就不匹配

具体过程如下

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 itif(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 element，compare s1.top and s2.top firstly to check if itvoid 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() {                             // 步骤7return s2.top();}private:                     // 步骤1stack s1; // stack s1 is used store datastack 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();*/