假设我们有两个堆栈,没有其他临时变量。

是否有可能“构造”一个队列数据结构只使用两个堆栈?


当前回答

public class QueueUsingStacks<T>
{
    private LinkedListStack<T> stack1;
    private LinkedListStack<T> stack2;

    public QueueUsingStacks()
    {
        stack1=new LinkedListStack<T>();
        stack2 = new LinkedListStack<T>();

    }
    public void Copy(LinkedListStack<T> source,LinkedListStack<T> dest )
    {
        while(source.Head!=null)
        {
            dest.Push(source.Head.Data);
            source.Head = source.Head.Next;
        }
    }
    public void Enqueue(T entry)
    {

       stack1.Push(entry);
    }
    public T Dequeue()
    {
        T obj;
        if (stack2 != null)
        {
            Copy(stack1, stack2);
             obj = stack2.Pop();
            Copy(stack2, stack1);
        }
        else
        {
            throw new Exception("Stack is empty");
        }
        return obj;
    }

    public void Display()
    {
        stack1.Display();
    }


}

对于每一个入队列操作,我们都将其添加到stack1的顶部。每次出队列时,我们都将stack1的内容清空到stack2中,并删除堆栈顶部的元素。出队列的时间复杂度是O(n),因为我们必须将stack1复制到stack2。队列的时间复杂度与常规堆栈相同

其他回答

不过,时间的复杂性会更糟。一个好的队列实现在常数时间内完成所有事情。

Edit

不知道为什么我的答案在这里被否决了。如果我们编程,我们会关心时间复杂度,使用两个标准堆栈来创建队列是低效的。这是一个非常有效和相关的观点。如果有人觉得有必要再投反对票,我很想知道为什么。

更详细一点:关于为什么使用两个堆栈比使用一个队列更糟糕:如果您使用两个堆栈,并且有人在发件箱为空时调用dequeue,则需要线性时间才能到达收件箱的底部(正如您可以在Dave的代码中看到的那样)。

您可以将队列实现为单链表(每个元素指向下一个插入的元素),保留一个额外的指针指向最后一个插入的元素进行推操作(或使其成为循环列表)。在此数据结构上实现队列和出队列非常容易,只需常数时间即可完成。这是最坏情况的常数时间,不是平摊。而且,正如注释中要求澄清的那样,最坏情况下常数时间严格来说比平摊常数时间要好。

您甚至可以只使用一个堆栈模拟一个队列。第二个(临时)堆栈可以通过对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();
    }
}

使用两个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();
        }

}

您必须从第一个堆栈中取出所有元素来获取底部元素。然后在每次“出队列”操作时将它们都放回第二个堆栈。

c#中的解决方案

public class Queue<T> where T : class
{
    private Stack<T> input = new Stack<T>();
    private Stack<T> output = new Stack<T>();
    public void Enqueue(T t)
    {
        input.Push(t);
    }

    public T Dequeue()
    {
        if (output.Count == 0)
        {
            while (input.Count != 0)
            {
                output.Push(input.Pop());
            }
        }

        return output.Pop();
    }
}