Skip to content

Introduction to Stack

Introduction to Stack in Data Structures

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, meaning the last element added to the stack is the first one to be removed. It is widely used in programming for tasks like managing function calls, evaluating expressions, and undoing operations in applications.

Characteristics of a Stack

  1. LIFO Principle: The element inserted last is the first to be removed.
  2. One End Operations: Elements can be added (pushed) or removed (popped) only from the top of the stack.
  3. Fixed Size or Dynamic: Depending on implementation, stacks can have a fixed size (array-based) or be dynamic in size (linked list-based).

Basic Operations on a Stack

  1. Push: Add an element to the top of the stack.
  2. Pop: Remove the top element from the stack.
  3. Peek/Top: Retrieve the top element without removing it.
  4. isEmpty: Check if the stack is empty.
  5. isFull: Check if the stack is full (only for array-based implementations).

Representation of a Stack

Stacks can be implemented in two ways:

  1. Array-Based Stack:
    • Uses a fixed-size array.
    • Simple to implement but has a limitation of a fixed size.
  2. Linked List-Based Stack:
    • Dynamic in size.
    • Each element (node) has a value and a pointer to the next node.

Stack Operations in Detail

1. Push Operation

  • Adds an element to the top of the stack.
  • Steps:
    • Check if the stack is full (in array implementation).
    • Increment the top pointer.
    • Insert the element at the position pointed by top.

2. Pop Operation

  • Removes the top element of the stack.
  • Steps:
    • Check if the stack is empty.
    • Retrieve the element at the position pointed by top.
    • Decrement the top pointer.

3. Peek Operation

  • Retrieves the top element without removing it.
  • Steps:
    • Check if the stack is empty.
    • Return the value at the position pointed by top.

4. isEmpty Operation

  • Checks if the stack has no elements.
  • Steps:
    • Return true if top == -1; otherwise, return false.

Algorithmic Example

Push Operation

PUSH(stack, element, maxSize):

    if TOP == maxSize – 1:

        print “Stack Overflow”

    else:

        TOP = TOP + 1

        stack[TOP] = element

Pop Operation

POP(stack):

    if TOP == -1:

        print “Stack Underflow”

    else:

        element = stack[TOP]

        TOP = TOP – 1

        return element

Applications of Stacks

  1. Function Call Management: Used in recursion and backtracking.
  2. Expression Evaluation:
    • Infix to Postfix/Prefix Conversion.
    • Evaluating Postfix/Prefix expressions.
  3. Undo/Redo Mechanism: Common in text editors and software.
  4. Balancing Parentheses: Validating expressions with brackets.
  5. Browser History Navigation: Managing forward and backward navigation.

Advantages of Stacks

  • Simple to implement.
  • Efficient for LIFO operations.
  • Useful in solving problems like parsing, recursion, and backtracking.

Limitations of Stacks

  • Limited size in array-based implementation.
  • Access is restricted to the top element only.

Example

Stack Push and Pop Example

Suppose a stack has a capacity of 5 and is initially empty:

  • Push 10 → Stack: [10]
  • Push 20 → Stack: [10, 20]
  • Push 30 → Stack: [10, 20, 30]
  • Pop → Removed 30; Stack: [10, 20]
  • Peek → Top element is 20.

Visualization

A stack can be visualized as a stack of plates where:

  • Adding a plate is analogous to the push operation.
  • Removing the top plate is analogous to the pop operation.

This foundational understanding makes stacks a crucial topic in computer science, with applications spanning multiple domains.