Stack

Stack data structure and its operations

A stack is a linear data structure that operates on a Last In, First Out (LIFO) basis, where the last element added is the first one to be removed. It's similar to a stack of plates—only the top plate can be removed at a time. The stack supports two main operations:

  1. Push: Adds an element to the top of the stack.
  2. Pop: Removes the element from the top of the stack.

Key Properties of Stack

  • LIFO (Last In, First Out): The last element added is the first one to be removed.
  • Top: A pointer or reference to the element at the top of the stack.
  • Size: The number of elements in the stack.

Basic Operations

  • Push(x): Insert element at the top of the stack.
  • Pop(): Remove and return the element from the top of the stack.
  • Peek() or Top(): Return the element at the top without removing it.
  • isEmpty(): Check if the stack has any elements.
  • isFull(): Check if the stack has reached its maximum capacity (for fixed-size stacks).

Implementation

Stacks can be implemented using arrays or linked lists.

Array
Linked List
# In an array-based stack, elements are added to the endof an array.
# Here's a simple code example in Python:

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

    def push(self, item):
        if len(self.stack) < self.capacity:
            self.stack.append(item)
        else:
            print("Stack Overflow")

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            print("Stack Underflow")

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

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

# Usage example
s = Stack(5)
s.push(10)
s.push(20)
print(s.pop())  # Output: 20

Applications of Stack

  • Expression Evaluation: Evaluating postfix or prefix expressions.
  • Syntax Parsing: Parsing expressions in compilers and interpreters.
  • Backtracking: Like undo operations in text editors.
  • Function Calls: Keeping track of function calls in recursion.

Stacks are simple but powerful, forming the backbone of many computer science algorithms and operations.

Resources

Edit this page
Linked List Introduction
Overview of Linked Lists
Queue
Queue data structure and its operations