LeetCode演算法題-Implement Stack Using Queues
這是悅樂書的第193 次更新，第198 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第54題（順位題號是225）。使用佇列實現棧的以下操作：
push（x） - 將元素x推入棧。
pop（） - 刪除棧頂部的元素。
top（） - 獲取頂部元素。
empty（） - 返回棧是否為空。
例如：
MyStack stack = new MyStack（）;
stack.push（1）;
stack.push（2）;
stack.top（）; //返回2
stack.pop（）; //返回2
stack.empty（）; //返回false
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
藉助ArrayList。進棧利用list的add方法。出棧時先獲取list最後一位元素存起來，然後再刪除最後一位元素，再返回先前存起來的最後一位元素。獲取棧頂時，返回list最後一位元素即可。判空可以直接利用list的isEmpty方法。
class MyStack {
List<Integer> list = null;
/** Initialize your data structure here. */
public MyStack() {
list = new ArrayList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
list.add(x);
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
int top = list.get(list.size()-1);
list.remove(list.size()-1);
return top;
}
/** Get the top element. */
public int top() {
return list.get(list.size()-1);
}
/** Returns whether the stack is empty. */
public boolean empty() {
return list.isEmpty();
}
}
03 第二種解法
利用佇列。
進棧直接使用queue的add方法或者offer方法。
出棧時，因為佇列是先進先出的特性，所以需要先把佇列裡的元素poll出來再add進去，但是此操作只能進行queue的size-1次，比如：進棧順序是1->2->3，進行一次出佇列再進佇列操作後，2->3->1，再進行一次出佇列再進佇列的操作，3->1->2，如果你再操作一次就還原了，所以只能操作queue的size-1次。最後再使用佇列的poll方法，實現出棧。
棧頂，和出棧的思路一樣，不過在把佇列裡的元素poll出來再add進去size-1次後，先要將頂獲取到，可以直接使用佇列的peek方法，然後再來一次poll出來再add進去，就把佇列元素的順序還原了。方便下次操作。
判空可以直接使用佇列自身的isEmpty方法。
class MyStack2 {
Queue<Integer> queue = null;
int size ;
/** Initialize your data structure here. */
public MyStack2() {
queue = new LinkedList<Integer>();
size = 0;
}
/** Push element x onto stack. */
public void push(int x) {
queue.add(x);
size++;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
for (int i=1; i<size; i++) {
queue.add(queue.poll());
}
size--;
return queue.poll();
}
/** Get the top element. */
public int top() {
for (int i=1; i<size; i++) {
queue.add(queue.poll());
}
int res = queue.peek();
queue.add(queue.poll());
return res;
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}
04 第三種解法
還是使用佇列。不過此解法除了入棧重新實現外，其他的出棧、棧頂、判空都是使用了佇列的方法，所以重點講下入棧即可。
入棧時，首先利用佇列的add方法，然後利用迴圈，把佇列裡的元素poll出來再add進去，此迴圈只執行佇列的size-1次，執行size次會還原。
class MyStack3 {
Queue<Integer> queue = null;
/** Initialize your data structure here. */
public MyStack3() {
queue = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
queue.add(x);
for (int i=0; i<queue.size()-1; i++) {
queue.add(queue.poll());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.poll();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}
05 小結
演算法專題目前已連續日更超過一個月，演算法題文章54 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！