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

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


当前回答

我的PHP解决方案

<?php
$_fp = fopen("php://stdin", "r");
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
    $queue = array();
    $count = 0;
    while($line = fgets($_fp)) {
        if($count == 0) {
            $noOfElement = $line;
            $count++;
            continue;
        }
        $action = explode(" ",$line);
        $case = $action[0];
        switch($case) {
            case 1:
                $enqueueValue = $action[1];
                array_push($queue, $enqueueValue);
                break;
            case 2:
                array_shift($queue);
                break;
            case 3:
                $show = reset($queue);
                print_r($show);
                break;
            default:
                break;
        }
    }
?>

其他回答

在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()!)
            }
        }
    }
}

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

使用堆栈实现队列的以下操作。

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();
  }
}

简单的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)

保持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();
    }

}