Can you implement a queue using stacks?

I can explain how to implement a queue using two stacks in Python. There are two ways two achieve it. The first one is by making ‘enqueue‘ operation costly and the second one is by making ‘dequeue‘ operation costly.

### Method 1: Making ‘enqueue‘ operation costly This method makes ensure that the oldest entered element is always at the top of stack 1, so that ‘dequeue‘ operation just pops from stack 1. To put an element at top of stack1, stack 2 is used.

Here is the algorithm:

1. ‘Enqueue(q, x)‘ operation’s step are described below:

- While stack1 is not empty, push everything from satck1 to stack2.

- Push x to stack1 (assuming size of stacks is unlimited).

- Push everything back to stack1.

2. ‘Dequeue(q)‘ operation’s function are described below:

- If stack1 is empty then error

- Pop an item from stack1 and return it

class Queue:
    def __init__(self):
        self.s1 = []
        self.s2 = []

    def enqueue(self, x):
        # Move all elements from s1 to s2 
        while len(self.s1) != 0:  
            self.s2.append(self.s1[-1])  
            self.s1.pop()
        
        # Push item into s1
        self.s1.append(x)  

        # Push everything back to s1
        while len(self.s2) != 0:
            self.s1.append(self.s2[-1])  
            self.s2.pop()

    def dequeue(self):
        # if first stack is empty
        if len(self.s1) == 0:  
            print("Queue is Empty")
        else:
            return self.s1.pop()  # pop the first item

### Method 2: Making ‘dequeue‘ operation costly In this method, in ‘enqueue‘ operation, the new element is entered at the top of stack1. In ‘dequeue‘ operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.

1. ‘Enqueue(q, x)‘

- Push x to stack1 (assuming size of stacks is unlimited).

2. ‘Dequeue(q)‘

- If both stacks are empty then error.

- If stack2 is empty. While stack1 is not empty, push everything from stack1 to stack2.

- Pop the element from stack2 and return it.

Here is the Python code implementing the above idea.

class Queue:
    def __init__(self):
        self.s1 = []
        self.s2 = []

    def enqueue(self, x):
        self.s1.append(x)

    def dequeue(self):
        # if first stack is empty
        if len(self.s1) == 0 and len(self.s2) == 0:
            print("Queue is Empty")
        elif len(self.s2) == 0 and len(self.s1) > 0:
            while len(self.s1):
                temp = self.s1.pop()
                self.s2.append(temp)
            return self.s2.pop()
        else:
            return self.s2.pop()

We can test this queue implementation as follows:

q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)

print(q.dequeue())
print(q.dequeue())
print(q.dequeue())

It will output ‘1 2 3‘ as expected.