Stack Implementation Using Array and Linked List in Data Structure

CHAPTER 23 • DATA STRUCTURE

Stack Implementation Using Array and Linked List in Data Structure

Learn Stack implementation with memory diagrams, TOP updates, Push, Pop, Peek algorithms, C programs and step-by-step examples for exams.

Array Stack Linked List Stack C Programs Dry Runs

When students learn Stack for the first time, Push and Pop look easy. But implementation questions become confusing when the examiner asks how TOP changes after every operation.

Why does an Array Stack use an index? Why does a Linked List Stack use pointers? What happens when memory is full? How can we avoid losing nodes during Pop?

These questions become simple when we understand that Stack insertion and deletion always happen at the TOP. Only the method of storing and updating TOP changes.

Quick Answer: Stack implementation means storing and managing elements using the LIFO (Last In, First Out) principle. In array implementation, elements occupy consecutive array positions and TOP is an integer index. In Linked List implementation, elements are stored in connected nodes and TOP is a pointer to the first node. Both support Push, Pop and Peek operations.

For a revision of LIFO and basic operations, read Stack in Data Structure: Operations, Implementation and Applications . This chapter explains how both implementations work internally.

What Is Stack Implementation?

Stack is a linear Data Structure in which the most recently inserted element is removed first. A Stack implementation decides where elements are stored and how operations update the storage.

Push

Add at TOP

Insert a new element at the active top end.

Pop

Remove TOP

Return the most recent element and update TOP.

Peek

Read TOP

Read the top value without removing it.

LIFO = Last In, First Out

Two Ways of Representing TOP

Array Stack

TOP stores an integer index. In an empty zero-based Stack, TOP = -1.

TOP = 2 → items[2]

Linked List Stack

TOP stores the address of the first node. When empty, TOP = NULL.

TOP → First Node

This difference is the foundation of Stack implementation questions.

1. Stack Implementation Using Array

In Array Implementation, Stack elements are stored in an array. An integer variable called TOP stores the index of the most recently inserted element.

Suppose an array has capacity 4. Its valid indices are 0, 1, 2 and 3.

TOP = 2
30 [2]
20 [1]
10 [0]
Logical Order

Bottom → 10, 20, 30 → TOP

Index 3 is still available, so one more Push can succeed.

Figure 1: Array-based Stack. The value 30 is stored at index 2, the current TOP.

Important Conditions

Empty Condition
TOP == -1

No active Stack elements exist.

Full Condition
TOP == CAPACITY - 1

All positions in the fixed array are occupied.

Push Algorithm Using Array

IF TOP == CAPACITY - 1
    PRINT "Overflow"
ELSE
    TOP = TOP + 1
    STACK[TOP] = VALUE
END IF
1
Check capacity.

Check whether the Stack is already full.

2
Increase TOP.

Move TOP to the next free index.

3
Store the value.

Insert the element at STACK[TOP].

Pop Algorithm Using Array

IF TOP == -1
    PRINT "Underflow"
ELSE
    VALUE = STACK[TOP]
    TOP = TOP - 1
    RETURN VALUE
END IF
Memory Trick: Array Push = Increase TOP, then insert. Array Pop = Read TOP, then decrease TOP.

Peek Algorithm Using Array

IF TOP == -1
    PRINT "Stack is Empty"
ELSE
    RETURN STACK[TOP]
END IF

Array Stack Dry Run

Consider a Stack having maximum capacity 4. Initially TOP = -1.

Operation TOP Stack (Bottom to Top) Explanation
Initialize-1EmptyNo elements
Push(10)010Index 0
Push(20)110, 20Index 1
Push(30)210, 20, 30Index 2
Pop()110, 20Returns 30
Push(40)210, 20, 40Index 2 reused
Push(50)310, 20, 40, 50Full
Push(60)3UnchangedOverflow
Final Result: TOP = 3 and Stack contains 10, 20, 40, 50 from bottom to top. Failed Push does not change the Stack.
Common Mistake: Pop does not need to erase the old array cell. Decreasing TOP is enough to remove the value logically.

Complete C Program: Stack Using Array

This program implements Push, Pop, Peek, isEmpty, isFull and Display. It also handles overflow and underflow.

#include <stdio.h>

#define CAPACITY 4

typedef struct {
    int items[CAPACITY];
    int top;
} Stack;

void initialize(Stack *s) {
    s->top = -1;
}

int isEmpty(const Stack *s) {
    return s->top == -1;
}

int isFull(const Stack *s) {
    return s->top == CAPACITY - 1;
}

int push(Stack *s, int value) {
    if (isFull(s))
        return 0;

    s->items[++s->top] = value;
    return 1;
}

