Stack – Introduction

Introduction

This article introduces the Stack data structure: what it is, how it works, core operations, common implementations, performance, and where it is used. You will also find step-by-step algorithms, an example with a dry run, and working C and Python programs.

Theory (from book)

A stack is a simple data structure used for storing data. In a stack, the arrival order matters. A familiar analogy is a pile of plates in a cafeteria: plates are added and removed at the top. The first plate placed becomes the last one used. Formally, a stack is an ordered list in which insertion and deletion are performed at one end called the top. The last element inserted is the first to be deleted, so a stack is a Last-In First-Out (LIFO) or First-In Last-Out (FILO) list.

When an element is inserted, it is called a push, and when an element is removed, it is called a pop. Trying to pop an empty stack is an underflow, and trying to push onto a full stack is an overflow; these are treated as exceptions.

A day-to-day illustration: a developer working on a project receives a higher-priority task and pushes the current work aside; an urgent call arrives and the current task is pushed aside again to answer the phone. After finishing the call, the previously suspended task is resumed first, and eventually the developer returns to the long-term project. This mirrors LIFO behavior.

Stack ADT (assume integer data):

• Main operations:
  • Push(int data): insert data onto the stack.
  • int Pop(): remove and return the last inserted element.
• Auxiliary operations:
  • int Top(): return the last inserted element without removing it.
  • int Size(): return the number of elements in the stack.
  • int IsEmptyStack(): indicate whether the stack has no elements.
  • int IsFullStack(): indicate whether the stack is full.
• Exceptions: Pop and Top cannot be performed on an empty stack; attempting them throws an exception. Pushing onto a full stack throws an exception.

Applications where stacks play an important role:

• Direct applications:
  • Balancing of symbols
  • Infix-to-postfix conversion
  • Evaluation of postfix expression
  • Implementing function calls (including recursion)
  • Finding spans (e.g., in stock markets)
  • Page-visited history in a web browser (Back buttons)
  • Undo sequence in a text editor
  • Matching tags in HTML and XML
• Indirect applications:
  • Auxiliary data structure for other algorithms (e.g., tree traversals)
  • Component of other data structures (e.g., simulating queues)

Implementations:

• Simple array-based implementation:
  • Elements are added left to right; a variable tracks the index of the top element.
  • The array can become full; pushing then throws a full stack exception.
  • Deleting from an empty stack throws an empty stack exception.
  • Performance (with n elements):
    • Space (for n pushes): O(n)
    • Push, Pop, Size, IsEmptyStack, IsFullStack, DeleteStack: O(1)
  • Limitation: Must predefine the maximum size; it cannot change. Pushing into a full stack causes an implementation-specific exception.
• Dynamic array-based implementation:
  • Use an index top (empty stack uses top = −1). Push increments top and writes the element; pop returns the element at top and decrements top.
  • Naive resizing (increase by 1 each time full) is too expensive: total time after n pushes is O(n²).
  • Repeated doubling: when full, create a new array of twice the size and copy items. Pushing n items takes time proportional to n (not n²). Doubling occurs log n times; total copy operations sum to O(n). The amortized time of push is O(1).
  • Performance (with n elements):
    • Space (for n pushes): O(n)
    • CreateStack: O(1)
    • Push: O(1) average (amortized)
    • Pop, Top, IsEmptyStack, IsFullStack, DeleteStack: O(1)
  • Note: Too many doublings may cause a memory overflow exception.
• Linked list implementation:
  • Push inserts at the beginning of the list; pop deletes from the beginning (the header/top node).
  • Performance (with n elements):
    • Space (for n pushes): O(n)
    • CreateStack: O(1)
    • Push: O(1) (average)
    • Pop: O(1)
    • Top: O(1)
    • IsEmptyStack: O(1)
    • DeleteStack: O(n)

Comparison of growth strategies and implementations:

• Incremental vs Doubling (amortized time of push over n pushes starting from size 1):
  • Incremental strategy: O(n) amortized time per push [O(n²)/n].
  • Doubling strategy: O(1) amortized time per push [O(n)/n].
• Array vs Linked list:
  • Array implementation:
    • Operations take constant time.
    • Occasional expensive doubling.
    • Any sequence of n operations (from empty): amortized time proportional to n.
  • Linked list implementation:
    • Grows and shrinks gracefully.
    • Every operation takes constant time O(1).
    • Each operation uses extra space and time to handle references.

Algorithm Steps

Below are generic steps for core stack operations (array-based view with a top index; empty when top = −1):

1. Push(x)
   1. If the stack is full, handle overflow (e.g., throw exception or resize if dynamic).
   2. Increment top.
   3. Set A[top] = x.
2. Pop()
   1. If the stack is empty (top == −1), handle underflow.
   2. Let x = A[top].
   3. Decrement top.
   4. Return x.
3. Top()
   1. If the stack is empty, handle underflow.
   2. Return A[top] without modifying top.
4. IsEmpty()
   1. Return true if top == −1; otherwise false.

Example & Dry Run

Operations sequence: Push(10), Push(20), Push(30), Pop(), Top()

