Queue with 2 Stacks – Python

Problem – Implement a Queue with two Stacks

Language used: Python

Notes:
Queue is a FIFO DS and supports two methods: Enqueue and Dequeue
Enqueue -> Adds an item to the Queue
DeQueue -> Removed an item from the Queue
Stack is a LIFO DS and supports two methods: PUSH and POP
PUSH -> Adds an item to the top of the stack
POP -> Removes the item at the top of the stack

I will use the following algorithm:
1. PUSH the item to the stack1 using the Enqueue method of the
2. When item needs to be Dequeued, POP the items from stack1 and PUSH all but the last one to stack2
3. POP the last item in stack 1; this is the first item inserted in the stack and in the spirit of
Queue’s FIFO attribute, needs to be the item returned via dequeue.
4. PUSH the items in stack2 back into stack1

Python specific nuts and bolts: I used Python Lists as stacks. Note Lists can be directly used as queue too
”’

class QueueWith2Stack
   list1 = list()
   list2 = list()
   # Add an item to our queue
   def enq(item):
      list1.append(item)
   # Return an item from the queue
   def deq():
      for k in list1[1:]:
         list2.append(k)
         list1.remove(k)
         list1.pop()
      for k in list2:
         list1.append(k)
         list2[:]=[]

Working through a programming refresher in Udemy – the program is quite good!

Advertisements