int pop(Stack *s, int *value) {
    if (isEmpty(s))
        return 0;

    *value = s->items[s->top--];
    return 1;
}

int peek(const Stack *s, int *value) {
    if (isEmpty(s))
        return 0;

    *value = s->items[s->top];
    return 1;
}

void display(const Stack *s) {
    if (isEmpty(s)) {
        puts("Stack is empty");
        return;
    }

    printf("TOP -> ");

    for (int i = s->top; i >= 0; i--)
        printf("%d ", s->items[i]);

    putchar('\n');
}

int main(void) {
    Stack s;
    int value;

    initialize(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    display(&s);

    if (peek(&s, &value))
        printf("Peek: %d\n", value);

    if (pop(&s, &value))
        printf("Pop: %d\n", value);

    push(&s, 40);
    push(&s, 50);

    display(&s);

    if (!push(&s, 60))
        puts("Overflow: stack is full");

    while (pop(&s, &value))
        printf("Removed: %d\n", value);

    if (!pop(&s, &value))
        puts("Underflow: stack is empty");

    return 0;
}

Expected Output

TOP -> 30 20 10
Peek: 30
Pop: 30
TOP -> 50 40 20 10
Overflow: stack is full
Removed: 50
Removed: 40
Removed: 20
Removed: 10
Underflow: stack is empty

Explanation of the C Program

initialize()

Set TOP

Starts the Stack at -1.

isFull()

Check Space

Checks whether the final slot is occupied.

push() and pop()

Change TOP

Insert or remove the active top element.

peek()

Read TOP

Returns the top value without deleting it.

2. Stack Implementation Using Linked List

In Linked List implementation, Stack elements are stored in separate dynamically allocated nodes.

Every node contains two fields: data and a pointer to the next node. TOP points to the first node.

For Push, a node is inserted at the beginning. For Pop, the first node is removed.

If you need to revise nodes and pointers, read Linked List in Data Structure: Types, Operations and Examples .

Linked List Stack Diagram

Figure 2: TOP stores the address of the first node. On mobile, swipe inside the diagram.

How Push Updates Pointers

Suppose TOP points to a node containing 20. Now insert 30.

1
Create a new node.

Allocate memory and store 30.

2
Connect the new node.

Set its next pointer to the current TOP.

3
Update TOP.

Make TOP point to the new node.

Before: TOP → 20 → 10 → NULL
After: TOP → 30 → 20 → 10 → NULL
Important Pointer Rule: First connect the new node with the old TOP, then update TOP. Otherwise, previous nodes may become unreachable.

Push Algorithm Using Linked List

NEW = ALLOCATE_NODE()

IF NEW == NULL
    PRINT "Allocation Failed"
    RETURN FAILURE
END IF

NEW.data = VALUE
NEW.next = TOP
TOP = NEW

RETURN SUCCESS

How Pop Updates Pointers

Suppose TOP contains 30 and the next node contains 20. We want to remove 30 safely.

1
Check TOP.

If TOP is NULL, the Stack is empty.

2
Save old TOP.

Store the first node in a temporary pointer.

3
Move TOP.

Make TOP point to the next node.

4
Release memory.

Save the removed value and free the old node.

Before: TOP → 30 → 20 → 10 → NULL
After: TOP → 20 → 10 → NULL

Pop Algorithm Using Linked List

IF TOP == NULL
    PRINT "Underflow"
    RETURN FAILURE
END IF

OLD = TOP
VALUE = OLD.data
TOP = OLD.next

FREE(OLD)

RETURN VALUE

Peek Algorithm Using Linked List

IF TOP == NULL
    PRINT "Stack is Empty"
ELSE
    RETURN TOP.data
END IF

Linked List Stack Dry Run

Operation TOP Node Linked Stack
StartNULLEmpty
Push(10)1010 → NULL
Push(20)2020 → 10 → NULL
Push(30)3030 → 20 → 10 → NULL
Pop()2020 → 10 → NULL
Push(40)4040 → 20 → 10 → NULL
ClearNULLEmpty
Memory Trick: Linked Push = Attach → Move TOP. Linked Pop = Save → Move TOP → Free.

Complete C Program: Stack Using Linked List

In this program, malloc() creates new nodes and free() releases deleted nodes.

#include <stdio.h>
#include <stdlib.h>

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

typedef struct {
    Node *top;
} Stack;

void initialize(Stack *s) {
    s->top = NULL;
}

int isEmpty(const Stack *s) {
    return s->top == NULL;
}

int push(Stack *s, int value) {
    Node *node = malloc(sizeof *node);

    if (!node)
        return 0;

    node->data = value;
    node->next = s->top;
    s->top = node;

    return 1;
}

int pop(Stack *s, int *value) {
    if (isEmpty(s))
        return 0;

    Node *old = s->top;

    *value = old->data;
    s->top = old->next;

    free(old);
    return 1;
}

int peek(const Stack *s, int *value) {
    if (isEmpty(s))
        return 0;

    *value = s->top->data;
    return 1;
}

void display(const Stack *s) {
    if (isEmpty(s)) {
        puts("Stack is empty");
        return;
    }

    printf("TOP -> ");

    for (Node *cur = s->top;
         cur != NULL;
         cur = cur->next) {
        printf("%d ", cur->data);
    }

    puts("-> NULL");
}

void clear(Stack *s) {
    int ignored;

    while (pop(s, &ignored)) {
    }
}

int main(void) {
    Stack s;
    int value;

    initialize(&s);

    if (!push(&s, 10) ||
        !push(&s, 20) ||
        !push(&s, 30)) {
        puts("Memory allocation failed");
        clear(&s);
        return 1;
    }

    display(&s);

    if (peek(&s, &value))
        printf("Peek: %d\n", value);

    if (pop(&s, &value))
        printf("Pop: %d\n", value);

    if (!push(&s, 40)) {
        clear(&s);
        return 1;
    }

    display(&s);

    clear(&s);
    display(&s);

    if (!pop(&s, &value))
        puts("Underflow: stack is empty");

    return 0;
}

Expected Output

TOP -> 30 20 10 -> NULL
Peek: 30
Pop: 30
TOP -> 40 20 10 -> NULL
Stack is empty
Underflow: stack is empty

Why Do We Use Stack *s?

The Stack structure stores the TOP pointer. When a function receives Stack *s, it can change the original TOP pointer using s->top.

Memory Safety: After free(old), do not access the deleted node again. Move TOP before releasing the old node.

Array vs Linked List Stack Implementation

Both implementations follow LIFO, but their memory management and TOP representation are different.

Feature Array Stack Linked List Stack
Storage Contiguous array slots Connected nodes
TOP Integer index Pointer to first node
Empty Condition TOP == -1 TOP == NULL
Full Condition Fixed capacity reached Memory allocation can fail
Push Increase index and store Create node and update TOP
Pop Read item and decrease index Move TOP and free node
Pointer Storage Not required per element Required in every node
Growth Fixed in basic implementation Dynamic while memory permits
Memory Layout Contiguous Nodes can be separate
Implementation Usually simpler Requires pointer handling

Which Implementation Should You Choose?

Choose Array

When Capacity Is Known

Suitable when you want a simple implementation with contiguous storage and predictable capacity.

Choose Linked List

When Size Changes

Suitable when the number of Stack elements changes and dynamic memory allocation is acceptable.

Dynamically resizing arrays are also possible, but this chapter uses a fixed-size array for easier understanding.

Stack Implementation Errors and Edge Cases

Stack Overflow

A fixed array is full but another Push is attempted.

Stack Underflow

Pop or Peek is attempted on an empty Stack.

Lost Pointer

TOP changes incorrectly and old nodes become unreachable.

Memory Leak

Dynamically allocated memory is not released after deletion.

Use After Free

The program accesses a node after free() has released it.

Wrong Error Value

Returning -1 as an error can be unsafe because -1 may be a valid Stack element.

Debug Checklist: Is TOP initialized? Are overflow and underflow checked? Does Push update TOP correctly? Is old TOP saved before Pop? Are removed nodes freed?

Time and Space Complexity

Push, Pop and Peek operate at TOP, so they normally do not require traversal of all Stack elements.

Operation Array Stack Linked List Stack
Push O(1) O(1) pointer updates
Pop O(1) O(1)
Peek O(1) O(1)
isEmpty O(1) O(1)
Display O(n) O(n)
Total Storage O(CAPACITY) O(n) nodes

Here, n represents the number of elements in the Stack.

Exam Accuracy: A Linked List Stack does not have unlimited capacity. Its growth depends on available memory. Dynamic allocation and array resizing may have implementation-dependent costs.

Memory Tricks for Stack Implementation

A = Array

Index Memory Trick

Push: Increase, Insert.
Pop: Read, Reduce.
Empty: TOP = -1.

L = Linked

Pointer Memory Trick

Push: Connect, Change TOP.
Pop: Save, Shift, Free.
Empty: TOP = NULL.

Array TOP = Index | Linked TOP = Pointer

Important Exam Questions With Answers

2 Marks

Q1. What is Stack Implementation?

Stack Implementation is the method of storing Stack elements and performing operations using the LIFO principle. It can be implemented using an array or Linked List.

2 Marks

Q2. What is TOP in Array Stack?

TOP is an integer variable that stores the index of the last inserted element. Initially, TOP is generally -1.

2 Marks

Q3. What is TOP in Linked List Stack?

TOP is a pointer to the first node. When the Stack is empty, TOP contains NULL.

2 Marks

Q4. Define Stack Overflow and Underflow.

Overflow occurs when a Push cannot be completed because storage is unavailable. Underflow occurs when we try to remove an element from an empty Stack.

5 Marks

Q5. Explain Array Implementation of Stack.

Array Stack stores elements in consecutive array positions. An integer variable TOP keeps the index of the most recently inserted element.

Initially TOP = -1. During Push, TOP is increased and the value is inserted. During Pop, the top element is returned and TOP is decreased.

Push: TOP++, then insert
Pop: Read TOP, then TOP--

Both operations take O(1) time in a fixed array implementation.

5 Marks

Q6. Explain Linked List Implementation of Stack.

In Linked List Stack implementation, every node contains data and a next pointer. TOP points to the first node.

Push allocates a new node, connects it to old TOP and updates TOP.

Pop saves the first node, moves TOP to the next node and releases the removed node. Both operations involve constant pointer updates.

10 Marks

Q7. Compare Stack Implementation Using Array and Linked List.

A Stack is a linear Data Structure that follows the LIFO principle. It supports insertion and deletion at one end called TOP.

Array Implementation

In array implementation, Stack elements are stored in consecutive array positions. TOP is an integer index, initially set to -1.

Push increases TOP and inserts the element. Pop returns the top element and decreases TOP.

Linked List Implementation

In Linked List implementation, nodes are connected using pointers. TOP stores the address of the first node.

Push inserts a new node at the beginning, while Pop removes the first node and frees its memory.

Example

After Push(10), Push(20), Push(30), both implementations contain 30 at TOP. Pop removes 30, leaving 20 at TOP.

Advantages and Limitations

Array Stack provides simple, contiguous storage but has a fixed capacity in the basic implementation. Linked List Stack supports flexible growth but requires pointer storage and dynamic memory management.

Conclusion

Both implementations support basic O(1) Stack operations. The suitable implementation depends on capacity and memory management requirements.

Practice Questions

Practice 1: Capacity is 3. Push(5), Push(8), Push(9), Push(11). What happens?

The fourth Push fails with overflow. TOP = 2 and the Stack contains 5, 8, 9 from bottom to top.

Practice 2: TOP → 15 → 10 → NULL. Push(20), then Pop(). What is TOP?

Push makes 20 the TOP. Pop removes 20. The final TOP is 15.

Practice 3: Why must linked Push connect the new node before changing TOP?

The new node must connect to the old first node before TOP is updated. Otherwise, remaining nodes may become unreachable.

Practice 4: Can -1 be stored in Stack?

Yes. -1 is a valid integer element. The program should use a separate success or failure status rather than using -1 as the only error value.

One-Minute Revision

Array Stack: TOP is an index. Empty TOP = -1. Full TOP = CAPACITY - 1.

Linked List Stack: TOP is a pointer. Empty TOP = NULL. Push creates and connects nodes. Pop moves TOP and releases memory.

Both: Push, Pop and Peek work at TOP and normally take O(1) time.

Frequently Asked Questions

Which is better: Array Stack or Linked List Stack?

Array Stack is suitable when capacity is known and simple contiguous storage is preferred. Linked List Stack is useful when the number of elements changes.

Why does Array TOP start at -1?

Array indices begin at 0. The value -1 represents an empty Stack before the first valid position.

Why is Linked List TOP initially NULL?

NULL indicates that no first node exists.

Do Push and Pop take O(1) time?

Yes, basic fixed-array operations take O(1) time. Linked Stack operations involve O(1) pointer changes, apart from allocation and memory-management costs.

Why is free() needed in Linked List Stack?

Memory allocated using malloc() should be released when a node is no longer needed. free() releases the removed node.

What is the main difference in TOP?

Array Stack uses an integer TOP index, while Linked List Stack uses a TOP pointer.

Conclusion

Stack Implementation becomes easy when we understand how TOP changes after Push and Pop.

In Array Stack, TOP is an integer index. Push increases TOP and Pop decreases it.

In Linked List Stack, TOP is a pointer to the first node. Push connects a new node and updates TOP, while Pop removes and releases the old first node.

Both implementations follow the LIFO principle and provide fast Push, Pop and Peek operations.

Final Memory Trick: Array = Index Change. Linked List = Pointer Change.

For exams, practise TOP index dry runs and linked pointer-update order. These two concepts explain most Stack implementation questions.

Tags

Post a Comment

0 Comments
* Please Don't Spam Here. All the Comments are Reviewed by Admin.
Join Telegram Exam updates and free resources