Stack using Linked List

Description

Implement a Stack data structure using a Singly Linked List. The stack has no fixed capacity and must grow dynamically until memory is available.

The stack must support the following operations:

push(x): Insert element x at the top of the stack.
pop(): Remove and return the element from the top of the stack. Return -1 if the stack is empty.
peek(): Return the top element without removing it. Return -1 if the stack is empty.
isEmpty(): Return true if the stack is empty, false otherwise.
size(): Return the number of elements currently in the stack.

A stack follows the LIFO (Last-In, First-Out) principle: the most recently pushed element is the first to be popped.

Examples

Example 1

Input: q = 7, queries = [[1, 5], [1, 3], [1, 4], [3], [2], [5], [4]]

Output: [4, 2, false]

Explanation:

push(5): Insert 5 at the top of the stack. Stack: [5]
push(3): Insert 3 at the top. Stack: [3, 5] (top → bottom)
push(4): Insert 4 at the top. Stack: [4, 3, 5]
peek(): Return the top element → 4
pop(): Remove the top element 4. Stack: [3, 5]
size(): Stack contains 2 elements → 2
isEmpty(): Stack is not empty → false

Example 2

Input: q = 4, queries = [[4], [3], [1, 10], [5]]

Output: [true, -1, 1]

Explanation:

isEmpty(): Stack is empty → true
peek(): Stack is empty, no top element → -1
push(10): Insert 10 at the top. Stack: [10]
size(): Stack contains 1 element → 1

Constraints

1 ≤ number of queries ≤ 10^3
0 ≤ x ≤ 10^5

Editorial

Brute Force - Array-Based Stack

Intuition

The simplest way to implement a stack is using an array (or list). The idea maps directly to the LIFO concept:

Maintain an array arr[] and an integer top that tracks the index of the topmost element.
Push: Increment top and store the value at arr[top].
Pop: Read arr[top] and decrement top.
Peek: Return arr[top] without modifying top.

The bottom of the stack sits at arr[0], and the top moves rightward with each push. This is how stacks work in most standard library implementations (e.g., std::stack in C++ uses deque or vector internally).

For example, after push(5), push(3), push(4):

arr = [5, 3, 4, _, _]    top = 2
                  ↑
               top points here

Peek returns arr[2] = 4. Pop returns arr[2] = 4 and decrements top to 1.

This approach is simple and cache-friendly, but requires knowing the maximum capacity upfront or using dynamic resizing.

Step-by-Step Explanation

Let's trace the operations from Example 1: push(5), push(3), push(4), peek(), pop(), size(), isEmpty().

Step 1: Create an array of fixed capacity (say 5). Set top = -1 to indicate an empty stack.

Step 2: push(5): Increment top to 0. Set arr[0] = 5. Stack: [5, _, _, _, _], top = 0.

Step 3: push(3): Increment top to 1. Set arr[1] = 3. Stack: [5, 3, _, _, _], top = 1.

Step 4: push(4): Increment top to 2. Set arr[2] = 4. Stack: [5, 3, 4, _, _], top = 2.

Step 5: peek(): Return arr[top] = arr[2] = 4. Stack unchanged. Output: 4.

Step 6: pop(): Save arr[top] = arr[2] = 4. Decrement top to 1. Stack: [5, 3, _, _, _], top = 1.

Step 7: size(): Return top + 1 = 2. isEmpty(): top >= 0, return false.

Array-Based Stack: push, peek, pop operations — Watch how an array-based stack uses a top pointer to track the stack's top. Push increments top and writes, pop reads and decrements top, peek just reads — all O(1).

Algorithm

Initialization:

Create an array arr[] of fixed capacity
Set top = -1 (empty stack indicator)

push(x):

If top == capacity - 1, stack overflow — cannot push
Increment top
Set arr[top] = x

pop():

If top == -1, return -1 (underflow)
Save val = arr[top]
Decrement top
Return val

peek():

If top == -1, return -1
Return arr[top]

isEmpty(): Return top == -1

size(): Return top + 1

Code

#include <iostream>
using namespace std;

class MyStack {
    int arr[1001];
    int topIdx;

public:
    MyStack() : topIdx(-1) {}

    void push(int x) {
        arr[++topIdx] = x;
    }

    int pop() {
        if (topIdx < 0) return -1;  // underflow
        return arr[topIdx--];
    }

    int peek() {
        if (topIdx < 0) return -1;
        return arr[topIdx];
    }

    bool isEmpty() {
        return topIdx < 0;
    }

    int size() {
        return topIdx + 1;
    }
};

class MyStack:
    def __init__(self):
        self.arr = [0] * 1001  # fixed capacity
        self.top_idx = -1

    def push(self, x: int) -> None:
        self.top_idx += 1
        self.arr[self.top_idx] = x

    def pop(self) -> int:
        if self.top_idx < 0:
            return -1  # underflow
        val = self.arr[self.top_idx]
        self.top_idx -= 1
        return val

    def peek(self) -> int:
        if self.top_idx < 0:
            return -1
        return self.arr[self.top_idx]

    def isEmpty(self) -> bool:
        return self.top_idx < 0

    def size(self) -> int:
        return self.top_idx + 1

