「剑指Offer」Day01：栈与队列（简单）
剑指 Offer 09. 用两个栈实现队列
题目描述
思路
- 一个栈用于入栈，一个栈用于出栈
- 入栈时只需入栈到栈1，出栈时需判断栈1和栈2是否为空
- 若栈1和栈2都为空，返回-1；栈2不为空直接出栈，栈顶元素即为队头元素；
-
栈2为空，栈1不为空，需将栈1中元素全部出栈到栈2，此时之前先入的元素就会先出现在栈2的栈顶，满足队列先入先出的性质。
代码实现
class CQueue {
private Stack<Integer> stack1 = null;
private Stack<Integer> stack2 = null;
public CQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
if(stack2.isEmpty() && stack1.isEmpty()){ //都为空，队列无元素，返回-1
return -1;
}else if(!stack2.isEmpty()){ //栈2用于弹出队头元素，不为空直接弹出
return stack2.pop();
}else{ //栈2为空，栈1不为空时，需将栈1元素全部循环入栈，再弹出队头元素
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
}
剑指 Offer 30. 包含min函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
思路
入栈顺序：-2，0，-3，实际栈和最小栈如下，思路即为在入栈时维护最小栈的栈顶元素始终为当前栈中的最小值| -3 | | -3 |
| 0 | | -2 || -2 | | -2 |
代码实现
class MinStack {
/** initialize your data structure here. */
private Deque<Integer> stack;
private Deque<Integer> minStack;
public MinStack() {
stack = new LinkedList<>();
minStack = new LinkedList<>();
}
public void push(int x) {
if(stack.isEmpty()){
minStack.push(x);
}else{
//维护minStack栈顶元素为当前栈中的最小值
if(minStack.peek() < x){
minStack.push(minStack.peek());
}else{
minStack.push(x);
}
}
stack.push(x);
}
public void pop() { //一同出栈
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}
