232. 用棧實現(xiàn)隊列

答案思路：

在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)棧和出棧都為空的話，說明模擬的隊列為空了。

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());}}
}

補充知識——Deque

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

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

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

方法

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

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

private static void usingAsQueue() {Deque<Integer> queue=new ArrayDeque<>();System.out.println("隊列為空:"+queue.isEmpty());   //判斷隊列是否為空queue.addLast(12);   //添加元素System.out.println("隊列為空:"+queue.isEmpty());   //判斷隊列是否為空System.out.println(queue.peekFirst());   //獲取隊列首部元素System.out.println(queue.pollFirst());   //獲取并移除棧頂元素System.out.println("隊列為空:"+queue.isEmpty());   //判斷隊列是否為空}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("============================================");