Stack – Introduction

Introduction

A stack is a simple data structure used for storing data where the order of arrival matters. The cafeteria plate pile is a familiar illustration: clean plates are added on top and retrieval also happens from the top. In a stack, insertion and deletion occur at one end called the top, and the last element inserted is the first one removed. This is why a stack is called a Last In First Out (LIFO) or First In Last Out (FILO) list. Inserting an element is called push, removing an element is called pop, popping an empty stack causes underflow, and pushing into a full stack causes overflow. These error conditions are treated as exceptions.

Crust Summary

A stack is an ordered list supporting push and pop at the top with LIFO behavior. Core operations include push, pop, top, size, is-empty, and is-full, and pop or top on an empty stack throw exceptions; pushing into a full stack throws an exception. Stacks are used in symbol balancing, infix-to-postfix conversion, postfix evaluation, function calls (including recursion), stock span problems, browser back history, undo in text editors, and matching tags in HTML/XML. Implementations include simple arrays, dynamic arrays with doubling, and linked lists. Array implementations give constant-time operations but have capacity limits and occasional expensive resizing; dynamic array doubling ensures amortized O(1) push; linked lists grow and shrink gracefully with O(1) per operation and O(n) to delete the entire stack.

Theory

What is a Stack?

A stack is an ordered list with insertion and deletion at one end called top. The last element inserted is the first to be deleted, so it follows LIFO/FILO. Pushing inserts an element, popping removes the most recently inserted element, and top returns the last inserted element without removing it. Popping from an empty stack is underflow, and pushing into a full stack is overflow; both are exceptions.

How Stacks are Used

Stacks naturally model task management where new urgent tasks preempt older ones. When a higher-priority task arrives, the current task is set aside and the new task is worked on; once finished, the most recent pending task is resumed. This mirrors push for deferring work and pop for resuming the latest deferred work.

Stack ADT

The Stack ADT provides main operations push (insert data) and pop (remove and return the last inserted element). Auxiliary operations include top (return last inserted element without removal), size (number of stored elements), isEmptyStack (check if any elements exist), and isFullStack (check if the stack is full). Executing pop or top on an empty stack throws an exception, and pushing into a full stack throws an exception.

Applications

Stacks play an important role in a variety of direct and indirect applications from balancing symbols to acting as auxiliary structures in larger algorithms and systems.

Implementation: Simple Array

An array-based stack inserts from left to right and tracks the top index. Pushing to a full array throws a full stack exception and popping an empty stack throws an empty stack exception. With n elements, space complexity for n pushes is O(n); push, pop, size, isEmptyStack, isFullStack, and deleteStack take O(1) time. A key limitation is that the maximum size is fixed in advance and cannot be changed, so pushing into a full stack leads to an implementation-specific exception.

Implementation: Dynamic Array

In the simple array approach, we track top, increment it to push and write the element, and decrement it to pop. An empty stack can be represented with top = −1. If we increase the array size by 1 upon each full condition, the total time after n pushes is O(n²), which is too expensive. Instead, array doubling is used: when full, create a new array with twice the size and copy items. Pushing n items then takes time proportional to n, since the doubling happens log n times and the copy counts sum to about 2n. Thus the amortized time for push is O(1). With dynamic arrays, space for n pushes is O(n), and createStack, pop, top, isEmptyStack, isFullStack, and deleteStack run in O(1), while push runs in O(1) on average. Note that too many doublings may cause a memory overflow exception.

Implementation: Linked List

Stacks can also be implemented with linked lists by inserting at the beginning for push and deleting the head for pop. For n elements, space for n pushes is O(n); createStack, push (average), pop, top, and isEmptyStack run in O(1), while deleteStack takes O(n). This approach grows and shrinks gracefully, and every operation uses extra space and time to manage references.

Comparison of Implementations and Strategies

Using an incremental array growth strategy (increasing by 1 each time) makes a push amortized O(n). Using doubling makes push amortized O(1). Comparing array and linked list implementations, arrays have constant-time operations with occasional expensive resizing but achieve amortized O(1) over n operations from empty; linked lists achieve O(1) per operation and adjust size smoothly but incur overhead for references.

