Stacks

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Searching #◇Data Structures #◇Search Efficiency #◇Algorithm #◇Data Abstraction #◇Accessing Elements #◇Fundamental Data Structures #◇Time Complexity #◇Space Complexity

◇Overview

A stack is an abstract data type that represents a collection of elements with two principal operations:

◇Key Concepts

PUSH POP TOP STACK_EMPTY STACK_FULL

◇Details / Theory

◇Overview

A stack is an abstract data type that represents a collection of elements with two principal operations:
PUSH: Adds an element to the top of the stack. POP: Removes the most recently added element (the top).

Stacks follow the Last-In, First-Out (LIFO) principle—the last element inserted is the first one to be removed.

◇Key Terminologies

TOP: Pointer indicating the position of the most recently inserted item in the stack. STACK_EMPTY: Check to see if the stack contains no elements. STACK_FULL: Check to see if the stack has reached its maximum capacity.

◇Stack Operations

1. CREATE(STACK)

Initializes an empty stack:

TOP = 0;

2. STACK_EMPTY(STACK)

if (TOP == 0)
    return 1; // true
else
    return 0; // false

3. STACK_FULL(STACK)

Assuming stack has capacity n:

if (TOP == n)
    return 1; // true
else
    return 0; // false

4. PUSH(STACK, x)

Adds an element x to the top:

if (STACK_FULL(STACK))
    printf("Overflow error!\n");
else {
    TOP = TOP + 1;
    STACK[TOP] = x;
}

5. POP(STACK)

Removes and returns the top element:

if (STACK_EMPTY(STACK))
    printf("Underflow Error!\n");
else {
    x = STACK[TOP];
    TOP = TOP - 1;
    return x;
}

6. TOP(STACK)

Returns the current top element without removing it:

if (STACK_EMPTY(STACK))
    printf("Stack Empty!\n");
else
    return STACK[TOP];

◇Stack Simulation Walkthrough

Assume a stack S with capacity 9.

◇Stack Errors

Underflow: Trying to pop from an empty stack. Overflow: Trying to push into a full stack.

◇Real-World Analogies

Book pile: Only the top book is accessible. Plates stack: Only the top plate can be taken or added.

Function call stack Expression evaluation (e.g., infix to postfix conversion) Backtracking (e.g., mazes, recursion) Undo features in editors

◇Time and Space Complexities

◇Common Pitfalls

Calling pop or top on an empty stack — causes underflow error; always check empty() first Calling push on a full (fixed-size) stack — causes overflow error; always check full() first Confusing LIFO (stack) with FIFO (queue) — stacks return the most recently added element, queues return the oldest Forgetting that top only peeks without removing, while pop removes the element — mixing these up corrupts the stack state Assuming stack operations are $O(n)$ — all core operations (push, pop, top, empty, full) are $O(1)$

◇Summary

TL;DR — A stack is a LIFO data structure with $O(1)$ push, pop, top, empty, and full operations. Watch for overflow (push on full) and underflow (pop/top on empty). Implemented via arrays (fixed size) or linked lists (dynamic size).

◇Links

Related: Source / Reference:

◇References & Navigation

• Previous Topic: ◇Searching Algorithms
• Next Topic: ◇Supplement-Infix-to-Postfix
• Related Notes: ◇Function Calls, ◇Searching Algorithms