假设我们有两个堆栈,没有其他临时变量。
是否有可能“构造”一个队列数据结构只使用两个堆栈?
假设我们有两个堆栈,没有其他临时变量。
是否有可能“构造”一个队列数据结构只使用两个堆栈?
当前回答
在Swift中使用两个堆栈的队列实现:
struct Stack<Element> {
var items = [Element]()
var count : Int {
return items.count
}
mutating func push(_ item: Element) {
items.append(item)
}
mutating func pop() -> Element? {
return items.removeLast()
}
func peek() -> Element? {
return items.last
}
}
struct Queue<Element> {
var inStack = Stack<Element>()
var outStack = Stack<Element>()
mutating func enqueue(_ item: Element) {
inStack.push(item)
}
mutating func dequeue() -> Element? {
fillOutStack()
return outStack.pop()
}
mutating func peek() -> Element? {
fillOutStack()
return outStack.peek()
}
private mutating func fillOutStack() {
if outStack.count == 0 {
while inStack.count != 0 {
outStack.push(inStack.pop()!)
}
}
}
}
其他回答
使用O(1) dequeue(),这与pythonquick的答案相同:
// time: O(n), space: O(n)
enqueue(x):
if stack.isEmpty():
stack.push(x)
return
temp = stack.pop()
enqueue(x)
stack.push(temp)
// time: O(1)
x dequeue():
return stack.pop()
使用O(1) enqueue()(这在本文中没有提到,所以这个答案),它也使用回溯来冒泡并返回最底部的项。
// O(1)
enqueue(x):
stack.push(x)
// time: O(n), space: O(n)
x dequeue():
temp = stack.pop()
if stack.isEmpty():
x = temp
else:
x = dequeue()
stack.push(temp)
return x
显然,这是一个很好的编码练习,因为它效率很低,但仍然很优雅。
使用堆栈实现队列的以下操作。
push(x)——将元素x推到队列的后面。
pop()——从队列前面移除元素。
peek()——获取前端元素。
empty()——返回队列是否为空。
class MyQueue {
Stack<Integer> input;
Stack<Integer> output;
/** Initialize your data structure here. */
public MyQueue() {
input = new Stack<Integer>();
output = new Stack<Integer>();
}
/** Push element x to the back of queue. */
public void push(int x) {
input.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
peek();
return output.pop();
}
/** Get the front element. */
public int peek() {
if(output.isEmpty()) {
while(!input.isEmpty()) {
output.push(input.pop());
}
}
return output.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return input.isEmpty() && output.isEmpty();
}
}
您甚至可以只使用一个堆栈模拟一个队列。第二个(临时)堆栈可以通过对insert方法的递归调用的调用堆栈来模拟。
在队列中插入新元素时,原理保持不变:
您需要将元素从一个堆栈转移到另一个临时堆栈,以反转它们的顺序。 然后将要插入的新元素推入临时堆栈 然后将元素转移回原始堆栈 新元素将在堆栈的底部,而最老的元素在顶部(第一个被弹出)
一个Queue类只使用一个Stack,如下所示:
public class SimulatedQueue<E> {
private java.util.Stack<E> stack = new java.util.Stack<E>();
public void insert(E elem) {
if (!stack.empty()) {
E topElem = stack.pop();
insert(elem);
stack.push(topElem);
}
else
stack.push(elem);
}
public E remove() {
return stack.pop();
}
}
保持2个堆栈,让我们称之为收件箱和发件箱。
排队:
将新元素推到收件箱上
出列:
如果发件箱为空,则通过弹出收件箱中的每个元素并将其推入发件箱来重新填充它 弹出并返回发件箱中的顶部元素
使用这种方法,每个元素只在每个堆栈中存在一次——这意味着每个元素将被压入两次,弹出两次,从而给出平摊常数时间操作。
下面是Java中的实现:
public class Queue<E>
{
private Stack<E> inbox = new Stack<E>();
private Stack<E> outbox = new Stack<E>();
public void queue(E item) {
inbox.push(item);
}
public E dequeue() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
return outbox.pop();
}
}
使用两个java.util.Stack对象实现队列:
public final class QueueUsingStacks<E> {
private final Stack<E> iStack = new Stack<>();
private final Stack<E> oStack = new Stack<>();
public void enqueue(E e) {
iStack.push(e);
}
public E dequeue() {
if (oStack.isEmpty()) {
if (iStack.isEmpty()) {
throw new NoSuchElementException("No elements present in Queue");
}
while (!iStack.isEmpty()) {
oStack.push(iStack.pop());
}
}
return oStack.pop();
}
public boolean isEmpty() {
if (oStack.isEmpty() && iStack.isEmpty()) {
return true;
}
return false;
}
public int size() {
return iStack.size() + oStack.size();
}
}