題目一：設(shè)計一個帶有g(shù)etMin功能的棧
[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();
}
}
解法二：兩個棧，壓入時當(dāng)前數(shù)小于等于棧頂元素才壓入耕突，彈出時當(dāng)前棧頂大于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);//為了和后面統(tǒng)一起來
}
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;
}
}
題目二 兩個棧實現(xiàn)隊列
兩個棧data help，只要注意兩點
１. help為空的時候才能往里面導(dǎo)數(shù)上祈。
- 導(dǎo)數(shù)就要把data中的所有數(shù)都導(dǎo)完培遵。
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();
}
}
題目三 兩個隊列實現(xiàn)棧
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();
}
}
題目四 僅使用遞歸實現(xiàn)棧的逆序
有利于對于遞歸的理解
要求只使用遞歸實現(xiàn)一個棧的逆序
思路：
假如不限條件浙芙，要實現(xiàn)一個棧的逆序，那么我們直接借助一個棧就可以實現(xiàn)了荤懂，這里不能再顯試的使用棧茁裙，那么我們就使用遞歸來利用系統(tǒng)的遞歸棧來實現(xiàn)。
這里首先思考getAndRemoveLast這個遞歸函數(shù)节仿，用于得到一個棧的棧底元素晤锥，并且刪除設(shè)個棧底元素。然后現(xiàn)在我們在每次遞歸返回的時候把之前保留的元素加到棧中廊宪，就可以實現(xiàn)逆序矾瘾。
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;
}
}
