Python Stack and Queue

In computer science, stacks and queues are essential data structures used for organizing and storing data in a particular order. They are fundamental to many algorithms and applications, such as parsing expressions, handling function calls, and scheduling tasks.

What is a Stack?

A stack is a data structure 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. A stack can be visualized as a stack of plates where you add a new plate on top and remove the plate from the top as well.

The main operations that can be performed on a stack are:

• push: Adds an item to the top of the stack.
• pop: Removes the item from the top of the stack.
• peek: Returns the item from the top without removing it.
• isEmpty: Checks whether the stack is empty.
• size: Returns the number of items in the stack.

Example of Stack

In Python, we can implement a stack using a list or the deque class from the collections module. Here, we will show an example using a simple Python list.

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if not self.isEmpty():
            return self.stack.pop()
        else:
            return "Stack is empty"

    def peek(self):
        if not self.isEmpty():
            return self.stack[-1]
        else:
            return "Stack is empty"

    def isEmpty(self):
        return len(self.stack) == 0

    def size(self):
        return len(self.stack)

# Creating a stack object
s = Stack()

# Performing stack operations
s.push(10)
s.push(20)
s.push(30)

print("Top element:", s.peek())  # Output: 30
print("Popped element:", s.pop())  # Output: 30
print("Is stack empty?", s.isEmpty())  # Output: False
print("Size of stack:", s.size())  # Output: 2
            

Explanation of the Code:

Output:

What is a Queue?

A queue is a data structure that follows the First In, First Out (FIFO) principle. In a queue, the first element added is the first one to be removed, similar to a queue at a ticket counter.

The main operations that can be performed on a queue are:

• enqueue: Adds an item to the back of the queue.
• dequeue: Removes the item from the front of the queue.
• peek: Returns the item from the front without removing it.
• isEmpty: Checks whether the queue is empty.
• size: Returns the number of items in the queue.

Example of Queue

In Python, the deque class from the collections module is ideal for implementing queues due to its efficiency for appending and popping from both ends.

from collections import deque

class Queue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.isEmpty():
            return self.queue.popleft()
        else:
            return "Queue is empty"

    def peek(self):
        if not self.isEmpty():
            return self.queue[0]
        else:
            return "Queue is empty"

    def isEmpty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

# Creating a queue object
q = Queue()

# Performing queue operations
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)

print("Front element:", q.peek())  # Output: 10
print("Dequeued element:", q.dequeue())  # Output: 10
print("Is queue empty?", q.isEmpty())  # Output: False
print("Size of queue:", q.size())  # Output: 2
            

Explanation of the Code:

- We define a class Queue with an internal deque self.queue to hold the elements. - The enqueue() method adds an item to the back of the queue using append(). - The dequeue() method removes and returns the item from the front of the queue using popleft(). - The peek() method returns the front element without removing it. - The isEmpty() method checks if the queue is empty by checking if its length is zero. - The size() method returns the number of elements currently in the queue.

Output:

Real-World Applications of Stack and Queue

Both stacks and queues have wide-ranging applications in computer science:

• Stack: Used in undo/redo functionality in software, expression evaluation, and function calls (call stack).
• Queue: Used in scheduling tasks, handling requests in a server, breadth-first search (BFS) in graphs, and print job management.

Stacks and queues are essential data structures that are used in many algorithms and real-world systems. Stacks use a LIFO approach, while queues use FIFO. Understanding these concepts helps build a solid foundation for working with more complex data structures and algorithms in the future.