232. Implement Queue using Stacks

Dhanaraj S

2 min readApr 2, 2022

Check out the problem description here.

Implement Queue using Stacks - LeetCode

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the…

leetcode.com

The general idea is to use 2 stack , one in which push is performed and another in which pop operation is performed.

Approach 1:

2Stack operation

We insert elements to stack1 as push operation is called. But when we need to get the front element or pop front element ,we pop all the elements from stack 1 and push to stack 2. Thus the stack 2 will contain the front element at the top. After popping this front element, we move them back to stack 1. And this is repeated.

class MyQueue:def __init__(self):
        self.stk1=[]
        self.stk2=[]
    
    def push(self, x: int) -> None:
        self.stk1.append(x)
        
    def pop(self) -> int:
        while(self.stk1):
            self.stk2.append(self.stk1.pop(-1))
        front = self.stk2.pop(-1)
        while(self.stk2):
            self.stk1.append(self.stk2.pop(-1))
            
        return frontdef peek(self) -> int:
        while(self.stk1):
            self.stk2.append(self.stk1.pop(-1))
        front = self.stk2[-1]
        while(self.stk2):
            self.stk1.append(self.stk2.pop(-1))
            
        return frontdef empty(self) -> bool:
        if  not self.stk1:
            return True
        return False

Time:

Pop :O(n)

Push: O(1)

Peek: O(n)

Space :

O(n)

Approach 2:

The question asks if the amortized time complexity can be made to O(1). So this approach is something which does the same.

Here when pop is called , we pop the values from stack2. If it is empty then we push all the element from stack 1 to 2 . At times when push operation is called, they are pushed to stack1.

Thus it ensures that pop is almost O(1).

class MyQueue:def __init__(self):
        self.stk1=[]
        self.stk2=[]
    
    def push(self, x: int) -> None:
        self.stk1.append(x)
        
    def pop(self) -> int:
        if not self.stk2:
            while(self.stk1):
                self.stk2.append(self.stk1.pop(-1))
        front = self.stk2.pop(-1)      
        return frontdef peek(self) -> int:
        if not self.stk2:
            while(self.stk1):
                self.stk2.append(self.stk1.pop(-1))
        front = self.stk2[-1]  
        return frontdef empty(self) -> bool:
        if  not self.stk1 and not self.stk2:
            return True
        return False