1. Start: top = −1, stack = []
2. Push(10): top = 0, stack = [10]
3. Push(20): top = 1, stack = [10, 20]
4. Push(30): top = 2, stack = [10, 20, 30]
5. Pop(): returns 30, top = 1, stack = [10, 20]
6. Top(): returns 20, top remains 1, stack = [10, 20]

Code in C and Python

The C implementation below uses a dynamic array with repeated doubling (amortized O(1) push). The Python implementation uses a list to achieve the same behavior.

C (Dynamic Array Stack with Doubling)

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;
    int capacity;
    int top; // index of last inserted element; -1 when empty
} Stack;

Stack* create_stack(int initial_capacity) {
    if (initial_capacity <= 0) initial_capacity = 1;
    Stack *s = (Stack*)malloc(sizeof(Stack));
    if (!s) { fprintf(stderr, "Memory allocation failed\n"); exit(EXIT_FAILURE); }
    s->data = (int*)malloc(sizeof(int) * initial_capacity);
    if (!s->data) { fprintf(stderr, "Memory allocation failed\n"); exit(EXIT_FAILURE); }
    s->capacity = initial_capacity;
    s->top = -1;
    return s;
}

int is_empty(Stack *s) { return s->top == -1; }
int size(Stack *s) { return s->top + 1; }

void resize(Stack *s, int new_capacity) {
    int *new_data = (int*)realloc(s->data, sizeof(int) * new_capacity);
    if (!new_data) { fprintf(stderr, "Memory reallocation failed\n"); exit(EXIT_FAILURE); }
    s->data = new_data;
    s->capacity = new_capacity;
}

void push(Stack *s, int value) {
    if (s->top + 1 == s->capacity) {
        // Double the capacity
        int new_capacity = s->capacity * 2;
        resize(s, new_capacity);
    }
    s->data[++(s->top)] = value;
}

int top(Stack *s) {
    if (is_empty(s)) { fprintf(stderr, "Top on empty stack (underflow)\n"); exit(EXIT_FAILURE); }
    return s->data[s->top];
}

int pop(Stack *s) {
    if (is_empty(s)) { fprintf(stderr, "Pop on empty stack (underflow)\n"); exit(EXIT_FAILURE); }
    return s->data[(s->top)--];
}

void delete_stack(Stack *s) {
    if (!s) return;
    free(s->data);
    free(s);
}

int main(void) {
    Stack *s = create_stack(2);
    push(s, 10);
    push(s, 20);
    push(s, 30); // triggers doubling from 2 to 4
    printf("Pop: %d\n", pop(s));  // 30
    printf("Top: %d\n", top(s));  // 20
    printf("Size: %d\n", size(s)); // 2
    delete_stack(s);
    return 0;
}
    

Python (Dynamic Array via list)

class Stack:
    def __init__(self):
        self._a = []  # Python list grows via dynamic array doubling

    def push(self, x: int) -> None:
        self._a.append(x)

    def pop(self) -> int:
        if self.is_empty():
            raise IndexError("pop from empty stack (underflow)")
        return self._a.pop()

    def top(self) -> int:
        if self.is_empty():
            raise IndexError("top from empty stack (underflow)")
        return self._a[-1]

    def is_empty(self) -> bool:
        return len(self._a) == 0

    def size(self) -> int:
        return len(self._a)

if __name__ == "__main__":
    s = Stack()
    s.push(10)
    s.push(20)
    s.push(30)
    print("Pop:", s.pop())  # 30
    print("Top:", s.top())  # 20
    print("Size:", s.size())  # 2
    

Time Complexity

Advantages & Disadvantages

• Array implementation:
  • Pros: Operations take constant time; any sequence of n operations from empty has amortized time proportional to n.
  • Cons: Occasional expensive doubling; fixed-size arrays cannot grow (overflow) unless using dynamic resizing.
• Dynamic array (doubling) strategy:
  • Pros: Amortized O(1) push; total time O(n) over n pushes.
  • Cons: Copying during doubling; too many doublings may cause memory overflow.
• Linked list implementation:
  • Pros: Grows and shrinks gracefully; every operation takes O(1).
  • Cons: Each operation uses extra space and time to manage references.

Applications

• Balancing of symbols
• Infix-to-postfix conversion
• Evaluation of postfix expression
• Implementing function calls (including recursion)
• Finding spans (e.g., stock market spans)
• Page-visited history in a Web browser (Back buttons)
• Undo sequence in a text editor
• Matching tags in HTML and XML
• Auxiliary structure for algorithms (e.g., tree traversal algorithms)
• Component of other data structures (e.g., simulating queues)

Crust Summary

• Stack is LIFO: push to top, pop from top; underflow on empty, overflow on full.
• ADT operations: Push, Pop, Top, Size, IsEmpty, IsFull; Pop/Top throw on empty; Push throws on full.
• Implementations:
  • Simple array: O(1) ops; fixed size.
  • Dynamic array (doubling): amortized O(1) push; occasional copies.
  • Linked list: O(1) ops; flexible growth; DeleteStack O(n).
• Used in parsing, expression conversion/evaluation, recursion, browser history, undo, and more.
• C and Python code provided for ready use.