Advanced Structures

Sets, Queues, and Stacks

Introduction

While lists, tuples, and dictionaries are the backbone of Python’s data structures, certain tasks benefit from specialized structures like sets, queues, and stacks. These structures provide efficient ways to manage data for specific use cases such as eliminating duplicates, managing tasks, or reversing orders. In this post, we’ll explore these advanced data structures and their applications.

1. Sets: Unique and Unordered Collections

A set is an unordered collection of unique elements.

Creating a Set

python
Copy code
# Empty set (use set(), not {})
my_set = set()

# Set with values
fruits = {"apple", "banana", "cherry"}

Key Operations

  • Add Elements: add()
  • Remove Elements: remove() or discard()
  • Set Operations: Union, Intersection, Difference

Examples:

python
Copy code
# Add and remove elements
fruits.add("orange")
fruits.remove("banana")

# Set operations
a = {1, 2, 3}
b = {3, 4, 5}

print(a.union(b))        # {1, 2, 3, 4, 5}
print(a.intersection(b)) # {3}
print(a.difference(b))   # {1, 2}

When to Use Sets

  • Ensuring all elements are unique (e.g., email addresses, user IDs).
  • Performing fast membership checks (x in my_set).

2. Queues: First-In, First-Out (FIFO)

A queue is a collection where elements are added at one end (rear) and removed from the other (front). Python’s collections.deque is an excellent choice for implementing queues.

Creating a Queue

python
Copy code
from collections import deque

queue = deque()

# Add elements
queue.append("task1")
queue.append("task2")

# Remove elements
print(queue.popleft())  # "task1"
print(queue)            # deque(['task2'])

Applications

  • Task scheduling.
  • Managing resources (e.g., printer jobs).

3. Stacks: Last-In, First-Out (LIFO)

A stack is a collection where elements are added and removed from the same end. Python’s lists work well as stacks, or you can use collections.deque.

Using a List as a Stack

python
Copy code
stack = []

# Push elements
stack.append("item1")
stack.append("item2")

# Pop elements
print(stack.pop())  # "item2"
print(stack)        # ["item1"]

Using deque for Better Performance

python
Copy code
from collections import deque

stack = deque()

stack.append("item1")
stack.append("item2")
print(stack.pop())  # "item2"

Applications

  • Undo/redo functionality in applications.
  • Traversing trees or graphs (depth-first search).

4. Comparison of Data Structures

Feature Set Queue Stack
Ordering Unordered FIFO LIFO
Duplicates Not Allowed Allowed Allowed
Use Case Unique items Task scheduling Reversing order

5. Practical Example

Problem: Task Management System

Let’s implement a simple task management system using both queues and stacks.

Code Example:

python
Copy code
from collections import deque

# Task queue: First-In, First-Out
task_queue = deque(["task1", "task2", "task3"])

# Process tasks in FIFO order
while task_queue:
    current_task = task_queue.popleft()
    print(f"Processing {current_task}")

# Undo functionality using stack
undo_stack = []

# Add actions to stack
undo_stack.append("type1")
undo_stack.append("type2")

# Undo last action
while undo_stack:
    last_action = undo_stack.pop()
    print(f"Undoing {last_action}")

6. Choosing the Right Structure

Scenario Best Structure
Remove duplicates from a list Set
Manage a list of tasks in FIFO order Queue
Implement undo/redo functionality Stack

Conclusion

Sets, queues, and stacks are invaluable tools for specific programming tasks. By understanding their features and use cases, you can write more efficient and organized code.