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.
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.
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.
Add at TOP
Insert a new element at the active top end.
Remove TOP
Return the most recent element and update TOP.
Read TOP
Read the top value without removing it.
Two Ways of Representing TOP
Array Stack
TOP stores an integer index. In an empty zero-based Stack, TOP = -1.
Linked List Stack
TOP stores the address of the first node. When empty, TOP = NULL.
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.
Bottom → 10, 20, 30 → TOP
Index 3 is still available, so one more Push can succeed.
Important Conditions
No active Stack elements exist.
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
Check whether the Stack is already full.
Move TOP to the next free index.
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
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 | -1 | Empty | No elements |
| Push(10) | 0 | 10 | Index 0 |
| Push(20) | 1 | 10, 20 | Index 1 |
| Push(30) | 2 | 10, 20, 30 | Index 2 |
| Pop() | 1 | 10, 20 | Returns 30 |
| Push(40) | 2 | 10, 20, 40 | Index 2 reused |
| Push(50) | 3 | 10, 20, 40, 50 | Full |
| Push(60) | 3 | Unchanged | Overflow |
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
Set TOP
Starts the Stack at -1.
Check Space
Checks whether the final slot is occupied.
Change TOP
Insert or remove the active top element.
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
How Push Updates Pointers
Suppose TOP points to a node containing 20. Now insert 30.
Allocate memory and store 30.
Set its next pointer to the current TOP.
Make TOP point to the new node.
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.
If TOP is NULL, the Stack is empty.
Store the first node in a temporary pointer.
Make TOP point to the next node.
Save the removed value and free the old node.
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 |
|---|---|---|
| Start | NULL | Empty |
| Push(10) | 10 | 10 → NULL |
| Push(20) | 20 | 20 → 10 → NULL |
| Push(30) | 30 | 30 → 20 → 10 → NULL |
| Pop() | 20 | 20 → 10 → NULL |
| Push(40) | 40 | 40 → 20 → 10 → NULL |
| Clear | NULL | Empty |
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.
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?
When Capacity Is Known
Suitable when you want a simple implementation with contiguous storage and predictable capacity.
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.
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.
Memory Tricks for Stack Implementation
Index Memory Trick
Push: Increase, Insert.
Pop: Read, Reduce.
Empty: TOP = -1.
Pointer Memory Trick
Push: Connect, Change TOP.
Pop: Save, Shift, Free.
Empty: TOP = NULL.
Important Exam Questions With Answers
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.
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.
Q3. What is TOP in Linked List Stack?
TOP is a pointer to the first node. When the Stack is empty, TOP contains NULL.
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.
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.
Both operations take O(1) time in a fixed array implementation.
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.
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.
