Implementing queue using stack

Question

This is question from homework:

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.

What I did:

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

Analysis of the algorithm:

Running time of one Enqueue is Theta(1). Total running time of the all Enqueue functions is n * Theta(1) = Theta(n).

Running time of Dequeue in worst case scenario is Theta(n) (when you call it after the last Enqueue, i.e. when all the items inserted). In all other cases the running time is Theta(1).

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

Is this correct?

amit · Accepted Answer · 2015-07-14 17:11:37Z

1

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

You're in the right direction, but you usually don't analyze "total running time", you split it to amortized average, worst case, and best case - and analyze it for each operation.

In your algorithm, it is easy to see that:

enqueue() runs in Theta(1) for all cases.
dequeue() runs in Theta(n) worst case and Theta(1) best case.

Noe, for the tricky part - we need to analyzed dequeue() amortised analysis.

First, note that before each Theta(n) (worst case), dequeue() you must have emptied the list, and inserted n elements.
This means, in order for the worst case to happen, you must have done at least n enqueue() operations, each Theta(1).

This gives us amortised time of:

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

It is easy to see that T(n) is in Theta(1), giving you Theta(1) amortized time complexity.

tl;dr:

enqueue: Theta(1) all cases
dequeue: Theta(1) amortized, Theta(n) worst case

answered Jul 14, 2015 at 17:11

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

rici Over a year ago

A possibly simpler way of looking at it is that if you start and end with an empty q, every element will have been pushed and popped exactly once from each stack. One push obviously corresponds to the enqueue, so the other three operations correspond to the (total of) the dequeues.

Mohit Motiani · Accepted Answer · 2015-07-30 04:29:06Z

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

}

Girish Rathi · Accepted Answer · 2019-09-20 03:25:22Z

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue.

pop() -- Removes the element from in front of queue.

peek() -- Get the front element.

empty() -- Return whether the queue is 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();
  }
}

Collectives™ on Stack Overflow

Implementing queue using stack

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related