# 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

Union Find in PythonImplement a queue using two stacks in Python

Implement tail command in Python

Counting Sort in Python