Queue Using Two Stacks
You will be given ‘Q’ queries. You need to implement a queue using two stacks according to those queries. Each query will belong to one of these three types:

1 ‘X’: Enqueue element ‘X’ into the end of the nth queue. Returns true after the element is enqueued. 2: Dequeue the element at the front of the nth queue. Returns -1 if the queue is empty, otherwise, returns the dequeued element.

Note:

Enqueue means adding an element to the end of the queue, while Dequeue means removing the element from the front of the queue.

Input Format:

The first line of input contains an integer ‘Q’ denoting the number of queries. The next ‘Q’ lines specify the type of operation/query to be performed on the data structure. Each query contains an integer ‘P’ denoting the type of query. For query of type 1, the integer ‘P’ is equal to 1 and it is followed by one integer ‘X’ denoting the element on which operation is to be performed. For query of type 2, the integer ‘P’ is equal to 2 which dequeues the element.

Output Format:

For each query, return the output returned after performing the corresponding operation on the data structure.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given functions.

Constraints:

1

Question

Queue Using Two Stacks

You will be given ‘Q’ queries. You need to implement a queue using two stacks according to those queries. Each query will belong to one of these three types:

1 ‘X’: Enqueue element ‘X’  into the end of the nth queue. Returns true after the element is enqueued.

2: Dequeue the element at the front of the nth queue. Returns -1 if the queue is empty, otherwise, returns the dequeued element.

Note:

Enqueue means adding an element to the end of the queue, while Dequeue means removing the element from the front of the queue.

Input Format:

The first line of input contains an integer ‘Q’ denoting the number of queries. 

The next ‘Q’ lines specify the type of operation/query to be performed on the data structure.

Each query contains an integer ‘P’ denoting the type of query.

For query of type 1, the integer ‘P’ is equal to 1 and it is followed by one integer ‘X’ denoting the element on which operation is to be performed.

For query of type 2, the integer ‘P’ is equal to 2 which dequeues the element.

Output Format:

For each query, return the output returned after performing the corresponding operation on the data structure.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given functions.

Constraints:

1 <= Q <= 10^5 
1 <= P <= 2
1 <= X <= 10^5

Time limit: 1 sec

Accepted Answer

Making the Enqueue operation costly

In this approach, we make sure that the oldest element added to the queue stays at the top of the stack, the second oldest below it and so on. To achieve this, we will need two stacks.

First stack('STK1') is the main stack being used to store the data, while the second stack('STK2') is to assist and store data temporarily during various operations.

Following steps will be involved while enqueuing a new element to the queue:

If the queue is empty(means 'STK1' is empty), directly push the first element onto the stack 'STK1'.
If the queue is not empty:
- move all the elements present in the first stack('STK1') to the second stack('STK1'), one by one.
- Then add the new element to the first stack, then move back all the elements from the second stack back to the first stack.
Doing so will always maintain the right order of the elements in the stack, with the 1st data element staying always at the top, with the 2nd data element right below it and the new data element will be added to the bottom.

This makes removing an element from the queue very simple, all we have to do is call the pop() method for stack 'STK1'.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the size of the queue.

Since we are using two stacks where each stack stores at max ‘N’ elements, so the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the size of the queue.

Push operation: O(N)

Since we have to empty the whole elements of ‘STK1’ into ‘STK2’ and back again to ‘STK1’, it takes O(N) time.

Pop operation: O(1)

Since we just need to pop the top element of the stack which takes O(1) time.

Java (SE 1.8)

/*
	Time complexity: O(N) 
	Space Complexity: O(N)
	
	Where 'N' is the size of the queue.
*/

import java.util.Stack;

class Queue {
	private Stack stk1, stk2;

	public Queue() {
		stk1 = new Stack();
		stk2 = new Stack();
	}

	// Enqueues 'X' into the queue. Returns true after enqueuing.
	public boolean enqueue(int value) {
		// Move all elements from 1st stack to the 2nd.
		while (!stk1.isEmpty()) {
			// Push top element of 1st stack into second.
			stk2.push(stk1.peek());

			// Pop out the pushed element.
			stk1.pop();
		}
		// Push item into 1st stack.
		stk1.push(value);

		// Move every element back to 1st stack.
		while (!stk2.isEmpty()) {
			// Push top of 2nd stack into first.
			stk1.push(stk2.peek());

			// pop out the pushed element.
			stk2.pop();
		}
		// Return true as element pushed.
		return true;
	}

