STACK

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed. It can be visualized as a stack of items where new items are placed on top, and only the top item can be accessed, removed, or added.

Operations on a Stack:

  1. Push: Adding an element to the top of the stack.
  2. Pop: Removing the top element from the stack.
  3. Peek (or Top): Returning the top element of the stack without removing it.
  4. isEmpty: Checking if the stack is empty.
  5. Size: Returning the number of elements in the stack.

Implementation of a Stack:

A stack can be implemented using various data structures such as arrays or linked lists. Here's an example implementation using a Python list:

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

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

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

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

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

Example Usage:

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print(stack.peek())  # Output: 3
print(stack.pop())   # Output: 3
print(stack.size())  # Output: 2

Applications of Stacks:

  1. Function Call Stack: Used by programming languages to manage function calls and returns.
  2. Expression Evaluation: Used to evaluate arithmetic expressions, postfix, and prefix expressions.
  3. Undo Operations: Used in text editors and software to implement undo functionality.
  4. Backtracking Algorithms: Used in algorithms like depth-first search (DFS) to backtrack and explore alternative paths.
  5. Parsing: Used in compilers and interpreters for parsing and evaluating expressions.

Stacks are versatile data structures with various applications in computer science and software engineering. They provide efficient operations and are used in many algorithms and applications for managing data and controlling program flow.

Table of Contents