Stack Implementation Using Linked List in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Push and Pop Operations on Stack

What is the printed state of the stack after the following operations?

Push 10, Push 20, Push 30, Pop, Push 40

DSA C++

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

class Stack {
    Node* top;
public:
    Stack() : top(nullptr) {}
    void push(int x) {
        Node* temp = new Node();
        temp->data = x;
        temp->next = top;
        top = temp;
    }
    void pop() {
        if (top == nullptr) return;
        Node* temp = top;
        top = top->next;
        delete temp;
    }
    void print() {
        Node* temp = top;
        while (temp != nullptr) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "null" << std::endl;
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    s.pop();
    s.push(40);
    s.print();
    return 0;
}

A 40 -> 20 -> 10 -> null

B 20 -> 10 -> 40 -> null

C 30 -> 20 -> 10 -> 40 -> null

D 10 -> 20 -> 40 -> null

💡 Hint

Remember that push adds to the top and pop removes from the top.

Push adds elements to the top of the stack. After pushing 10, 20, 30, the stack is 30 -> 20 -> 10 -> null. Pop removes the top element (30), so stack becomes 20 -> 10 -> null. Then pushing 40 adds it on top: 40 -> 20 -> 10 -> null.

🧠 Conceptual

intermediate

Understanding Stack Top Pointer

In a stack implemented using a linked list, what does the 'top' pointer represent?

A Points to the middle element of the stack

B Points to the most recently added element (top of the stack)

C Points to the bottom element of the stack

D Points to the last node in the linked list

💡 Hint

Think about where push and pop operations happen in a stack.

The 'top' pointer always points to the most recently added element, which is the top of the stack. This allows push and pop operations to happen efficiently at the top.

🔧 Debug

advanced

Identify the Bug in Pop Method

What error will occur when running the pop method below if the stack is empty?

DSA C++

void pop() {
    Node* temp = top;
    top = top->next;
    delete temp;
}

A Compilation error due to missing return

B No error, pop works correctly

C Memory leak due to not deleting node

D Segmentation fault (accessing null pointer)

💡 Hint

What happens if top is nullptr and you try to access top->next?

If the stack is empty, top is nullptr. Accessing top->next causes a segmentation fault because you are dereferencing a null pointer.

❓ Predict Output

advanced

Output After Multiple Push and Pop

What is the printed stack after these operations?

Push 5, Push 15, Pop, Push 25, Push 35, Pop, Pop

DSA C++

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

class Stack {
    Node* top;
public:
    Stack() : top(nullptr) {}
    void push(int x) {
        Node* temp = new Node();
        temp->data = x;
        temp->next = top;
        top = temp;
    }
    void pop() {
        if (top == nullptr) return;
        Node* temp = top;
        top = top->next;
        delete temp;
    }
    void print() {
        Node* temp = top;
        while (temp != nullptr) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "null" << std::endl;
    }
};

int main() {
    Stack s;
    s.push(5);
    s.push(15);
    s.pop();
    s.push(25);
    s.push(35);
    s.pop();
    s.pop();
    s.print();
    return 0;
}

A 5 -> null

B 25 -> 5 -> null

C 15 -> 5 -> null

D 35 -> 25 -> 5 -> null

💡 Hint

Track each push and pop carefully from the top.

Operations step-by-step: - Push 5: stack is 5 -> null - Push 15: 15 -> 5 -> null - Pop: removes 15, stack is 5 -> null - Push 25: 25 -> 5 -> null - Push 35: 35 -> 25 -> 5 -> null - Pop: removes 35, stack is 25 -> 5 -> null - Pop: removes 25, stack is 5 -> null

🧠 Conceptual

expert

Memory Usage in Stack Implemented with Linked List

Which statement about memory usage in a stack implemented using a linked list is true?

A Memory is pre-allocated for a fixed number of elements, so stack size is limited

B Memory is allocated on the stack segment of the program, limiting size to a few KB

C Memory is allocated dynamically for each element, so stack size can grow until system memory is exhausted

D Memory is shared between all nodes, so adding elements does not increase memory usage

💡 Hint

Think about how linked lists allocate memory for nodes.

Each node in a linked list is allocated dynamically on the heap when pushed. This allows the stack to grow as needed until system memory runs out.

Practice

1. What is the main advantage of implementing a stack using a linked list instead of an array?

easy

A. It uses less memory than an array

B. The stack can grow dynamically without a fixed size limit

C. It allows random access to elements

D. It is easier to sort the stack elements

Solution

1. Step 1: Understand stack size limitation in arrays