Problems & Solutions: Multi-Stack Arrangements

Two stacks can share one array by growing one from the left and the other from the right, giving O(1) time for push and pop and O(1) space overhead. Three stacks in one array can be managed by tracking start and top indices for the third stack and shifting it when it bumps into neighbors; pushes may become O(n) due to shifts, while pops remain O(1) with O(1) extra space. For m stacks in one array, the array is partitioned and stacks shift as needed; pushing may take O(n) due to adjustments, and popping remains O(1) with O(1) extra space.

Examples explanation

As a simple example that shows how stacks help with sequence symmetry, consider checking whether a string is a palindrome around a known middle separator character X. The idea is to push the first half before X onto a stack, and then match the second half against elements popped from the stack. If all symbols match in order until the stack empties, the string is a palindrome.

1. Traverse the input until the middle separator X is encountered, pushing each element onto the stack.
2. Continue traversal after X; for each element, compare it with the top of the stack and pop if they match.
3. If a mismatch occurs, the string is not a palindrome.
4. If the process ends with the stack empty, the string is a palindrome.

This approach uses O(n) time and O(n/2) ≈ O(n) space.

Algorithm Steps

• Array-based push: increment top and place the new element at the new top index; if the array is full, throw a full stack exception (or double the array size in the dynamic array approach).
• Array-based pop: read the element at top and decrement top; if the stack is empty (top = −1), throw an empty stack exception.
• Dynamic array doubling on push: when the array is full, allocate a new array of twice the size, copy all elements, and then insert the new element; this leads to amortized O(1) push over a sequence of operations.
• Two stacks in one array: start one index at the left and another at the right; the first stack grows rightward and the second grows leftward; push and pop run in O(1).
• Palindrome with separator X using a stack: traverse and push until X, then match each subsequent element against the stack top and pop on match; report not a palindrome on mismatch, and report palindrome when the stack empties successfully.

Code in C and Python

// Dynamic array-based stack for chars with doubling,
// plus palindrome check around 'X' as the middle separator.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    char *data;
    int top;
    int capacity;
} CharStack;

CharStack* createStack(int initialCap) {
    CharStack *s = (CharStack*)malloc(sizeof(CharStack));
    s->data = (char*)malloc(sizeof(char) * initialCap);
    s->top = -1;
    s->capacity = initialCap;
    return s;
}

bool isEmptyStack(CharStack *s) {
    return s->top == -1;
}

bool isFullStack(CharStack *s) {
    return s->top + 1 == s->capacity;
}

void doubleCapacity(CharStack *s) {
    int newCap = s->capacity * 2;
    char *newData = (char*)malloc(sizeof(char) * newCap);
    for (int i = 0; i <= s->top; i++) {
        newData[i] = s->data[i];
    }
    free(s->data);
    s->data = newData;
    s->capacity = newCap;
}

void push(CharStack *s, char c) {
    if (isFullStack(s)) {
        // Dynamic array doubling; average O(1) amortized push.
        doubleCapacity(s);
    }
    s->data[++(s->top)] = c;
}

char top(CharStack *s) {
    if (isEmptyStack(s)) {
        // Underflow exception in ADT terms; here we print and exit for demo.
        fprintf(stderr, "Exception: top() on empty stack\n");
        exit(EXIT_FAILURE);
    }
    return s->data[s->top];
}

char pop(CharStack *s) {
    if (isEmptyStack(s)) {
        // Underflow exception in ADT terms; here we print and exit for demo.
        fprintf(stderr, "Exception: pop() on empty stack\n");
        exit(EXIT_FAILURE);
    }
    return s->data[(s->top)--];
}

void deleteStack(CharStack *s) {
    free(s->data);
    free(s);
}

