Ctrl+K

Queue and stack

16. Queue and stack#

In computer science, stacks and queues are fundamental data structures that are widely used to solve various problems. These data structures organize and manage collections of data items in specific ways, making them suitable for different types of operations.

16.1. Stack (LIFO - Last In, First Out)#

A stack (see Stack) is a collection of elements that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. You can think of a stack like a stack of plates: you add new plates to the top, and you remove plates from the top.

Basic Operations of a Stack are:

  • Push: Add an element to the top of the stack.

  • Pop: Remove and return the element from the top of the stack.

  • Peek: Return the top element without removing it from the stack.

  • isEmpty: Check if the stack is empty.

In Python, a stack can be implemented using a list, where the last element of the list represents the top of the stack.

stack = []

# Push elements onto the stack
stack.append(10)
stack.append(20)
stack.append(30)

print(stack)  # Output: [10, 20, 30]

# Pop an element from the stack
top_element = stack.pop()
print(top_element)  # Output: 30

print(stack)  # Output: [10, 20]

16.2. Queue (FIFO - First In, First Out)#

A queue (see Queue) is a collection of elements that follows the First In, First Out (FIFO) principle. This means that the first element added to the queue is the first one to be removed. A queue is similar to a line of people: the first person in line is the first to be served.

Basic operations of a queue are:

  • Enqueue: Add an element to the end of the queue.

  • Dequeue: Remove and return the element from the front of the queue.

  • Peek/Front: Return the element at the front of the queue without removing it.

  • isEmpty: Check if the queue is empty.

In Python, a queue can also be implemented using a list, where the first element of the list represents the front of the queue.

queue = []

# Enqueue elements
queue.append(10)
queue.append(20)
queue.append(30)

print(queue)  # Output: [10, 20, 30]

# Dequeue an element from the queue
front_element = queue.pop(0)
print(front_element)  # Output: 10

print(queue)  # Output: [20, 30]

16.3. The type deque#

While Python lists can be used to implement stacks and queues, they are not always the most efficient option, especially for queues. Removing elements from the front of a list (using pop(0)) has take a time which is proportionnal with the number of elements in the list because all the elements have to be shifted. In a more advanced algorithmic terms, the time complexity is O(n) (see Complexity). Rest of operations are efficient, i.e. do not depend on the number of element in the list.

The deque (pronounced “deck”) is a class in Python’s collections module that provides a more efficient way to implement stacks and queues. Deques are generalizations of stacks and queues that allow efficient appending and popping from both ends. This makes them suitable for both LIFO (stack) and FIFO (queue) operations.

To use a deque, you first need to import it from the collections module:

from collections import deque

# Creating an empty deque
d = deque()

16.3.1. Using deque as a Stack#

When using deque as a stack, you can use append() to push elements onto the stack and pop() to remove them.

stack = deque()

# Push elements onto the stack
stack.append(10)
stack.append(20)
stack.append(30)

print(stack)  # Output: deque([10, 20, 30])

# Pop an element from the stack
top_element = stack.pop()
print(top_element)  # Output: 30

print(stack)  # Output: deque([10, 20])

16.3.2. Using deque as a Queue#

When using deque as a queue, you can use append() to enqueue elements and popleft() to dequeue them.

queue = deque()

# Enqueue elements
queue.append(10)
queue.append(20)
queue.append(30)

print(queue)  # Output: deque([10, 20, 30])

# Dequeue an element from the queue
front_element = queue.popleft()
print(front_element)  # Output: 10

print(queue)  # Output: deque([20, 30])

16.3.3. Advantages of Using deque#

Deque operations such as append(), pop(), appendleft(), and popleft() are all efficient, making them more efficient than list operations for these use cases. Deques can be used as stacks, queues, or even double-ended queues where elements can be added or removed from both ends.

Contents