Stack vs Queue

Commonality

Stack and Queue, both store data in a linear order, i.e., elements are arranged sequentially.

Difference

	Stack	Queue
Order	Last In, First Out (LIFO)	First In, First Out (FIFO)
Insertion	push() (adds element at the top)	enqueue() (adds element at the rear)
Deletion	pop()  (removes element from the top)	dequeue()  (removes element from the front)

 

The key difference is their processing order—LIFO and FIFO, which can be illustrated by the following figures.

Code

In Python, we can use lists to implement data storage in a linear order.

List as Stack

A stack follows a Last In, First Out (LIFO) order. We can use the list.append() method to push elements and list.pop() to pop elements.

stack = []
stack.append(1)  # push(1)
stack.append(2)  # push(2)
stack.append(3)  # push(3)
print(stack)  # [1, 2, 3]

stack.pop()  # pop() -> 3
print(stack)  # [1, 2]

List as Queue

A queue follows a First In, First Out (FIFO) order. We can use list.append() to enqueue and list.pop(0) to dequeue elements.

queue = []
queue.append(1)  # enqueue(1)
queue.append(2)  # enqueue(2)
queue.append(3)  # enqueue(3)
print(queue)  # [1, 2, 3]

queue.pop(0)  # dequeue() -> 1
print(queue)  # [2, 3]

!Note: pop(0) is inefficient because it shifts all elements after index 0 to the left, making it has time complexity of O(n).

Efficient Queue Implementation

To improve performance, we use collections.deque, which provides O(1) time complexity for both append() and popleft() operations.

from collections import deque

queue = deque()
queue.append(1)  # enqueue(1)
queue.append(2)  # enqueue(2)
queue.append(3)  # enqueue(3)
print(queue)  # deque([1, 2, 3])

queue.popleft()  # dequeue() -> 1
print(queue)  # deque([2, 3])