Implement Stack Using Array and Linked List (DSA)

Introduction

The Stack is one of the most basic and important data structures in DSA. Interviewers love stack questions because they test your understanding of order, constraints, and control flow.

In simple terms, a stack works on the rule: Last In, First Out (LIFO).

Real-World Meaning of Stack

Think of a stack of plates:

• You place a plate on top

• You remove the top plate first

You cannot remove a plate from the middle. This exact behavior is followed by a stack.

What is a Stack?

A Stack is a linear data structure where:

• Insertion happens at the top

• Deletion also happens from the top

Basic Stack Operations

• Push – add an element

• Pop – remove the top element

• Peek / Top – see the top element

• isEmpty – check if stack is empty

Before vs After Example

Push Operation

Before:  [10, 20]
Push 30
After:   [10, 20, 30]

Pop Operation

Before:  [10, 20, 30]
Pop
After:   [10, 20]

What Interviewers Are Testing

When interviewers ask stack implementation, they check:

• Can you control insertion and deletion order?

• Do you handle overflow and underflow?

• Do you understand memory usage differences?

Implement Stack Using Array

Idea in Simple Words

• Use an array to store elements

• Maintain an index called top

• top always points to the last inserted element

Step-by-Step Logic (Array Stack)

1. Initialize top = -1

2. For push:

   • Increment top

   • Insert element at arr[top]

3. For pop:

   • Return arr[top]

   • Decrement top

Common Beginner Mistakes (Array Stack)

• Forgetting stack overflow check

• Popping from empty stack

• Mismanaging top index

Code: Stack Using Array

C++ Code

class Stack {
    int arr[100];
    int top;

public:
    Stack() {
        top = -1;
    }

    void push(int x) {
        if (top == 99) {
            cout << "Stack Overflow";
            return;
        }
        arr[++top] = x;
    }

    int pop() {
        if (top == -1) {
            cout << "Stack Underflow";
            return -1;
        }
        return arr[top--];
    }
};

One-Line Logic Before Code

We use an index to track the top and move it up for push and down for pop.

Implement Stack Using Linked List

Real-World Analogy

Imagine a chain of boxes, where each box knows only about the next box. The top of the stack is the first box.

Why Use Linked List for Stack

• No fixed size limitation

• Dynamic memory allocation

• No overflow (until memory ends)

Step-by-Step Logic (Linked List Stack)

1. Head node represents the top of the stack

2. For push:

   • Create new node

   • Point it to current head

   • Move head to new node

3. For pop:

   • Store head value

   • Move head to next node

Common Beginner Mistakes (Linked List Stack)

• Forgetting to update head

• Memory leaks (not deleting node)

Code: Stack Using Linked List

C++ Code

struct Node {
    int data;
    Node* next;
};

class Stack {
    Node* top;

public:
    Stack() {
        top = NULL;
    }

    void push(int x) {
        Node* newNode = new Node();
        newNode->data = x;
        newNode->next = top;
        top = newNode;
    }

    int pop() {
        if (top == NULL) {
            cout << "Stack Underflow";
            return -1;
        }
        int value = top->data;
        Node* temp = top;
        top = top->next;
        delete temp;
        return value;
    }
};

Stack Using Array vs Linked List

Feature	Array Stack	Linked List Stack
Size	Fixed	Dynamic
Memory	Continuous	Non-continuous
Overflow	Possible	Rare
Cache Friendly	Yes	No

When to Use Stack in Real Problems

Stacks are used in:

• Undo / Redo operations

• Function call stack

• Expression evaluation

• Parenthesis checking

• Backtracking problems

Time and Space Complexity

• Push: O(1)

• Pop: O(1)

• Space: O(n)

Easy Summary (Explain Like I’m 10)

A stack works like a pile of plates. You can only add or remove plates from the top. Whether you use an array or a linked list, the rule stays the same: last item goes out first. Once you understand push and pop clearly, many interview problems become very easy.

Summary

The Stack Data Structure is a foundational concept in DSA. Implementing it using both array and linked list helps you understand memory behavior, constraints, and performance trade-offs. Interviewers expect you to know both approaches, their differences, and real-world applications. Mastering stack implementation is the first step toward solving advanced stack-based problems confidently.