A stack is a simple yet powerful data structure that follows the Last In, First Out (LIFO) principle. Imagine stacking plates in your kitchen — the last plate you put on top is the first one you take off. Similarly, in a stack, the last element pushed is the first one popped.
Stacks are widely used in programming for tasks such as function call management, expression evaluation, undo operations in text editors, and memory management. There are two common ways to implement a stack: using arrays or linked lists.
In this article, we will focus on implementing a stack using a linked list. Unlike arrays, linked lists do not require predefined sizes, allowing the stack to grow dynamically as needed.
Understanding the Problem
When using a linked list to implement a stack, each element is represented by a node. A node contains two parts:
- The data field, which stores the value.
- A pointer, which links the current node to the next one.
The stack maintains a pointer called top, which always points to the last node added.
- When pushing a new element, a node is created and linked at the top.
- When popping an element, the top node is removed, and
topis updated to point to the next node.
This structure ensures that operations such as push and pop can be done in constant time (O(1)).
Program: Stack Using Linked List
Now let’s write a complete menu-driven C program that allows users to push, pop, peek, and display elements interactively.
#include <stdio.h>
#include <stdlib.h>
// Define the node structure
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* top = NULL; // Stack top pointer
// Push operation
void push(int value) {
Node* newNode = (Node*) malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = value;
newNode->next = top;
top = newNode;
printf("%d pushed to stack.\n", value);
}
// Pop operation
void pop() {
if (top == NULL) {
printf("Stack Underflow! Cannot pop.\n");
return;
}
Node* temp = top;
printf("%d popped from stack.\n", top->data);
top = top->next;
free(temp);
}
// Peek operation
void peek() {
if (top == NULL) {
printf("Stack is empty.\n");
} else {
printf("Top element is %d\n", top->data);
}
}
// Display stack elements
void display() {
if (top == NULL) {
printf("Stack is empty.\n");
return;
}
Node* current = top;
printf("Stack contents: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// Main function with menu
int main() {
int choice, value;
while (1) {
printf("\n--- Stack Menu ---\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Peek\n");
printf("4. Display\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value to push: ");
scanf("%d", &value);
push(value);
break;
case 2:
pop();
break;
case 3:
peek();
break;
case 4:
display();
break;
case 5:
printf("Exiting program.\n");
exit(0);
default:
printf("Invalid choice. Try again.\n");
}
}
return 0;
}This program provides an interactive menu where the user can choose an operation: push, pop, peek, display, or exit.
When the user selects the push option, the program asks for a value and inserts it at the top of the stack. Choosing pop removes the top element and frees its memory. Peek shows the current top element without removing it, while display traverses the stack from top to bottom to show all values.
The loop continues until the user chooses to exit, making it a convenient way to practice stack operations interactively.
FAQs
Q1: Why should I use a linked list instead of an array for a stack?
A linked list is more flexible because it grows dynamically, while arrays require resizing if you exceed their initial capacity.
Q2: Is push and pop always O(1) in linked list implementation?
Yes. Since both operations involve only manipulating the top pointer, they execute in constant time.
Q3: Can I traverse a stack implemented with a linked list?
Yes. The display function demonstrates how to traverse the stack from top to bottom. However, remember that stacks are usually used with only push and pop operations.
Q4: How can I clear all elements from the stack?
You can repeatedly pop elements until the stack becomes empty. This ensures that all dynamically allocated memory is freed properly.
Conclusion
Stacks are a fundamental data structure, and understanding how to implement them is essential for any programmer. Using a linked list makes stacks dynamic, eliminating the need for predefined sizes.
In this article, we built a menu-driven stack program in C, allowing users to push, pop, peek, and display elements interactively. Along the way, we also highlighted common mistakes and provided best practices to avoid them.
By mastering both array-based and linked list-based stacks, you will gain a deeper understanding of data structures and memory management in C.
References & Additional Resources
A collection of textbooks and tutorials for learning stack implementation using linked lists in C.
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – The classic C reference covering pointers, memory management, and structures essential for linked list and stack implementation.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Comprehensive coverage of data structures, including stacks with arrays and linked lists.
- GeeksforGeeks: Stack using Linked List – Step-by-step explanation and code examples of stack implementation with singly linked lists.
- Tutorialspoint: C Pointers – Clear explanation of pointer usage in C, crucial for handling linked lists.
- Cprogramming.com: Pointers in C – Beginner-friendly guide to pointers, structures, and dynamic memory.
- C Standard Library Documentation – Official reference for standard C libraries and functions.