class MyStack {
    int[] arr;
    int topIdx;

    MyStack() {
        arr = new int[1001];
        topIdx = -1;
    }

    void push(int x) {
        arr[++topIdx] = x;
    }

    int pop() {
        if (topIdx < 0) return -1;  // underflow
        return arr[topIdx--];
    }

    int peek() {
        if (topIdx < 0) return -1;
        return arr[topIdx];
    }

    boolean isEmpty() {
        return topIdx < 0;
    }

    int size() {
        return topIdx + 1;
    }
}

Complexity Analysis

Time Complexity: O(1) per operation

All five operations (push, pop, peek, isEmpty, size) perform a constant number of steps: one array access and one integer increment/decrement. No loops, no traversals.

Space Complexity: O(capacity)

The array is allocated with a fixed capacity (e.g., 1001) regardless of how many elements are actually stored. If the stack only holds 3 elements, the remaining 998 slots are wasted memory. This is the fundamental space inefficiency of the array-based approach.

Why This Approach Is Not Efficient

The array-based stack achieves O(1) for all operations, so it's efficient in terms of time. However, it has structural limitations that make it unsuitable when the problem demands a dynamic, no-fixed-capacity stack:

1. Fixed capacity leads to overflow: An array must be allocated with a predetermined size. If the number of pushes exceeds this capacity, the stack overflows. We either crash or silently fail — unacceptable for a production data structure.

2. Memory waste: If we allocate capacity 1000 but only store 5 elements, 995 array slots sit unused. The memory is reserved but provides no value. For memory-constrained environments, this is wasteful.

