題目描述
- [225]僅使用兩個棧實現(xiàn)先入先出隊列泵三。隊列應當支持一般隊列支持的所有操作（push、pop衔掸、peek烫幕、empty）
- [232]僅使用兩個隊列實現(xiàn)一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push敞映、top纬霞、pop 和 empty）
一、個人拙見
對比隊列與棧的特性區(qū)別驱显，一個是先進先出，一個是先進后出，然后埃疫，嗯~ o(￣▽￣)o伏恐！
用棧實現(xiàn)隊列
class MyQueue {
Stack<Integer> s1;
Stack<Integer> s2;
public MyQueue() {
s1 = new Stack<Integer>();
s2 = new Stack<Integer>();
}
/**
* Push element x to the back of queue.
*/
public void push(int x) {
s1.push(x);
}
/**
* Removes the element from in front of queue and returns that element.
*/
public int pop() {
peek();
return s2.pop();
}
/**
* Get the front element.
*/
public int peek() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
if (s2.isEmpty()) {
return -1;
} else {
return s2.peek();
}
}
/**
* Returns whether the queue is empty.
*/
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
用隊列實現(xiàn)棧
class MyStack {
Queue<Integer> q1, q2;
public MyStack() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
}
/**
* Push element x onto stack.
*/
public void push(int x) {
q1.add(x);
}
/**
* Removes the element on top of the stack and returns that element.
*/
public int pop() {
top();
return q1.remove();
}
/**
* Get the top element.
*/
public int top() {
if (q1.isEmpty()) {
while (!q2.isEmpty()) {
q1.add(q2.remove());
}
}
if (q1.isEmpty()) return -1;
while (q1.size() > 1) {
q2.add(q1.remove());
}
return q1.peek();
}
/**
* Returns whether the stack is empty.
*/
public boolean empty() {
return q1.isEmpty() && q2.isEmpty();
}
}
二、labuladong解答
作者：labuladong
這位大牛的方法栓霜，只用了一個隊列實現(xiàn)翠桦。確實，腦袋被前一道題限制了胳蛮，以為還是要用倆隊列销凑。。仅炊。
且用了個變量斗幼，存儲top
class MyStack {
Queue<Integer> q = new LinkedList<>();
int topElem = 0;
public void push(int x) {
// x 是隊列的隊尾，是棧的棧頂
q.offer(x);
topElem = x;
}
public int top() {
return topElem;
}
public int pop() {
int size = q.size();
// 留下隊尾 2 個元素
while (size > 2) {
q.offer(q.poll());
--size;
}
// 記錄新的隊尾元素
// 此時的位置即為刪除最后元素后的新的最后元素
topElem = q.peek();
q.offer(q.poll());
// 刪除之前的隊尾元素
return q.poll();
}
public boolean empty() {
return q.isEmpty();
}
}
三抚垄、官方解答
解法一蜕窿、兩個隊列
思路
為了滿足棧的特性，即最后入棧的元素最先出棧呆馁，在使用隊列實現(xiàn)棧時桐经，應滿足隊列前端的元素是最后入棧的元素≌懵耍可以使用兩個隊列實現(xiàn)棧的操作阴挣，其中 queue 1 用于存儲棧內的元素，queue 2 作為入棧操作的輔助隊列纺腊。
入棧操作時畔咧，首先將元素入隊到 queue 2 ，然后將 queue 1 的全部元素依次出隊并入隊到 queue 2 摹菠，此時 queue 2 的前端的元素即為新入棧的元素盒卸，再將 queue 1 和 queue 2 互換，則 queue 1 的元素即為棧內的元素次氨，queue 1 的前端和后端分別對應棧頂和棧底蔽介。
代碼
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
/** Initialize your data structure here. */
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
queue2.offer(x);
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll();
}
/** Get the top element. */
public int top() {
return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}
復雜度分析
- 時間復雜度：入棧操作 O(n)，其余操作都是 O(1)煮寡。
- 空間復雜度：O(n)虹蓄，其中 n 是棧內的元素。需要使用兩個隊列存儲棧內的元素幸撕。
解法二薇组、一個隊列
思路
使用一個隊列時，為了滿足棧的特性坐儿，即最后入棧的元素最先出棧律胀，同樣需要滿足隊列前端的元素是最后入棧的元素宋光。
入棧操作時，首先獲得入棧前的元素個數(shù) n炭菌，然后將元素入隊到隊列罪佳，再將隊列中的前 n 個元素（即除了新入棧的元素之外的全部元素）依次出隊并入隊到隊列，此時隊列的前端的元素即為新入棧的元素黑低，且隊列的前端和后端分別對應棧頂和棧底赘艳。
代碼
class MyStack {
Queue<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
queue = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
int n = queue.size();
queue.offer(x);
for (int i = 0; i < n; i++) {
queue.offer(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();
}
}
復雜度分析
- 時間復雜度：入棧操作 O(n)，其余操作都是 O(1)克握。
- 空間復雜度：O(n)蕾管，其中 n 是棧內的元素。需要使用一個隊列存儲棧內的元素菩暗。
