假设我们有两个堆栈，没有其他临时变量。
是否有可能“构造”一个队列数据结构只使用两个堆栈?
当前回答
我将在Go中回答这个问题，因为Go在其标准库中没有丰富的集合。
由于堆栈真的很容易实现，我想我应该尝试使用两个堆栈来完成一个双端队列。为了更好地理解我是如何得到我的答案的，我将实现分为两部分，第一部分希望更容易理解，但它是不完整的。
type IntQueue struct {
front []int
back []int
}
func (q *IntQueue) PushFront(v int) {
q.front = append(q.front, v)
}
func (q *IntQueue) Front() int {
if len(q.front) > 0 {
return q.front[len(q.front)-1]
} else {
return q.back[0]
}
}
func (q *IntQueue) PopFront() {
if len(q.front) > 0 {
q.front = q.front[:len(q.front)-1]
} else {
q.back = q.back[1:]
}
}
func (q *IntQueue) PushBack(v int) {
q.back = append(q.back, v)
}
func (q *IntQueue) Back() int {
if len(q.back) > 0 {
return q.back[len(q.back)-1]
} else {
return q.front[0]
}
}
func (q *IntQueue) PopBack() {
if len(q.back) > 0 {
q.back = q.back[:len(q.back)-1]
} else {
q.front = q.front[1:]
}
}
它基本上是两个堆栈，我们允许堆栈的底部相互操纵。我还使用了STL命名约定，其中堆栈的传统push、pop、peek操作都有一个front/back前缀，无论它们是指队列的前面还是后面。
上面代码的问题是它没有非常有效地使用内存。事实上，它会不断增长，直到空间耗尽。这太糟糕了。解决这个问题的方法是尽可能重用堆栈空间的底部。我们必须引入一个偏移量来跟踪这一点，因为围棋中的切片一旦收缩就不能在前面生长。
type IntQueue struct {
front []int
frontOffset int
back []int
backOffset int
}
func (q *IntQueue) PushFront(v int) {
if q.backOffset > 0 {
i := q.backOffset - 1
q.back[i] = v
q.backOffset = i
} else {
q.front = append(q.front, v)
}
}
func (q *IntQueue) Front() int {
if len(q.front) > 0 {
return q.front[len(q.front)-1]
} else {
return q.back[q.backOffset]
}
}
func (q *IntQueue) PopFront() {
if len(q.front) > 0 {
q.front = q.front[:len(q.front)-1]
} else {
if len(q.back) > 0 {
q.backOffset++
} else {
panic("Cannot pop front of empty queue.")
}
}
}
func (q *IntQueue) PushBack(v int) {
if q.frontOffset > 0 {
i := q.frontOffset - 1
q.front[i] = v
q.frontOffset = i
} else {
q.back = append(q.back, v)
}
}
func (q *IntQueue) Back() int {
if len(q.back) > 0 {
return q.back[len(q.back)-1]
} else {
return q.front[q.frontOffset]
}
}
func (q *IntQueue) PopBack() {
if len(q.back) > 0 {
q.back = q.back[:len(q.back)-1]
} else {
if len(q.front) > 0 {
q.frontOffset++
} else {
panic("Cannot pop back of empty queue.")
}
}
}
有很多小函数，但6个函数中有3个只是另一个的镜像。
其他回答
使用堆栈实现队列的以下操作。
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();
}
}
使用两个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();
}
}
// Two stacks s1 Original and s2 as Temp one
private Stack<Integer> s1 = new Stack<Integer>();
private Stack<Integer> s2 = new Stack<Integer>();
/*
* Here we insert the data into the stack and if data all ready exist on
* stack than we copy the entire stack s1 to s2 recursively and push the new
* element data onto s1 and than again recursively call the s2 to pop on s1.
*
* Note here we can use either way ie We can keep pushing on s1 and than
* while popping we can remove the first element from s2 by copying
* recursively the data and removing the first index element.
*/
public void insert( int data )
{
if( s1.size() == 0 )
{
s1.push( data );
}
else
{
while( !s1.isEmpty() )
{
s2.push( s1.pop() );
}
s1.push( data );
while( !s2.isEmpty() )
{
s1.push( s2.pop() );
}
}
}
public void remove()
{
if( s1.isEmpty() )
{
System.out.println( "Empty" );
}
else
{
s1.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
显然，这是一个很好的编码练习，因为它效率很低，但仍然很优雅。
这是我的解决方案在Java使用链表。
class queue<T>{
static class Node<T>{
private T data;
private Node<T> next;
Node(T data){
this.data = data;
next = null;
}
}
Node firstTop;
Node secondTop;
void push(T data){
Node temp = new Node(data);
temp.next = firstTop;
firstTop = temp;
}
void pop(){
if(firstTop == null){
return;
}
Node temp = firstTop;
while(temp != null){
Node temp1 = new Node(temp.data);
temp1.next = secondTop;
secondTop = temp1;
temp = temp.next;
}
secondTop = secondTop.next;
firstTop = null;
while(secondTop != null){
Node temp3 = new Node(secondTop.data);
temp3.next = firstTop;
firstTop = temp3;
secondTop = secondTop.next;
}
}
}
注意:在这种情况下，弹出操作非常耗时。因此，我不建议使用两个堆栈创建队列。