3. Dynamic resizing has hidden costs: We could use a dynamic array (like std::vector or Python's list) that resizes when full. This gives amortized O(1) push, but individual push operations can take O(n) when the array needs to double in size and copy all elements. The worst-case per-operation time is O(n), not O(1).

4. The problem explicitly requires linked list implementation: Beyond theoretical concerns, this specific problem asks for a linked list-based stack — testing our ability to work with pointers and dynamic node allocation.

The linked list solution eliminates all these issues:

No fixed capacity: Grows node-by-node, limited only by system memory
No wasted memory: Each node stores exactly one element + one pointer
True O(1) worst-case: Every push and pop creates/deletes exactly one node — no resizing, no copying
Dynamic memory management: Memory is allocated when needed and freed when popped

Optimal Approach - Linked List Implementation

Intuition

Instead of a contiguous array, we represent each stack element as a node in a singly linked list. The head of the linked list acts as the top of the stack.

Each node contains:

data: the stored value
next: a pointer to the node below it in the stack

Why does a linked list naturally implement LIFO? Because we always insert at and remove from the head:

Push = insert at head: Create a new node, point its next to the current top, then update top to the new node. The new element is now at the front — it will be the first to be removed.
Pop = remove from head: Save the current top's value, move top to top.next, free the old node. The element that was pushed most recently is the one removed.

This is exactly head insertion and head deletion — the two simplest operations on a singly linked list, both O(1).

Key insight: A singly linked list with head insertion/deletion IS a stack. The LIFO behavior emerges naturally from how linked list head operations work. No index manipulation, no capacity checks, no resizing — just pointer updates.

Visually, after push(5), push(3), push(4):

top → [4] → [3] → [5] → NULL

Peek returns 4 (top's data). Pop removes [4] and updates top to [3].

Step-by-Step Explanation

Let's trace the operations from Example 1: push(5), push(3), push(4), peek(), pop(), size(), isEmpty().

Step 1: Initialize empty stack. Set top = NULL and count = 0. The linked list has no nodes.

Step 2: push(5): Create node with data=5. Set node.next = NULL (top is NULL). Update top to this node. count = 1.

top → [5] → NULL

Step 3: push(3): Create node with data=3. Set node.next = top (pointing to node 5). Update top to node 3. count = 2.

top → [3] → [5] → NULL

Step 4: push(4): Create node with data=4. Set node.next = top (pointing to node 3). Update top to node 4. count = 3.

top → [4] → [3] → [5] → NULL

Step 5: peek(): Return top.data = 4. No pointers change, no nodes created or destroyed. O(1).

Step 6: pop(): Save top.data = 4. Move top to top.next (node 3). Free old node [4]. count = 2. Return 4.

top → [3] → [5] → NULL

Step 7: size(): Return count = 2. isEmpty(): top ≠ NULL → return false.

Linked List Stack: Push, Peek, and Pop Operations — Watch how a singly linked list implements stack operations through head insertion (push) and head deletion (pop). The top pointer always points to the head node — the most recently added element.

Algorithm

Node Structure:

data: integer value
next: pointer to the next node (the one below in the stack)

Initialization:

Set top = NULL
Set count = 0

push(x):

Create a new node with data = x
Set node.next = top (new node points to current top)
Set top = node (new node becomes the new top)
Increment count

pop():

If top == NULL, return -1 (underflow)
Save val = top.data
Save temp = top
Set top = top.next (move top to the node below)
Free/delete temp
Decrement count
Return val

peek():

If top == NULL, return -1
Return top.data

isEmpty(): Return top == NULL

size(): Return count

Code

#include <iostream>
using namespace std;

struct StackNode {
    int data;
    StackNode* next;
    StackNode(int x) : data(x), next(NULL) {}
};

class MyStack {
    StackNode* top;
    int count;

public:
    MyStack() : top(NULL), count(0) {}

    void push(int x) {
        StackNode* node = new StackNode(x);
        node->next = top;   // new node points to old top
        top = node;          // new node becomes the top
        count++;
    }

    int pop() {
        if (top == NULL) return -1;  // underflow
        StackNode* temp = top;
        int val = temp->data;
        top = top->next;     // move top to next node
        delete temp;         // free the old top node
        count--;
        return val;
    }

    int peek() {
        if (top == NULL) return -1;
        return top->data;
    }

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

    int size() {
        return count;
    }
};

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

class MyStack:
    def __init__(self):
        self.top = None
        self.count = 0

    def push(self, x: int) -> None:
        node = StackNode(x)
        node.next = self.top   # new node points to old top
        self.top = node         # new node becomes the top
        self.count += 1

    def pop(self) -> int:
        if self.top is None:
            return -1  # underflow
        val = self.top.data
        self.top = self.top.next  # move top to next node
        self.count -= 1
        return val

    def peek(self) -> int:
        if self.top is None:
            return -1
        return self.top.data

    def isEmpty(self) -> bool:
        return self.top is None

    def size(self) -> int:
        return self.count

class StackNode {
    int data;
    StackNode next;
    StackNode(int x) {
        data = x;
        next = null;
    }
}

class MyStack {
    StackNode top;
    int count;

    MyStack() {
        top = null;
        count = 0;
    }

    void push(int x) {
        StackNode node = new StackNode(x);
        node.next = top;   // new node points to old top
        top = node;         // new node becomes the top
        count++;
    }

    int pop() {
        if (top == null) return -1;  // underflow
        int val = top.data;
        top = top.next;     // move top to next node
        count--;
        return val;
    }

    int peek() {
        if (top == null) return -1;
        return top.data;
    }

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

    int size() {
        return count;
    }
}

Complexity Analysis

Time Complexity: O(1) per operation

Every operation performs a constant number of steps:

push: One node allocation + two pointer assignments → O(1)
pop: One pointer update + one deallocation → O(1)
peek: One pointer dereference → O(1)
isEmpty: One NULL check → O(1)
size: Return stored count → O(1)

Critically, this is worst-case O(1), not amortized. Every individual operation is guaranteed to complete in constant time.

Space Complexity: O(n)

Where n is the number of elements currently in the stack. Each element uses one node (data + next pointer). Memory usage scales exactly with the number of elements — no pre-allocation, no wasted slots.

Comparison with Array-Based Stack:

Metric	Array Stack	Linked List Stack
Push (worst case)	O(1) or O(n)*	O(1)
Pop (worst case)	O(1)	O(1)
Memory usage	O(capacity)	O(n)
Overflow possible?	Yes (fixed)	No**
Memory per element	~4 bytes (int)	~12 bytes (int + ptr)
Cache locality	Excellent	Poor

* O(n) when dynamic array needs resizing
** Only if system runs out of memory

Trade-off: The linked list uses more memory per element (due to the next pointer) and has poorer cache locality (nodes scattered in heap memory). But it guarantees true O(1) worst case and dynamic capacity — exactly what this problem requires.

Language Essentials & Syntax

EASY

Pattern-Based Logic Building

EASY

Standard Libraries & Collections

EASY

Essential Mathematics

EASY

MEDIUM

Recursion Fundamentals

EASY

Hashing Essentials

EASY

MEDIUM

Comparison-Based Sorts

EASY

Divide & Conquer Sorts

EASY

MEDIUM

Array Fundamentals

EASY

MEDIUM

Intermediate Array Problems

EASY

MEDIUM

Advanced Array Challenges

EASY

MEDIUM

HARD

Searching in Sorted Arrays

EASY

MEDIUM

Search Space Reduction

EASY

MEDIUM

HARD

Matrix Binary Search

EASY

MEDIUM

HARD

Core String Operations

EASY

MEDIUM

Intermediate String Challenges

EASY

MEDIUM

Singly Linked List Basics

EASY

MEDIUM

Doubly Linked List Basics

EASY

MEDIUM

Linked List Techniques

EASY

MEDIUM

Doubly Linked List Techniques

MEDIUM

HARD

Advanced Linked List Challenges

MEDIUM

HARD

Building Recursive Thinking

EASY

MEDIUM

Generating Subsequences

EASY

MEDIUM

Exhaustive Search & Constraint Solving

MEDIUM

HARD

Bitwise Operations Fundamentals

EASY

MEDIUM

Bit Manipulation Applications

EASY

MEDIUM

Number Theory & Primes

EASY

MEDIUM

HARD