Skip to main content

Stacks and Queues

Introduction​

Stacks and queues are fundamental data structures used in computer science and programming. They are essential concepts in data manipulation and play a crucial role in many algorithms and data processing tasks.

What are Stacks?​

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It behaves like a vertical pile of plates where elements are added and removed from only one end.

Key characteristics of a stack:

  1. Elements are stored in a single array.
  2. Only one end of the stack is accessible for insertion and deletion.
  3. The top element is the last one inserted and the first one to be removed.

Stack Operations​

  1. Push: Adds an element to the top of the stack.
  2. Pop: Removes the top element from the stack.
  3. Peek (or Top): Returns the top element without removing it.
  4. IsEmpty: Checks if the stack is empty.
  5. Size: Returns the number of elements in the stack.

Example implementation in Python:

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

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

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

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

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

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

# Example usage:
s = Stack()
s.push(10)
s.push(20)
print(s.peek())  # Output: 20
print(s.pop())   # Output: 20
print(s.size())  # Output: 1

Applications of Stacks​

  • Expression Evaluation: Stacks are used to evaluate postfix and prefix expressions.
  • Backtracking: The undo feature in text editors and the recursive backtracking algorithm use stacks.
  • Depth-First Search (DFS): DFS traversal of graphs can be implemented using a stack.
  • Function Call Management: The call stack in programming languages helps manage function calls and recursion.

What are Queues?​

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. It behaves like a line of people waiting for a service, where the first person in the line is served first.

Key characteristics of a queue:

  1. Elements are inserted at one end (rear) and removed from the other end (front).
  2. Only the front element can be accessed for removal.
  3. Queues maintain the order of elements based on their insertion time.

Queue Operations​

  1. Enqueue: Adds an element to the rear of the queue.
  2. Dequeue: Removes the front element from the queue.
  3. Peek (or Front): Returns the front element without removing it.
  4. IsEmpty: Checks if the queue is empty.
  5. Size: Returns the number of elements in the queue.

Example implementation in Python:

class Queue:
    def __init__(self):
        self.queue = []

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

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            return "Queue is empty"

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

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

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

# Example usage:
q = Queue()
q.enqueue(10)
q.enqueue(20)
print(q.peek())  # Output: 10
print(q.dequeue())  # Output: 10
print(q.size())  # Output: 1

Applications of Queues​

  • Task Scheduling: Queues are used in operating systems to schedule tasks and manage processes.
  • Breadth-First Search (BFS): BFS traversal of graphs relies on queues to maintain the order of exploration.
  • Printer Queue: Printers use queues to manage the order of print jobs.
  • Buffer Management: Queues are used to manage buffers in data streaming or packet processing.

Conclusion​

Stacks and queues are foundational data structures that serve as the basis for many algorithms and real-world applications. Understanding their properties, operations, and use cases is crucial for developing efficient algorithms and systems.