// Check palindrome with a known middle separator 'X'.
// Algorithm:
// 1) Push all chars before 'X'.
// 2) After 'X', each char must match stack top; pop on match.
// 3) Mismatch => not palindrome. Empty stack at end => palindrome.
// Time: O(n), Space: O(n/2) ~ O(n).
bool isPalindromeWithX(const char *str) {
    CharStack *s = createStack(4);
    int i = 0;
    // Push until 'X' or end
    while (str[i] != '\0' && str[i] != 'X') {
        push(s, str[i]);
        i++;
    }
    if (str[i] != 'X') {
        // No separator; treat as not applicable for this demo
        deleteStack(s);
        return false;
    }
    i++; // skip 'X'
    // Match second half
    while (str[i] != '\0') {
        if (isEmptyStack(s) || str[i] != top(s)) {
            deleteStack(s);
            return false;
        }
        pop(s);
        i++;
    }
    bool ok = isEmptyStack(s);
    deleteStack(s);
    return ok;
}

int main(void) {
    const char *a = "abcXcba";
    const char *b = "abXca";
    printf("%s : %s\n", a, isPalindromeWithX(a) ? "Palindrome" : "Not Palindrome");
    printf("%s : %s\n", b, isPalindromeWithX(b) ? "Palindrome" : "Not Palindrome");
    return 0;
}

# Python stack using list (dynamic array) and palindrome check with 'X'.
# Time: O(n), Space: O(n/2) ~ O(n).

class Stack:
    def __init__(self):
        self._a = []
    def push(self, x):
        # Amortized O(1) push due to underlying dynamic array doubling
        self._a.append(x)
    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")  # underflow in ADT terms
        return self._a.pop()
    def top(self):
        if self.is_empty():
            raise IndexError("top from empty stack")
        return self._a[-1]
    def is_empty(self):
        return len(self._a) == 0
    def size(self):
        return len(self._a)

def is_palindrome_with_X(s: str) -> bool:
    st = Stack()
    i = 0
    while i < len(s) and s[i] != 'X':
        st.push(s[i])
        i += 1
    if i == len(s) or s[i] != 'X':
        return False  # no separator for this demo
    i += 1  # skip 'X'
    while i < len(s):
        if st.is_empty() or s[i] != st.top():
            return False
        st.pop()
        i += 1
    return st.is_empty()

if __name__ == "__main__":
    print("abcXcba:", "Palindrome" if is_palindrome_with_X("abcXcba") else "Not Palindrome")
    print("abXca:", "Palindrome" if is_palindrome_with_X("abXca") else "Not Palindrome")

Dry Run in points

• Input: abcXcba
• Push until X: push ‘a’, push ‘b’, push ‘c’ (stack top is ‘c’).
• Encounter X; move to right side.
• Compare ‘c’ with top ‘c’ → match → pop.
• Compare ‘b’ with top ‘b’ → match → pop.
• Compare ‘a’ with top ‘a’ → match → pop.
• End of string and stack is empty → palindrome.

Time Complexity

Advantages & Disadvantages

• Array Implementation: operations take constant time; occasional expensive doubling; any sequence of n operations from empty has amortized time proportional to n; maximum size must be predefined and cannot change; pushing into a full stack causes an exception.
• Dynamic Array Doubling: pushing n items takes time proportional to n; amortized push is O(1); too many doublings may cause memory overflow exception.
• Linked List Implementation: grows and shrinks gracefully; every operation takes O(1); operations use extra space and time to deal with references; deleting the stack takes O(n).
• Incremental vs Doubling Strategy: incremental growth yields O(n) amortized push; doubling yields O(1) amortized push.
• Two Stacks in One Array: push and pop for both stacks are O(1) with O(1) extra space.
• Three or m Stacks in One Array: pushes may require shifting and can be O(n); pops are O(1); extra space overhead is O(1).

Applications

• Balancing of symbols
• Infix-to-postfix conversion
• Evaluation of postfix expression
• Implementing function calls (including recursion)
• Finding of spans (finding spans in stock markets)
• Page-visited history in a Web browser (Back Buttons)
• Undo sequence in a text editor
• Matching Tags in HTML and XML
• Auxiliary data structure for other algorithms (Tree traversal algorithms)
• Component of other data structures (Simulating queues)