LeetCode[232] Implement Queue using Stacks

Implement the following operations of a queue using stacks.

  • push(x) – Push element x to the back of queue.
  • pop() – Removes the element from in front of queue.
  • peek() – Get the front element.
  • empty() – Return whether the queue is empty.

Notes:

You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.

Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.

You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

分析:

这题跟LeetCode[225] Implement Stack using Queues相反。

两种方案:

方案 A :

可以用两个栈 a 和 b 来实现队列。其中,push()都在栈 a 中进行,pop()和 peek()都在栈 b 中进行。如果b中没有元素可以 pop()或 peek(),则依次从 a 中 pop()出来并 push()到 b 中。

若 a 和 b 均为空则该队列为空。

方案 B :

也是用两个栈。其中栈 temp 是用来辅助使栈 queue 维持与入栈时相反的顺序。如入栈顺序为 1、2、3、4、5 ,最终栈 queue 维持的顺序为 5、4、3、2、1 。这样就可以在栈 queue 上直接 pop()和 peek()了。

代码:

方案 A :

public class MyQueue {
Stack<Integer> a = new Stack<Integer>();
Stack<Integer> b = new Stack<Integer>();
/** Initialize your data structure here. */
public MyQueue() {
}
/** Push element x to the back of queue. */
public void push(int x) {
a.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (b.empty()) {
while (!a.empty()) {
b.push(a.pop());
}
}
return b.pop();
}
/** Get the front element. */
public int peek() {
if (b.empty()) {
while (!a.empty()) {
b.push(a.pop());
}
}
return b.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return a.empty() && b.empty() ? true : false;
}
}

方案 B :

public class MyQueue {
Stack<Integer> queue = new Stack<Integer>();
Stack<Integer> temp = new Stack<Integer>();
/** Initialize your data structure here. */
public MyQueue() {
}
/** Push element x to the back of queue. */
public void push(int x) {
while (!queue.empty()) {
temp.push(queue.pop());
}
queue.push(x);
while (!temp.empty()) {
queue.push(temp.pop());
}
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
return queue.pop();
}
/** Get the front element. */
public int peek() {
return queue.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return queue.empty();
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :