---
title: "Linked stack overcoming array demerits"
subject: "Data Structure and Algorithm"
chapter: 4
key: "semester_4/data_structure_and_algorithm:stack-linked-overcome-array-demerits"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/stack-linked-overcome-array-demerits
site: BCT Engineering
---

# Linked stack overcoming array demerits

Data Structure and Algorithm · Chapter 4: Linked lists

- Asked in: 2068 Magh, 6+2 marks
- Video: [Linked List Implementation of Stacks (Part 1)](https://www.youtube.com/watch?v=0-kkDfCOXOI) — Neso Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/stack-linked-overcome-array-demerits
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-4

## Question

Devise an algorithm that overcomes the demerits of array implementation of stack. Also verify your algorithm with necessary illustrations.

## Short answer

A linked stack dynamically allocates nodes on push and frees on pop, so there is no fixed-size overflow. Push inserts at top; pop removes top node. Both O(1), overcoming array stack’s fixed capacity and overflow issues.

## Answer

**Demerits of array stack:** fixed size (overflow even when memory is free, or wasted space when mostly empty), size must be known in advance, and it cannot grow at run time. A **linked stack** removes these: nodes are allocated on demand, so the stack grows and shrinks dynamically.

#### Algorithm (top = head of a singly linked list)
```c
struct node { int info; struct node *next; };
struct node *top = NULL;
```
**PUSH(x)**
1. Create node `p` with malloc; if NULL, overflow (heap full), stop.
2. `p->info = x; p->next = top; top = p`.

**POP()**
1. If `top == NULL`, underflow, stop.
2. `p = top; x = p->info; top = top->next; free(p)`; return `x`.

**PEEK()**: if `top != NULL` return `top->info`.

```c
void push(int x) {
    struct node *p = (struct node *)malloc(sizeof(struct node));
    if (!p) { printf("Overflow\n"); return; }
    p->info = x; p->next = top; top = p;
}
int pop(void) {
    if (!top) { printf("Underflow\n"); return -1; }
    struct node *p = top; int x = p->info;
    top = top->next; free(p);
    return x;
}
```

#### Verification
| Operation | Stack (top first) | Returned |
|---|---|---|
| push(5) | 5 | - |
| push(8) | 8, 5 | - |
| push(2) | 2, 8, 5 | - |
| pop() | 8, 5 | 2 |
| pop() | 5 | 8 |
| pop() | empty | 5 |
| pop() | underflow | - |

```text
push(2):  top -> [2]->[8]->[5]->NULL
pop():    top -> [8]->[5]->NULL       ([2] freed)
```
Elements leave in last-in first-out order, and push/pop are O(1) with no size limit except available memory.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which demerit of the array stack does the linked stack remove?
   A. Fixed size: the stack cannot grow at run time
   B. Slow O(n) push
   C. Elements cannot be popped in LIFO order
   D. Stack cannot store integers
   Answer: A. Nodes are allocated on demand, so the linked stack grows and shrinks dynamically instead of having a fixed size. (Key point: Array stack demerit)

2. In linked-stack PUSH(x), which statements correctly insert the new node p?
   A. top = p; p->next = top
   B. p->next = top; top = p
   C. p->next = NULL; top = p
   D. top->next = p; top = p
   Answer: B. The new node must first point to the old top, then top is moved to the new node. Reversing the order loses the old stack. (Key point: PUSH steps)

3. In linked-stack POP, why is the old top saved in p before moving top?
   A. Because top cannot be changed directly
   B. To make pop O(n)
   C. So the node can be freed and its info returned after top moves
   D. To check for overflow
   Answer: C. After top = top->next the old node would be unreachable, so p keeps it to read info and free it. (Key point: POP steps)

4. In the linked stack, when does overflow occur and when underflow?
   A. Overflow when top == NULL; underflow when malloc fails
   B. Overflow when the array is full; underflow when size is 0
   C. Neither can ever occur
   D. Overflow when malloc returns NULL; underflow when top == NULL
   Answer: D. No fixed limit exists, so overflow only happens when heap memory runs out (malloc NULL); popping an empty stack (top NULL) is underflow. (Key point: Overflow and underflow)

## Related in Data Structure and Algorithm

- [Stack and queue using linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astack-queue-singly-linked-list) — Data Structure and Algorithm, chapter 4, asked 2×
- [Linked list considerations; array list in C](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Alinked-list-considerations-array-list) — Data Structure and Algorithm, chapter 3
- [Static vs dynamic implementation of stack](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astack-static-vs-dynamic) — Data Structure and Algorithm, chapter 2
- [Push and pop on stack as linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astack-push-pop-linked-list) — Data Structure and Algorithm, chapter 4
- [Array implementation of list in C](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aarray-list-c-limitations) — Data Structure and Algorithm, chapter 3
- [Dynamic implementation of queue](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adynamic-queue-linked-algorithm) — Data Structure and Algorithm, chapter 4

## Related in other subjects

- [Forward vs reverse engineering merits and demerits](https://www.bctengineer.com/question.md?key=semester_6%2Fobject_oriented_analysis_and_design%3Aforward-reverse-engineering-merits) — Object Oriented Analysis and Design, chapter 4, asked 3×