Stack in Data Structures: Implementations in Java, Python, & C++

A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. The last element added to the stack is the first one to be removed. It is analogous to a stack of plates — you add a plate on top and remove it from the top.

Basic Operations

• push(element): Adds an element to the top of the stack.
• pop(): Removes and returns the top element from the stack.
• peek() / top(): Returns the top element without removing it.
• isEmpty(): Checks if the stack is empty.
• size(): Returns the number of elements in the stack.

Implementation Options

Stacks can be implemented using:

• Arrays: Fixed size, efficient O(1) operations, but can overflow.
• Dynamic Arrays (ArrayList): Resizable, O(1) amortized.
• Linked Lists: Dynamic size, O(1) operations, no overflow.

Implementation in Python

Using List (Dynamic Array)

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

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.stack.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.stack[-1]

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

    def size(self):
        return len(self.stack)

# Example usage
s = Stack()
s.push(10)
s.push(20)
s.push(30)
print(s.peek())   # Output: 30
print(s.pop())    # Output: 30
print(s.size())   # Output: 2

Using Linked List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None
        self._size = 0

    def push(self, item):
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node
        self._size += 1

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        data = self.top.data
        self.top = self.top.next
        self._size -= 1
        return data

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.top.data

    def is_empty(self):
        return self.top is None

    def size(self):
        return self._size

Implementation in Java

Using ArrayList

import java.util.ArrayList;

class Stack {
    private ArrayList stack;

    public Stack() {
        stack = new ArrayList<>();
    }

    public void push(int item) {
        stack.add(item);
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack.remove(stack.size() - 1);
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack.get(stack.size() - 1);
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }

    public int size() {
        return stack.size();
    }
}

// Example usage
class Main {
    public static void main(String[] args) {
        Stack s = new Stack();
        s.push(10);
        s.push(20);
        s.push(30);
        System.out.println(s.peek());  // Output: 30
        System.out.println(s.pop());   // Output: 30
        System.out.println(s.size());  // Output: 2
    }
}

Using Java's Built-in Stack

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack.peek());  // Output: 30
        System.out.println(stack.pop());   // Output: 30
        System.out.println(stack.size());  // Output: 2
    }
}

Using Linked List (Custom)

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class Stack {
    private Node top;
    private int size;

    public Stack() {
        top = null;
        size = 0;
    }

    public void push(int item) {
        Node newNode = new Node(item);
        newNode.next = top;
        top = newNode;
        size++;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        int data = top.data;
        top = top.next;
        size--;
        return data;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public int size() {
        return size;
    }
}

Implementation in C++

Using Vector (Dynamic Array)

#include 
#include 
using namespace std;

class Stack {
private:
    vector stack;

public:
    void push(int item) {
        stack.push_back(item);
    }

    int pop() {
        if (isEmpty()) {
            throw runtime_error("Stack is empty");
        }
        int item = stack.back();
        stack.pop_back();
        return item;
    }

    int peek() {
        if (isEmpty()) {
            throw runtime_error("Stack is empty");
        }
        return stack.back();
    }

    bool isEmpty() {
        return stack.empty();
    }

    int size() {
        return stack.size();
    }
};

// Example usage
int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << s.peek() << endl;  // Output: 30
    cout << s.pop() << endl;   // Output: 30
    cout << s.size() << endl;  // Output: 2
    return 0;
}

Using C++ STL Stack

#include 
#include 
using namespace std;

int main() {
    stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << s.top() << endl;   // Output: 30
    s.pop();
    cout << s.top() << endl;   // Output: 20
    cout << s.size() << endl;  // Output: 2
    return 0;
}

Using Linked List (Custom)

#include 
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class Stack {
private:
    Node* top;
    int size;

public:
    Stack() : top(nullptr), size(0) {}

    void push(int item) {
        Node* newNode = new Node(item);
        newNode->next = top;
        top = newNode;
        size++;
    }

    int pop() {
        if (isEmpty()) {
            throw runtime_error("Stack is empty");
        }
        int data = top->data;
        Node* temp = top;
        top = top->next;
        delete temp;
        size--;
        return data;
    }

    int peek() {
        if (isEmpty()) {
            throw runtime_error("Stack is empty");
        }
        return top->data;
    }

    bool isEmpty() {
        return top == nullptr;
    }

    int getSize() {
        return size;
    }

    ~Stack() {
        while (!isEmpty()) {
            pop();
        }
    }
};

Complexity Analysis

Applications of Stack

• Function Call Management: The call stack stores function calls, local variables, and return addresses.
• Expression Evaluation: Converting infix to postfix/prefix and evaluating expressions (e.g., calculators).
• Undo/Redo Operations: In text editors and applications.
• Backtracking: Algorithms like DFS, maze solving, N-Queens.
• Parsing: Checking balanced parentheses, XML/HTML tag matching.
• Browser Navigation: Back and forward buttons.
• Recursion: The recursive call mechanism is implemented using a stack.
• Memory Management: Stack memory allocation for local variables.

Advantages & Disadvantages

Advantages

• Simple: Easy to understand and implement.
• Fast: All operations are O(1).
• Memory Efficient: Only stores the data needed.
• Dynamic: Can grow/shrink dynamically with linked list or dynamic array.

Disadvantages

• Limited Access: You can only access the top element.
• Fixed Size (array implementation): May overflow if not sized correctly.
• No Random Access: Cannot access elements by index.

Common Stack Problems

• Balanced Parentheses: Check if parentheses are properly matched.
• Next Greater Element: Find the next greater element for each element.
• Valid Parentheses: Check if brackets are valid.
• Evaluate Postfix Expression: Evaluate a postfix expression.
• Stock Span Problem: Calculate span of stock prices.
• Largest Rectangle in Histogram: Find largest rectangular area.

Key Takeaways

• Stack follows the LIFO (Last-In-First-Out) principle.
• Basic operations: push, pop, peek, isEmpty, size — all O(1).
• Can be implemented using arrays, dynamic arrays, or linked lists.
• Widely used in function calls, expression evaluation, undo/redo, and backtracking.
• Essential for many interview problems and algorithmic challenges.