Implement Stack

Design and implement a stack data structure with push, pop, top, and empty operations

Language Selection

Choose your preferred programming language

Showing: Python

Implement Stack

Problem Statement

Design a stack data structure that supports the following operations:

push(x): Push element x onto the stack
pop(): Remove and return the element on top of the stack
top(): Return the element on top of the stack without removing it
empty(): Check whether the stack is empty

Input/Output Specifications

Operations:
- push(int x): No return value
- pop(): Returns the popped integer
- top(): Returns the top integer without removing it
- empty(): Returns boolean indicating if stack is empty
Constraints:
- All operations should be performed in O(1) time complexity
- You may assume all operations are valid (no pop/top on empty stack in basic version)

Examples

Example 1:

Input:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

Output:
[null, null, null, 2, 2, false]

Explanation:
MyStack stack = new MyStack();
stack.push(1);    // stack: [1]
stack.push(2);    // stack: [2, 1]
stack.top();      // return 2, stack: [2, 1]
stack.pop();      // return 2, stack: [1]
stack.empty();    // return false

Solution Approaches

Approach 1: Array-Based Implementation (Dynamic)

Use a dynamic array (list/vector) to implement the stack with automatic resizing.

Algorithm Explanation

Data Structure: Use a dynamic array to store stack elements
Push: Append element to the end of array
Pop: Remove and return the last element
Top: Return the last element without removing
Empty: Check if array length is zero

Implementation

Python:

class MyStack:
    """
    Array-based stack implementation
    All operations: O(1) average time
    Space: O(n) where n is number of elements
    """
    
    def __init__(self):
        self.data = []
    
    def push(self, x: int) -> None:
        """Push element onto stack"""
        self.data.append(x)
    
    def pop(self) -> int:
        """Remove and return top element"""
        if self.empty():
            return -1  # Or raise exception
        return self.data.pop()
    
    def top(self) -> int:
        """Return top element without removing"""
        if self.empty():
            return -1  # Or raise exception
        return self.data[-1]
    
    def empty(self) -> bool:
        """Check if stack is empty"""
        return len(self.data) == 0

Java:

class MyStack {
    /**
     * Array-based stack implementation using ArrayList
     * All operations: O(1) average time
     * Space: O(n) where n is number of elements
     */
    
    private List<Integer> data;
    
    public MyStack() {
        data = new ArrayList<>();
    }
    
    public void push(int x) {
        data.add(x);
    }
    
    public int pop() {
        if (empty()) {
            return -1; // Or throw exception
        }
        return data.remove(data.size() - 1);
    }
    
    public int top() {
        if (empty()) {
            return -1; // Or throw exception
        }
        return data.get(data.size() - 1);
    }
    
    public boolean empty() {
        return data.isEmpty();
    }
}

Go:

// MyStack - Array-based stack implementation
// All operations: O(1) average time
// Space: O(n) where n is number of elements
type MyStack struct {
    data []int
}

func Constructor() MyStack {
    return MyStack{data: make([]int, 0)}
}

func (s *MyStack) Push(x int) {
    s.data = append(s.data, x)
}

func (s *MyStack) Pop() int {
    if s.Empty() {
        return -1 // Or panic
    }
    top := s.data[len(s.data)-1]
    s.data = s.data[:len(s.data)-1]
    return top
}

func (s *MyStack) Top() int {
    if s.Empty() {
        return -1 // Or panic
    }
    return s.data[len(s.data)-1]
}

func (s *MyStack) Empty() bool {
    return len(s.data) == 0
}

JavaScript:

/**
 * Array-based stack implementation
 * All operations: O(1) average time
 * Space: O(n) where n is number of elements
 */
class MyStack {
    constructor() {
        this.data = [];
    }
    
    push(x) {
        this.data.push(x);
    }
    
    pop() {
        if (this.empty()) {
            return -1; // Or throw error
        }
        return this.data.pop();
    }
    
    top() {
        if (this.empty()) {
            return -1; // Or throw error
        }
        return this.data[this.data.length - 1];
    }
    
    empty() {
        return this.data.length === 0;
    }
}

C#:

public class MyStack {
    /// <summary>
    /// Array-based stack implementation using List
    /// All operations: O(1) average time
    /// Space: O(n) where n is number of elements
    /// </summary>
    
    private List<int> data;
    
    public MyStack() {
        data = new List<int>();
    }
    
    public void Push(int x) {
        data.Add(x);
    }
    
    public int Pop() {
        if (Empty()) {
            return -1; // Or throw exception
        }
        int top = data[data.Count - 1];
        data.RemoveAt(data.Count - 1);
        return top;
    }
    
    public int Top() {
        if (Empty()) {
            return -1; // Or throw exception
        }
        return data[data.Count - 1];
    }
    
    public bool Empty() {
        return data.Count == 0;
    }
}

Approach 2: Linked List Implementation

Use a singly linked list to implement the stack for constant time operations without array resizing overhead.

Python:

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None

class MyStackLinkedList:
    """
    Linked list-based stack implementation
    All operations: O(1) time
    Space: O(n) where n is number of elements
    """
    
    def __init__(self):
        self.head = None
    
    def push(self, x: int) -> None:
        new_node = ListNode(x)
        new_node.next = self.head
        self.head = new_node
    
    def pop(self) -> int:
        if self.empty():
            return -1
        val = self.head.val
        self.head = self.head.next
        return val
    
    def top(self) -> int:
        if self.empty():
            return -1
        return self.head.val
    
    def empty(self) -> bool:
        return self.head is None

Key Insights

LIFO Principle: Stack follows Last-In-First-Out principle
Implementation Choices: Array vs Linked List trade-offs
Memory Management: Dynamic arrays handle resizing automatically
Cache Locality: Array implementation has better cache performance

Common Mistakes

Index Management: Off-by-one errors in array indexing
Empty Stack Handling: Not checking for empty stack before pop/top
Memory Leaks: Not properly managing memory in manual implementations

Interview Tips

Clarify Requirements: Ask about capacity limits and error handling
Discuss Trade-offs: Compare array vs linked list implementations
Handle Edge Cases: Always consider empty stack scenarios