題目描述

• 經典題了，貌似現在面試也有點喜歡問，今天補補題！
• 要實現均攤時間復雜度O(1)噢
  

思路 & 代碼

• 用兩個棧來實現：輸出棧 & 輸入棧
• 輸出棧 out：負責 pop、peek
• 輸入棧 in：負責 push
• 關鍵點：in.size() + out.size() == MyQueue.size()，也就是隊列元素分布在兩個棧中
• peek & pop：會有一個倒棧處理，把 in 的內容全倒入 out 中。

/*** 要點：in.size() + out.size() == MyQueue.size() */class MyQueue {Stack<Integer> in;Stack<Integer> out;/** Initialize your data structure here. */public MyQueue() {in = new Stack<>();out = new Stack<>();}/** Push element x to the back of queue. */public void push(int x) {in.push(x);}/** Removes the element from in front of queue and returns that element. */public int pop() {// 出棧空，入棧導入if(out.isEmpty()){while(!in.isEmpty()){out.push(in.pop());}}return out.pop();}/** Get the front element. */public int peek() {if(out.isEmpty()){while(!in.isEmpty()){out.push(in.pop());}}return out.peek();}/** Returns whether the queue is empty. */public boolean empty() {return in.isEmpty() && out.isEmpty();} }/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

更新版

• 換成 ArrayDeque()

class MyQueue {ArrayDeque<Integer> in;ArrayDeque<Integer> out;public MyQueue() {in = new ArrayDeque<>();out = new ArrayDeque<>();}public void push(int x) {in.push(x);}public int pop() {if(out.isEmpty()) {while(!in.isEmpty()) {out.push(in.pop());}}return out.pop();}public int peek() {if(out.isEmpty()) {while(!in.isEmpty()) {out.push(in.pop());}}return out.peek();}public boolean empty() {return in.isEmpty() && out.isEmpty();} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】232. 用栈实现队列（Java、栈、队列）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。