	/*
	  Dequeues top element from queue. Returns -1 if the queue is empty, 
	  otherwise returns the popped element.
	*/
	public int dequeue() {
		// If first stack is empty.
		if (stk1.isEmpty()) {
			// Queue is empty.
			return -1;
		}

		// Return top element of the 1st stack.
		int value = stk1.peek();

		// Pop out the top element.
		stk1.pop();

		// Return popped element.
		return value;
	}
};

Python (3.5)

"""
    Time complexity: O(N) 
    Space Complexity: O(N)
    
    Where 'N' is the size of the queue.
"""

class Queue:
    def __init__(self):
        self.stk1 = []
        self.stk2 = []
    
    # Enqueues 'X' into the queue. Returns true after enqueuing.
    def enqueue(self, X):
        # Move all elements from 1st stack to the 2nd.
        while (len(self.stk1) > 0):  
        	# Pop out the element.
            temp = self.stk1.pop(); 

            # Push top element of 1st stack into second.
            self.stk2.append(temp) 
         
        # Push item into 1st stack.
        self.stk1.append(X) 
  		
        # Move every element back to 1st stack .
        while (len(self.stk2) > 0): 
        	# Pop out the pushed element.
            temp = self.stk2.pop()

            # Push top of 2nd stack into first .
            self.stk1.append(temp)
         
        # Return true as element pushed.
        return True
    
    """
      Dequeues top element from queue. Returns -1 if the queue is empty, 
      otherwise returns the popped element.
    """
    def dequeue(self):
        # If first stack is empty .
        if (len(self.stk1) == 0): 
            # Queue is empty .
            return -1
         
        # Return top element of the 1st stack and pop it.
        X = self.stk1.pop() 

        # Return popped element.
        return X

C++ (g++ 5.4)

/*
    Time complexity: O(N) 
    Space Complexity: O(N)
    
    Where 'N' is the size of the queue.
*/

class Queue{
    stack stk1, stk2;
    public:
    
    // Enqueues 'X' into the queue. Returns true after enqueuing.
    bool enqueue(int X){
        // Move all elements from 1st stack to the 2nd.
        while (!stk1.empty()) { 
            // Push top element of 1st stack into second.
            stk2.push(stk1.top()); 

            // Pop out the pushed element.
            stk1.pop(); 
        } 
        // Push item into 1st stack.
        stk1.push(X); 
  		
        // Move every element back to 1st stack .
        while (!stk2.empty()) {
            // Push top of 2nd stack into first .
            stk1.push(stk2.top()); 

            // Pop out the pushed element.
            stk2.pop(); 
        } 
        // Return true as element pushed.
        return true;
    }

    /*
      Dequeues top element from queue. Returns -1 if the queue is empty, 
      otherwise returns the popped element.
    */
    int dequeue(){
        // If first stack is empty .
        if (stk1.empty()) {
            // Queue is empty .
            return -1;
        } 

        // Return top element of the 1st stack .
        int X = stk1.top(); 

        // Pop out the top element.
        stk1.pop(); 

        // Return popped element.
        return X; 
    }
};

Accepted Answer

Making the dequeue operation costly

In this approach, we insert a new element onto the stack 'STK1' simply by calling the push() function, but doing so will push our first element towards the bottom of the stack, as we insert more elements to the stack.

But we want the first element to be removed first. Hence in the dequeue operation, we will have to use the second stack 'STK2'.

The steps are as follows:

If the queue is empty(means 'STK1' is empty), then we return an error message saying, the queue is empty.
If the queue is not empty:
- move all the elements present in the first stack('STK1') to the second stack('STK2'), one by one.
- Then remove the element at the top from the second stack, and then move back all the elements from the second stack to the first stack.
The purpose of moving all the elements present in the first stack to the second stack is to reverse the order of the elements, because of which the first element inserted into the queue, is positioned at the top of the second stack, and all we have to do is call the pop() function on the second stack to remove the element.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the size of the queue.

Since we are using two stacks where each stack stores at max ‘N’ elements, so the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the size of the queue.

