双栈实现队列操作
剑指offer09
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完
成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：
1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
思路
一个in_stack，一个out_stack模拟队列，进入队列时，直接压入in_stack，出队列时，如果out_stack非空，则直接out_stack直接pop，如果空，则将in_stack所有元素压入out_stack，再pop
代码实现
class CQueue {
public:
stack<int> stack_in;
stack<int> stack_out;
CQueue() {
}
void appendTail(int value) {
stack_in.push(value);
}
int deleteHead() {
int x=-1;
if(stack_out.empty())//出栈空，则入栈转入出栈再出
{
if(stack_in.empty())//均空则返回-1
{
return x;
}
while(!stack_in.empty())//入栈非空，则转入出栈
{
x=stack_in.top();
stack_in.pop();
stack_out.push(x);
}
}
x=stack_out.top();
stack_out.pop();
return x;
}
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/
实现包含查询最小值min的栈
剑指offer 30
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.
提示：
各函数的调用总次数不超过 20000 次
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof
思路
两个栈，一个正常存储comstack，一个用于存放最小值minstack，每次有入栈元素时，正常压入comstack，再与minstack栈顶元素对比，如果小于等于其，则压入minstack，因此保证了minstack是非严格递减的；出栈时，comstack正常pop，minstack如果栈顶元素和comstack一样，则也pop；min操作则直接minstack的top即可
代码实现
/*暴力土方法
class MinStack {
public:
// initialize your data structure here.
MinStack() {
}
vector<int> minstack;
int min_num;
int min_i=-1;
void push(int x) {
if(min_i==-1)//第一个压栈元素设为最小
{
min_num=x;
min_i=0;
}
else
{
if(x<min_num)
{
min_num=x;
min_i=minstack.size();//this line can delete
}
}
minstack.push_back(x);
}
void pop() {
minstack.pop_back();
}
int top() {
return minstack.back();
}
int min() {
vector<int>::iterator it=minstack.begin();
for(min_num=minstack.front();it!=minstack.end();it++)
{
if(*it<min_num)
{
min_num=*it;
min_i=it-minstack.begin();
}
}
return min_num;
}
};
*/
class MinStack{
public:
stack<int> comstack;//用于正常存储
stack<int> minstack;//用于存放最小值，非严格递减
MinStack(){
}
void push(int x){
comstack.push(x);
if(minstack.empty()||x<=minstack.top())//minstack空或者x比栈顶元素小，则压入minstack
{
minstack.push(x);
}
}
void pop() {
if(comstack.top()==minstack.top())
{
comstack.pop();
minstack.pop();
}
else
{
comstack.pop();
}
}
int top() {
return comstack.top();
}
int min() {
return minstack.top();
}
};
/**
* 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();
*/