题目一：设计一个带有getMin功能的栈
[leetcode155]https://leetcode.com/problems/min-stack/
解法一：两个栈，其中help栈压入的都是最小值，同步压入，同步弹出,最省时间
public class MinStack {
Stack<Integer> data;
Stack<Integer> help;
/** initialize your data structure here. */
public MinStack() {
data=new Stack<Integer>();
help=new Stack<Integer>();
}
public void push(int x) {
if(data.isEmpty()){
data.push(x);
help.push(x);
}else{
data.push(x);
help.push(Math.min(help.peek(),x));
}
}
public void pop() {
if(data.isEmpty())
throw new RuntimeException("your stack is rmpty");
data.pop();
help.pop();
}
public int top() {
if(data.isEmpty())
throw new RuntimeException("your stack is rmpty");
return data.peek();
}
public int getMin() {
return help.peek();
}
}
解法二：两个栈，压入时当前数小于等于栈顶元素才压入，弹出时当前栈顶大于help栈顶才弹出，省了一些空间
public class MinStack {
Stack<Integer> data;
Stack<Integer> help;
/** initialize your data structure here. */
public MinStack() {
data=new Stack<Integer>();
help=new Stack<Integer>();
}
public void push(int x) {
if(data.isEmpty()){
data.push(x);
help.push(x);
}else{
data.push(x);
if(x<=help.peek())
help.push(x);
}
}
public void pop() {
// if(data.isEmpty())
// throw new RuntimeException("your stack is rmpty");
int cur=data.peek();
data.pop();
if(cur==help.peek())
help.pop();
}
public int top() {
// if(data.isEmpty())
// throw new RuntimeException("your stack is rmpty");
return data.peek();
}
public int getMin() {
return help.peek();
}
}
方法三：只使用一个栈，另外使用一个变量来记录最小，栈中压入的是与最小值的差。
public class MinStack {
private long min;
Stack<Long> stack;
/** initialize your data structure here. */
public MinStack() {
stack=new Stack<Long>();
}
public void push(int x) {
if(stack.isEmpty()){
min=x;
stack.push(0L);//为了和后面统一起来
}
else{
stack.push(x-min);
if(x<min)
min=x;
}
}
public void pop() {
if(stack.isEmpty())
return;
long pop=stack.pop();
if(pop<0)
min=min-pop;
}
public int top() {
long peek=stack.peek();
if(peek>0)
return (int)(min+peek);
else
return (int)min;
}
public int getMin() {
return (int)min;
}
}
题目二 两个栈实现队列
两个栈data help，只要注意两点
１. help为空的时候才能往里面导数。
- 导数就要把data中的所有数都导完。
class MyQueue {
Stack<Integer> data=new Stack<Integer>();
Stack<Integer> help=new Stack<Integer>();
// Push element x to the back of queue.
public void push(int x) {
data.push(x);
}
// Removes the element from in front of queue.
public void pop() {
if(help.isEmpty()&&data.isEmpty())
throw new RuntimeException("your queue is empty");
else if(help.isEmpty()){
while(!data.isEmpty())
help.push(data.pop());
}
help.pop();
}
// Get the front element.
public int peek() {
if(help.isEmpty()&&data.isEmpty())
throw new RuntimeException("your stack is empty");
else if(help.isEmpty()){
while(!data.isEmpty())
help.push(data.pop());
}
return help.peek();
}
// Return whether the queue is empty.
public boolean empty() {
return help.isEmpty()&&data.isEmpty();
}
}
题目三 两个队列实现栈
class MyStack {
Queue<Integer> data=new LinkedList<Integer>();
Queue<Integer> help=new LinkedList<Integer>();
// Push element x onto stack.
public void push(int x) {
data.add(x);
}
// Removes the element on top of the stack.
public void pop() {
if(data.isEmpty())
throw new RuntimeException("your stack is empty!");
while(data.size()!=1){
help.add(data.poll());
}
data.poll();
while(!help.isEmpty()){
data.add(help.poll());
}
}
// Get the top element.
public int top() {
if(data.isEmpty())
throw new RuntimeException("your stack is empty!");
while(data.size()!=1){
help.add(data.poll());
}
int tmp=data.peek();
help.add(data.poll());//小心这里
while(!help.isEmpty()){
data.add(help.poll());
}
return tmp;
}
// Return whether the stack is empty.
public boolean empty() {
return data.isEmpty();
}
}
题目四 仅使用递归实现栈的逆序
有利于对于递归的理解
要求只使用递归实现一个栈的逆序
思路：
假如不限条件，要实现一个栈的逆序，那么我们直接借助一个栈就可以实现了，这里不能再显试的使用栈，那么我们就使用递归来利用系统的递归栈来实现。
这里首先思考getAndRemoveLast这个递归函数，用于得到一个栈的栈底元素，并且删除设个栈底元素。然后现在我们在每次递归返回的时候把之前保留的元素加到栈中，就可以实现逆序。
public static void reverse(Stack<Integer> stack){
if(stack.isEmpty())
return;
int i=getAndRemoveLast(stack);
reverse(stack);
stack.push(i);
}
public static int getAndRemoveLast(Stack<Integer> stack){
int res=stack.pop();
if(stack.isEmpty()){
return res;
}
else{
int last=getAndRemoveLast(stack);
stack.push(res);
return last;
}
}
