Stack先進(jìn)后出声离，常用函數(shù)3P: peek push pop
Queue先進(jìn)先出，常用函數(shù)POP: peek offer poll
注意瘫怜，Stack是一個(gè)Class术徊，而Queue在Java里是interface，一般用LinkedList實(shí)現(xiàn)鲸湃。
1. 最小棧
設(shè)計(jì)含返回棧中最小數(shù)的函數(shù)的棧赠涮，要求時(shí)間復(fù)雜度為O(1)。
做法是使用一個(gè)記錄最小值的棧暗挑，每層的元素對(duì)應(yīng)原棧相同層截止最小的元素笋除。
public class MinStack {
Stack<Integer> stack;
Stack<Integer> min;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<Integer>();
min = new Stack<Integer>();
}
public void push(int x) {
if(stack.empty() || x < min.peek()){
min.push(x);
}else{
min.push(min.peek());
}
stack.push(x);
}
public void pop() {
stack.pop();
min.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min.peek();
}
}
2. 兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列
讓一個(gè)棧實(shí)現(xiàn)隊(duì)列的順序，就是在每插入一個(gè)元素時(shí)炸裆，把元素插到棧底垃它，即為隊(duì)尾。這時(shí)候就需要用到一個(gè)輔助棧來記錄原棧成員烹看，實(shí)現(xiàn)原棧的修復(fù)国拇。
如果一個(gè)棧的元素一個(gè)個(gè)跳出同時(shí)另一個(gè)棧不停把元素push進(jìn)去，那么另一個(gè)棧的跳出順序就會(huì)反過來惯殊，就會(huì)變成隊(duì)列的順序酱吝，而另一個(gè)棧再進(jìn)行一個(gè)個(gè)跳出讓原棧一個(gè)個(gè)push，原棧的順序變回跟以前一樣土思。
還有一個(gè)類似的思路是务热，push不變毕源，原棧還是保持棧的順序，只是跳出時(shí)跳棧底的元素陕习。
public class MyQueue {
Stack<Integer> queue;
/** Initialize your data structure here. */
public MyQueue() {
queue = new Stack<Integer>();
}
/** Push element x to the back of queue. */
public void push(int x) {
Stack<Integer> temp = new Stack<Integer>();
while(!queue.empty()){
temp.push(queue.pop());
}
temp.push(x);
while(!temp.empty()){
queue.push(temp.pop());
}
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
return queue.pop();
}
/** Get the front element. */
public int peek() {
return queue.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return queue.empty();
}
}
3. 兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧
public class MyStack {
Queue<Integer> stack;
/** Initialize your data structure here. */
public MyStack() {
stack = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
Queue<Integer> temp = new LinkedList<Integer>();
while(stack.peek() != null){
temp.offer(stack.poll());
}
stack.offer(x);
while(temp.peek() != null) {
stack.offer(temp.poll());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return stack.poll();
}
/** Get the top element. */
public int top() {
return stack.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return stack.peek() == null;
}
}
4. 出棧入棧合理性
輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序址愿，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序该镣。
這里就用一個(gè)棧來儲(chǔ)存和模擬壓入和彈出的過程。按照壓入順序依次壓入元素進(jìn)棧响谓，如果發(fā)現(xiàn)棧頂元素剛好是當(dāng)前彈出元素损合，說明此時(shí)發(fā)生一次彈出，棧彈出一個(gè)元素且彈出數(shù)組后移一位娘纷。整個(gè)過程結(jié)束后(遍歷完pushA后)嫁审，如果棧為空且popA也遍歷完，則說明合理赖晶；反之不合理律适。
（P.S.之前代碼思路有誤但牛客網(wǎng)上仍然通過遏插，說明盼婊撸客網(wǎng)測(cè)試用例設(shè)計(jì)得不夠全面。幸得朋友指出胳嘲。）
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA == null || popA == null) return false;
Stack<Integer> stack = new Stack<Integer>();
int j = 0;
for(int i = 0; i < pushA.length; i++){
stack.push(pushA[i]);
while(!stack.isEmpty() && stack.peek() == popA[j]){
stack.pop();
j++;
}
}
return (stack.isEmpty() && popA.length == j);
}
