使用栈实现队列

Question

这是作业中的问题：

Implement a FIFO queue using two stacks.

The total running time of Enqueue and Dequeue functions should be O(n) in the worst case scenario. Also, analyze the running time of the algorithm.

我做了什么：

void Enqueue(T *value)
{
s1.Push(value);
}

T *Dequeue()
{
    if (s2.size > 0)
        return s2.Pop();
    else if (s1.size > 0)
    {
        for (int i = 0; i < s1.size; i++)
            s2.Push(s1.Pop());

        return s2.Pop();
    }
    else return NULL;
}

算法分析：

运行一个Enqueue的时间是Theta(1)。所有 Enqueue 函数的总运行时间为 n * Theta(1) = Theta(n)。

运行 Dequeue 在最坏情况下的时间是 Theta(n)（当您在最后一次 Enqueue 之后调用它时，即当所有项目都插入时）。在所有其他情况下，运行时间为 Theta(1).

因此，总运行时间为： O(n) + O(n) + n * O(1) = 3 * O(n) = O(n)

这是正确的吗？

Answer 1

So, the total running time is: O(n) + O(n) + n * O(1) = 3 * O(n) = O(n)

您的方向是正确的，但您通常不分析 "total running time"，而是将其拆分为摊销平均值、最坏情况和最佳情况 - 并针对每个操作进行分析。

在你的算法中，很容易看出：

enqueue() 在所有情况下都在 Theta(1) 中运行。
dequeue() 在 Theta(n) 最坏情况和 Theta(1) 最好情况下运行。

不，对于棘手的部分 - 我们需要分析 dequeue() 摊销分析。

首先，请注意在每个 Theta(n)（最坏情况）之前，dequeue() 必须清空列表，并插入 n 元素。
这意味着，为了使最坏的情况发生，您必须至少进行 n enqueue() 次操作，每次 Theta(1).

这为我们提供了摊销时间：

T(n) = (n*CONST1      +    CONST2*n)             /(n+1)
          ^                 ^                      ^
     n enqueues      1 "espansive" dequeue        #operations

很容易看出 T(n) 在 Theta(1) 中，给你 Theta(1) 摊销时间复杂度。

tl;博士：

入队：Theta(1) 所有情况
出队：Theta(1) 摊销，Theta(n) 最坏情况

Answer 2

导入java.util.Stack；

public class Q5_ImplementQueueUsingStack {

/**
 * @param args
 * Implement a MyQueue class which implements a queue using two stacks.
 */
public static Stack<Integer> s1 = new Stack<Integer>();
public static Stack<Integer> s2 = new Stack<Integer>();
public static void main(String[] args) {
    int[] array = {2,5,10,3,11,7,13,8,9,4,1,6};
    for(int i=0;i<5;i++){
        enQueue(array[i]);
    }
    System.out.println(deQueue());
    System.out.println(deQueue());
    System.out.println(deQueue());
    System.out.println(deQueue());
    System.out.println(deQueue());
    for(int i=0;i<4;i++){
        enQueue(array[i+5]);
    }
    System.out.println(deQueue());
    for(int i=0;i<3;i++){
        enQueue(array[i+9]);
    }
    System.out.println(deQueue());
    System.out.println(deQueue());
    System.out.println(deQueue());
    System.out.println(deQueue());
    System.out.println(deQueue());
    System.out.println(deQueue());
}
public static void enQueue(int data){
    s1.push(data);
}
public static int deQueue(){
    if(s2.isEmpty())
        while(!s1.isEmpty()) 
            s2.push(s1.pop());
    return s2.pop();
}

}

Answer 3

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

push(x) -- 将元素 x 推到队列的后面。

pop() -- 从队列前面移除元素。

peek() -- 获取最前面的元素。

empty() -- Return队列是否为空。

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

使用栈实现队列

Implementing queue using stack

algorithm

queue

stack

time-complexity