232. 用棧實(shí)現(xiàn)隊(duì)列

答案思路：

在push數(shù)據(jù)的時候，只要數(shù)據(jù)放進(jìn)輸入棧就好，但在pop的時候，操作就復(fù)雜一些，輸出棧如果為空，就把進(jìn)棧數(shù)據(jù)全部導(dǎo)入進(jìn)來（注意是全部導(dǎo)入），再從出棧彈出數(shù)據(jù)，如果輸出棧不為空，則直接從出棧彈出數(shù)據(jù)就可以了。

如果進(jìn)棧和出棧都為空的話，說明模擬的隊(duì)列為空了。

class MyQueue {Deque<Integer> inStack;Deque<Integer> outStack;public MyQueue() {inStack=new LinkedList<Integer>();outStack=new LinkedList<Integer>();}public void push(int x) {inStack.push(x);}public int pop() {if(outStack.isEmpty()){popInStack();}return outStack.pop();}public int peek() {if(outStack.isEmpty()){popInStack();}return outStack.peek();}public boolean empty() {return inStack.isEmpty()&&outStack.isEmpty();}public void popInStack(){while(!inStack.isEmpty()){outStack.push(inStack.pop());}}
}

補(bǔ)充知識——Deque

定義
雙向隊(duì)列：支持插入刪除元素的線性集合。
java官方文檔推薦用deque實(shí)現(xiàn)棧（stack）。

和Queue的區(qū)別
Deque是double ended queue，將其理解成雙端結(jié)束的隊(duì)列，雙端隊(duì)列，可以在首尾插入或刪除元素。
Queue的解釋中，Queue就是簡單的FIFO隊(duì)列。
所以在概念上來說，Queue是FIFO的單端隊(duì)列，Deque是雙端隊(duì)列。

特點(diǎn)
1.插入、刪除、獲取操作支持兩種形式：快速失敗和返回null或true/false
2.既具有FIFO特點(diǎn)又具有LIFO特點(diǎn)，即是隊(duì)列又是棧
3.不推薦插入null元素，null作為特定返回值表示隊(duì)列為空
4.未定義基于元素相等的equals和hashCode

方法

• addFirst(): 向隊(duì)頭插入元素，如果元素為空，則發(fā)生NPE(空指針異常)
• addLast(): 向隊(duì)尾插入元素，如果為空，則發(fā)生NPE
• offerFirst(): 向隊(duì)頭插入元素，如果插入成功返回true，否則返回false
• offerLast(): 向隊(duì)尾插入元素，如果插入成功返回true，否則返回false
• removeFirst(): 返回并移除隊(duì)頭元素，如果該元素是null，則發(fā)生NoSuchElementException
• removeLast(): 返回并移除隊(duì)尾元素，如果該元素是null，則發(fā)生NoSuchElementException
• pollFirst(): 返回并移除隊(duì)頭元素，如果隊(duì)列無元素，則返回null
• pollLast(): 返回并移除隊(duì)尾元素，如果隊(duì)列無元素，則返回null
• getFirst(): 獲取隊(duì)頭元素但不移除，如果隊(duì)列無元素，則發(fā)生NoSuchElementException
• getLast(): 獲取隊(duì)尾元素但不移除，如果隊(duì)列無元素，則發(fā)生NoSuchElementException
• peekFirst(): 獲取隊(duì)頭元素但不移除，如果隊(duì)列無元素，則返回null
• peekLast(): 獲取隊(duì)尾元素但不移除，如果隊(duì)列無元素，則返回null
• pop(): 彈出棧中元素，也就是返回并移除隊(duì)頭元素，等價于removeFirst()，如果隊(duì)列無元素，則發(fā)生NoSuchElementException
• push(): 向棧中壓入元素，也就是向隊(duì)頭增加元素，等價于addFirst()，如果元素為null，則發(fā)生NPE，如果?？臻g受到限制，則發(fā)生IllegalStateException

實(shí)現(xiàn)
ArrayDeque: 基于數(shù)組實(shí)現(xiàn)的線性雙向隊(duì)列，通常作為?；蜿?duì)列使用，但是棧的效率不如LinkedList高。
LinkedList: 基于鏈表實(shí)現(xiàn)的鏈?zhǔn)诫p向隊(duì)列，通常作為?；蜿?duì)列使用，但是隊(duì)列的效率不如ArrayQueue高。

private static void usingAsQueue() {Deque<Integer> queue=new ArrayDeque<>();System.out.println("隊(duì)列為空:"+queue.isEmpty());   //判斷隊(duì)列是否為空queue.addLast(12);   //添加元素System.out.println("隊(duì)列為空:"+queue.isEmpty());   //判斷隊(duì)列是否為空System.out.println(queue.peekFirst());   //獲取隊(duì)列首部元素System.out.println(queue.pollFirst());   //獲取并移除棧頂元素System.out.println("隊(duì)列為空:"+queue.isEmpty());   //判斷隊(duì)列是否為空}private static void usingAsStack() {//作為棧使用Deque<Integer> stack=new LinkedList<>();System.out.println("棧為空:"+stack.isEmpty());   //判斷棧是否為空stack.addFirst(12);System.out.println("棧為空:"+stack.isEmpty());   //判斷棧是否為空System.out.println(stack.peekFirst());   //獲取棧頂元素System.out.println(stack.pollFirst());   //獲取并移除棧頂元素System.out.println("棧為空:"+stack.isEmpty());   //判斷棧是否為空System.out.println("============================================");