Implement a queue using two stacks in Python
algorithms pythonA queue is a First-In-First-Out linear data structure, i.e., the element that is first inserted into the queue is the element that comes out first. The operation that involves inserting an element into the queue is called enqueue. The operation that involves removing an element from the queue is called dequeue. Normally, a queue is implemented using an array and two pointers; front and rear. This makes the time complexity of enqueue and dequeue operations O(1).
In this snippet, we will instead look at implementing a queue using a stack. This may increase the time complexity of the enqueue or dequeue operations, but the idea here is to see how such an implementation will look like. A stack is a Last-In-First-Out linear data structure. Here the last element inserted into the stack is the first element that comes out of the stack. It has push and pop operations where push inserts the element into the stack and pop removes the last inserted element from the stack.
Let’s try to implement a queue using two stacks in Python. We will use Python’s list data structure as the two stacks. The list data structure has a pop operation and the list’s append operation is anologous to push.
import unittest
class QueueTwoStacks(object):
# Implement the enqueue and dequeue methods
def __init__(self):
self.in_stack = []
self.out_stack = []
def enqueue(self, item):
self.in_stack.append(item)
def dequeue(self):
if len(self.out_stack) == 0:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
if len(self.out_stack) == 0:
raise Exception('queue is empty')
return self.out_stack.pop()
class Test(unittest.TestCase):
def test_basic_queue_operations(self):
queue = QueueTwoStacks()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
actual = queue.dequeue()
expected = 1
self.assertEqual(actual, expected)
actual = queue.dequeue()
expected = 2
self.assertEqual(actual, expected)
queue.enqueue(4)
actual = queue.dequeue()
expected = 3
self.assertEqual(actual, expected)
actual = queue.dequeue()
expected = 4
self.assertEqual(actual, expected)
def test_error_when_dequeue_from_new_queue(self):
queue = QueueTwoStacks()
with self.assertRaises(Exception):
queue.dequeue()
def test_error_when_dequeue_from_empty_queue(self):
queue = QueueTwoStacks()
queue.enqueue(1)
queue.enqueue(2)
actual = queue.dequeue()
expected = 1
self.assertEqual(actual, expected)
actual = queue.dequeue()
expected = 2
self.assertEqual(actual, expected)
with self.assertRaises(Exception):
queue.dequeue()
if __name__ == '__main__':
unittest.main(argv=[''], verbosity=2, exit=False)
The output will look like this:
test_basic_queue_operations (__main__.Test) ... ok
test_error_when_dequeue_from_empty_queue (__main__.Test) ... ok
test_error_when_dequeue_from_new_queue (__main__.Test) ... ok
----------------------------------------------------------------------
Ran 3 tests in 0.009s
OK
In this implementation, the time complexity of enqueue operation is O(1) and the time complexity of dequeue operation is O(n).
Related Posts
Implement a queue using two stacks in PythonCounting Sort in Python
Union Find in Python
Implement tail command in Python