   Arrays have fixed size, so stack implemented with arrays has a maximum capacity.

2. Step 2: Linked list dynamic size property

   Linked lists can grow or shrink dynamically by adding or removing nodes, so stack size is not fixed.

3. Final Answer:

   The stack can grow dynamically without a fixed size limit -> Option B

4. Quick Check:

   Linked list stack size = dynamic growth [OK]

Hint: Linked list stacks grow dynamically, arrays have fixed size [OK]

Common Mistakes:

• Thinking linked list uses less memory always
• Assuming stack allows random access
• Confusing sorting with stack operations

2. Which of the following is the correct syntax to create a new node in a linked list stack in C++?

easy

A. Node* newNode = new Node(value);

B. Node newNode = Node(value);

C. Node newNode = new Node(value);

D. Node* newNode = Node(value);

Solution

1. Step 1: Understand dynamic memory allocation in C++

   To create a node dynamically, use 'new' keyword and pointer type.

2. Step 2: Check syntax correctness

   Node* newNode = new Node(value); uses pointer and 'new' correctly: Node* newNode = new Node(value);

3. Final Answer:

   Node* newNode = new Node(value); -> Option A

4. Quick Check:

   Dynamic node creation = new + pointer [OK]

Hint: Use 'new' with pointer to create nodes dynamically [OK]

Common Mistakes:

• Omitting pointer (*) when using new
• Using stack allocation instead of dynamic
• Assigning new object to non-pointer variable

3. What will be the output after executing the following code snippet for a stack implemented using linked list?

Stack s;
s.push(10);
s.push(20);
s.push(30);
s.pop();
s.push(40);
s.display();

Assuming display prints elements from top to bottom.

medium

A. 40 -> 30 -> 20 -> 10 -> null

B. 30 -> 20 -> 10 -> null

C. 20 -> 10 -> null

D. 40 -> 20 -> 10 -> null

Solution

1. Step 1: Trace push and pop operations

   Push 10, stack: 10; push 20, stack: 20->10; push 30, stack: 30->20->10; pop removes 30, stack: 20->10; push 40, stack: 40->20->10.

2. Step 2: Determine display output

   Display prints from top to bottom: 40 -> 20 -> 10 -> null.

3. Final Answer:

   40 -> 20 -> 10 -> null -> Option D

4. Quick Check:

   Stack after ops = 40->20->10 [OK]

Hint: Track push/pop stepwise to find top element [OK]

Common Mistakes:

• Forgetting pop removes top element
• Assuming push adds at bottom
• Mixing order of elements in display

4. Identify the error in the following pop function of a linked list stack:

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

medium

A. Returning -1 on empty stack is incorrect

B. Missing check for stack overflow

C. Accessing top->next after deleting top causes undefined behavior

D. Not updating top pointer after pop

Solution

1. Step 1: Analyze order of operations in pop

   Code deletes top node before accessing top->next, which is unsafe.

2. Step 2: Identify correct order

   Must save top->next in a temp pointer before deleting top, then update top.

3. Final Answer:

   Accessing top->next after deleting top causes undefined behavior -> Option C

4. Quick Check:

   Delete before next access = error [OK]

Hint: Save next pointer before deleting current node [OK]

Common Mistakes:

• Deleting node before updating pointer
• Ignoring stack underflow check
• Returning wrong values on empty stack

5. You want to implement a function to reverse a stack implemented using a linked list without using extra data structures. Which approach is correct?

hard

A. Use recursion to pop all elements and push them back in reverse order

B. Traverse the linked list and swap data of nodes pairwise

C. Create a new linked list and copy elements in reverse order

D. Use a queue to reorder elements and then push back to stack

Solution

1. Step 1: Understand constraints

   No extra data structures allowed, so cannot use queue or new list.

2. Step 2: Use recursion to reverse stack

   Recursion can pop all elements, then push them back in reverse order naturally.

3. Step 3: Why other options fail

   Swapping data pairwise does not reverse entire stack; copying needs extra list; queue is extra structure.

4. Final Answer:

   Use recursion to pop all elements and push them back in reverse order -> Option A

5. Quick Check:

   Recursion reverses stack without extra structures [OK]

Hint: Recursion can reverse stack without extra memory [OK]

Common Mistakes:

• Using extra data structures despite constraints
• Trying to swap data instead of nodes
• Not understanding recursion stack behavior