Stacks and Queues

In the realm of data structures, stacks and queues play a crucial role in managing data in specific orderings. They are fundamental tools for organizing and processing data efficiently.

Stacks

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It can be visualized as a stack of plates where the last plate placed on top is the first one to be removed. The elements in a stack are added and removed from the same end, which is known as the top of the stack.

In Python, you can easily implement a stack using a list. The list.append() method is used to add elements to the top of the stack, and the list.pop() method is used to remove elements from the top. Here's an example:

1# Create an empty stack
2stack = []
3
4# Add elements to the stack
5stack.append('A')
6stack.append('B')
7stack.append('C')
8
9# Remove elements from the stack
10item = stack.pop()
11print(item)  # Output: C
12
13item = stack.pop()
14print(item)  # Output: B
15
16item = stack.pop()
17print(item)  # Output: A

In this code snippet, we create an empty stack using a list. We then add elements to the stack using the append() method and remove elements from the stack using the pop() method.

Queues

In contrast to stacks, queues follow the First-In-First-Out (FIFO) principle. Imagine a queue of people waiting in line at a ticket counter, where the person who arrives first is served first. Similarly, the elements in a queue are added at one end called the rear and removed from the other end called the front.

Python provides the collections.deque class that can be used to implement a queue. The deque.append() method is used to add elements to the rear of the queue, and the deque.popleft() method is used to remove elements from the front. Here's an example:

1from collections import deque
2
3# Create an empty queue
4queue = deque()
5
6# Add elements to the rear of the queue
7queue.append('A')
8queue.append('B')
9queue.append('C')
10
11# Remove elements from the front of the queue
12item = queue.popleft()
13print(item)  # Output: A
14
15item = queue.popleft()
16print(item)  # Output: B
17
18item = queue.popleft()
19print(item)  # Output: C

In this code snippet, we import the deque class from the collections module. We then create an empty queue using the deque() function and add elements to the rear of the queue using the append() method. Elements are removed from the front of the queue using the popleft() method.

Stacks and queues are versatile data structures that are used in various applications, including robotics and computer vision. In robotics, stacks can be used to store robot configurations or function call information. Queues are useful for storing sensor data or tasks in a queue-based controller.