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

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


当前回答

下面是使用ES6语法的javascript语言解决方案。

Stack.js

//stack using array
class Stack {
  constructor() {
    this.data = [];
  }

  push(data) {
    this.data.push(data);
  }

  pop() {
    return this.data.pop();
  }

  peek() {
    return this.data[this.data.length - 1];
  }

  size(){
    return this.data.length;
  }
}

export { Stack };

QueueUsingTwoStacks.js

import { Stack } from "./Stack";

class QueueUsingTwoStacks {
  constructor() {
    this.stack1 = new Stack();
    this.stack2 = new Stack();
  }

  enqueue(data) {
    this.stack1.push(data);
  }

  dequeue() {
    //if both stacks are empty, return undefined
    if (this.stack1.size() === 0 && this.stack2.size() === 0)
      return undefined;

    //if stack2 is empty, pop all elements from stack1 to stack2 till stack1 is empty
    if (this.stack2.size() === 0) {
      while (this.stack1.size() !== 0) {
        this.stack2.push(this.stack1.pop());
      }
    }

    //pop and return the element from stack 2
    return this.stack2.pop();
  }
}

export { QueueUsingTwoStacks };

用法如下:

index.js

import { StackUsingTwoQueues } from './StackUsingTwoQueues';

let que = new QueueUsingTwoStacks();
que.enqueue("A");
que.enqueue("B");
que.enqueue("C");

console.log(que.dequeue());  //output: "A"

其他回答

简单的JS解决方案**

注:我从其他人的评论中获得了一些想法

/* enQueue(q, x) 1) Push x to stack1 (assuming size of stacks is unlimited). deQueue(q) 1) If both stacks are empty then error. 2) If stack2 is empty While stack1 is not empty, push everything from stack1 to stack2. 3) Pop the element from stack2 and return it. */ class myQueue { constructor() { this.stack1 = []; this.stack2 = []; } push(item) { this.stack1.push(item) } remove() { if (this.stack1.length == 0 && this.stack2.length == 0) { return "Stack are empty" } if (this.stack2.length == 0) { while (this.stack1.length != 0) { this.stack2.push(this.stack1.pop()) } } return this.stack2.pop() } peek() { if (this.stack2.length == 0 && this.stack1.length == 0) { return 'Empty list' } if (this.stack2.length == 0) { while (this.stack1.length != 0) { this.stack2.push(this.stack1.pop()) } } return this.stack2[0] } isEmpty() { return this.stack2.length === 0 && this.stack1.length === 0; } } const q = new myQueue(); q.push(1); q.push(2); q.push(3); q.remove() console.log(q)

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

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

Edit

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

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

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

队列中的两个堆栈定义为stack1和stack2。

排队: euqueued的元素总是被推入stack1

出列: stack2的顶部可以被弹出,因为它是在stack2不为空时插入队列的第一个元素。当stack2为空时,我们从stack1中弹出所有元素,并将它们逐个推入stack2。队列中的第一个元素被压入stack1的底部。由于它位于stack2的顶部,所以在弹出和推入操作后可以直接弹出。

下面是相同的c++示例代码:

template <typename T> class CQueue
{
public:
    CQueue(void);
    ~CQueue(void);

    void appendTail(const T& node); 
    T deleteHead();                 

private:
    stack<T> stack1;
    stack<T> stack2;
};

template<typename T> void CQueue<T>::appendTail(const T& element) {
    stack1.push(element);
} 

template<typename T> T CQueue<T>::deleteHead() {
    if(stack2.size()<= 0) {
        while(stack1.size()>0) {
            T& data = stack1.top();
            stack1.pop();
            stack2.push(data);
        }
    }


    if(stack2.size() == 0)
        throw new exception("queue is empty");


    T head = stack2.top();
    stack2.pop();


    return head;
}

这个解决方案是从我的博客中借来的。我的博客网页上有详细的操作模拟分析。

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

}