Push operation: O(1)

Since we are just pushing the element at the top of the stack.

Pop operation: O(N)

Since we have to empty the whole elements of 'STK1' into 'STK2'.

C++ (g++ 5.4)

/*
    Time complexity: O(N) 
    Space Complexity: O(N)
    
    Where 'N' is the size of the queue.
*/

class Queue{
    stack stk1, stk2;
    public:

    // Enqueues 'X' into the queue. Returns true after enqueuing.
    bool enqueue(int X){
        // Simply push the value into the 1st stack.
        stk1.push(X);

        // Return true as element pushed.
        return true;
    }

    // Dequeues top element from queue. Returns -1 if the queue is empty, otherwise returns the popped element..
    int dequeue(){
        // Check if both the stacks are empty .
        if (stk1.empty() && stk2.empty()){ 
            // Queue is empty.
            return -1; 
        } 
  
        // If 2nd stack is empty, move elements from 1st stack to 2nd .
        if (stk2.empty()){ 
            // Until stack is empty.
            while (!stk1.empty()){ 
                // Push top element of 1st stack into 2nd stack.
                stk2.push(stk1.top()); 

                // Pop out the pushed element.
                stk1.pop(); 
            } 
        } 
        // Store the top element of 2nd stack into a variable.
        int X = stk2.top(); 

        // Pop out the elemnt.
        stk2.pop(); 

        // Return the popped element.
        return X; 
    }
};

Python (3.5)

"""
    Time complexity: O(N) 
    Space Complexity: O(N)
    
    Where 'N' is the size of the queue.
"""

class Queue:
    def __init__(self):
        self.stk1 = []
        self.stk2 = []

    # Enqueues 'X' into the queue. Returns true after enqueuing.
    def enqueue(self, X):
        # Simply push the value into the 1st stack.
        self.stk1.append(X)

        # Return true as element pushed.
        return True
    
    # Dequeues top element from queue. Returns -1 if the queue is empty, otherwise returns the popped element..
    def dequeue(self):
        # Check if both the stacks are empty .
        if (len(self.stk1) == 0 and len(self.stk2) == 0): 
            # Queue is empty.
            return -1
        
        # If 2nd stack is empty, move elements from 1st stack to 2nd .
        if (len(self.stk2) == 0): 
            # Until stack is empty.
            while (len(self.stk1) > 0):
                # Pop out the pushed element.
                temp = self.stk1.pop()

                # Push top element of 1st stack into 2nd stack.
                self.stk2.append(temp)
  
        # Store the top element of 2nd stack into a variable and pop it.
        X = self.stk2.pop() 

        # Return the popped element.
        return X

Java (SE 1.8)

/*
	Time complexity: O(N) 
	Space Complexity: O(N)
	
	Where 'N' is the size of the queue.
*/

import java.util.Stack;

class Queue {
	private Stack stk1, stk2;

	public Queue() {
		stk1 = new Stack();
		stk2 = new Stack();
	}

	// Enqueues 'X' into the queue. Returns true after enqueuing.
	public boolean enqueue(int value) {
		// Simply push the value into the 1st stack.
		stk1.push(value);

		// Return true as element pushed.
		return true;
	}
	/*
	   Dequeues top element from queue. Returns -1 if the queue is empty, 
	   otherwise returns the popped element.
	*/
	public int dequeue() {
		// Check if both the stacks are empty.
		if (stk1.isEmpty() && stk2.isEmpty()) {
			// Queue is empty.
			return -1;
		}

		// If 2nd stack is empty, move elements from 1st stack to 2nd.
		if (stk2.isEmpty()) {
			// Until stack is empty.
			while (!stk1.isEmpty()) {
				// Push top element of 1st stack into 2nd stack.
				stk2.push(stk1.peek());

				// pop out the pushed element.
				stk1.pop();
			}
		}

		// Store the top element of 2nd stack into a variable.
		int value = stk2.peek();

		// Pop out the elemnt.
		stk2.pop();

		// Return the popped element.
		return value;
	}
};

You will be given ‘Q’ queries. You need to implement a queue using two stacks according to those queries. Each query will belong to one of these three types:

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Springworks Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Springworks Software Developer Intern