A stack is a very useful data structure that follows the principle of Last In, First Out (LIFO). This means that the last element added to the stack is the first one to be removed. Stacks are used in many areas of programming such as function call management, undo/redo operations, and expression evaluation.
In this article, we will build the stack step by step using arrays. First, we will write a simple static stack with push and pop operations. Next, we will add more helper functions like peek(), isEmpty(), and isFull(). Finally, we will go deeper and create a dynamic stack that can grow in size using malloc() and realloc().
Understanding the Problem
The challenge in implementing a stack lies in managing the top pointer correctly. A stack must also be able to handle overflow (when it’s full) and underflow (when it’s empty).
When we use arrays, a stack has a fixed size. This is simple but not always flexible. To improve this, we can use dynamic memory allocation so that the stack can grow as needed. Let’s start with the basic implementation and then move to more advanced versions.
Program 1: Simple Stack with Push and Pop
The following program demonstrates a simple stack using arrays with basic push and pop operations.
#include <stdio.h>
#define MAX 5 // Maximum size of the stack
int stack[MAX];
int top = -1; // Initially, stack is empty
// Function to push an element into the stack
void push(int value) {
if (top == MAX - 1) {
printf("Stack Overflow! Cannot push %d\n", value);
} else {
top++;
stack[top] = value;
printf("Pushed %d into the stack.\n", value);
}
}
// Function to pop an element from the stack
void pop() {
if (top == -1) {
printf("Stack Underflow! Cannot pop.\n");
} else {
printf("Popped %d from the stack.\n", stack[top]);
top--;
}
}
// Function to display the stack elements
void display() {
if (top == -1) {
printf("Stack is empty.\n");
} else {
printf("Stack contents: ");
for (int i = 0; i <= top; i++) {
printf("%d ", stack[i]);
}
printf("\n");
}
}
int main() {
push(10);
push(20);
push(30);
display();
pop();
display();
push(40);
push(50);
push(60);
push(70); // This should trigger overflow
display();
return 0;
}In this program, the stack is represented by an array of fixed size. The top variable starts at -1, which indicates that the stack is empty. When the push function is called, the top is incremented, and the new value is stored in the stack. If the stack is already full, it prints an overflow message.
The pop function removes the topmost element by printing it and then decrementing the top variable. If the stack is empty, it prints an underflow message instead. The display function helps to view the current elements in the stack from bottom to top.
Program 2: Menu-Driven Stack Implementation
The next program expands the stack implementation by allowing the user to interact with the stack through a menu-driven system. This provides an option to push, pop, or display the stack contents based on the user’s choice.
#include <stdio.h>
#define MAX 5
int stack[MAX];
int top = -1;
void push(int value) {
if (top == MAX - 1) {
printf("Stack Overflow!\n");
} else {
stack[++top] = value;
printf("%d pushed onto stack.\n", value);
}
}
void pop() {
if (top == -1) {
printf("Stack Underflow!\n");
} else {
printf("%d popped from stack.\n", stack[top--]);
}
}
void display() {
if (top == -1) {
printf("Stack is empty.\n");
} else {
printf("Stack elements: ");
for (int i = 0; i <= top; i++) {
printf("%d ", stack[i]);
}
printf("\n");
}
}
int main() {
int choice, value;
while (1) {
printf("\n--- Stack Menu ---\n");
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter 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:
display();
break;
case 4:
return 0;
default:
printf("Invalid choice! Try again.\n");
}
}
}Here, the program runs in a loop and displays a menu with four choices: push, pop, display, and exit. The user can push elements until the stack is full, remove them until it is empty, or display the contents. This program makes the stack operations interactive and practical.
Program 3: Stack with Utility Functions
This program improves the earlier stack by adding useful helper functions.
#include <stdio.h>
#define MAX 5
int stack[MAX];
int top = -1;
// Check if stack is empty
int isEmpty() {
return top == -1;
}
// Check if stack is full
int isFull() {
return top == MAX - 1;
}
// Push operation
void push(int value) {
if (isFull()) {
printf("Stack Overflow!\n");
} else {
stack[++top] = value;
printf("%d pushed into stack.\n", value);
}
}
// Pop operation
void pop() {
if (isEmpty()) {
printf("Stack Underflow!\n");
} else {
printf("%d popped from stack.\n", stack[top--]);
}
}
// Peek operation (view top element)
void peek() {
if (isEmpty()) {
printf("Stack is empty.\n");
} else {
printf("Top element is %d\n", stack[top]);
}
}
// Display contents of stack
void display() {
if (isEmpty()) {
printf("Stack is empty.\n");
} else {
printf("Stack contents: ");
for (int i = 0; i <= top; i++) {
printf("%d ", stack[i]);
}
printf("\n");
}
}
int main() {
push(5);
push(15);
push(25);
peek();
display();
pop();
display();
return 0;
}Here, isEmpty() and isFull() help us avoid underflow and overflow errors. The peek() function allows us to check the top element without removing it. These small utilities make the stack more practical and reliable in use.
Program 4: Dynamic Stack Using malloc() and realloc()
Now, let’s make the stack dynamic. Instead of fixing the size with a constant, we allocate memory at runtime. When the stack is full, we use realloc() to expand it.
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *arr; // Pointer to hold stack elements
int capacity; // Current maximum size
int top; // Index of top element
} Stack;
// Create a new stack
Stack* createStack(int capacity) {
Stack* stack = (Stack*) malloc(sizeof(Stack));
stack->capacity = capacity;
stack->top = -1;
stack->arr = (int*) malloc(stack->capacity * sizeof(int));
return stack;
}
// Check if stack is empty
int isEmpty(Stack* stack) {
return stack->top == -1;
}
// Push with dynamic resizing
void push(Stack* stack, int value) {
if (stack->top == stack->capacity - 1) {
stack->capacity *= 2;
stack->arr = (int*) realloc(stack->arr, stack->capacity * sizeof(int));
printf("Stack resized to capacity %d\n", stack->capacity);
}
stack->arr[++stack->top] = value;
printf("%d pushed.\n", value);
}
// Pop operation
void pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow!\n");
} else {
printf("%d popped.\n", stack->arr[stack->top--]);
}
}
// Peek operation
void peek(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty.\n");
} else {
printf("Top element is %d\n", stack->arr[stack->top]);
}
}
// Display stack contents
void display(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty.\n");
} else {
printf("Stack contents: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->arr[i]);
}
printf("\n");
}
}
int main() {
Stack* stack = createStack(2); // Start with small size
push(stack, 10);
push(stack, 20);
push(stack, 30); // triggers resize
push(stack, 40);
display(stack);
peek(stack);
pop(stack);
display(stack);
free(stack->arr);
free(stack);
return 0;
}In this implementation, the stack starts with a small capacity. If it becomes full, we double the size dynamically using realloc(). This ensures that the stack grows as needed without running into overflow errors.
FAQs
Q1: Why use arrays for a stack instead of linked lists?
Arrays are simple and provide faster access since they use continuous memory. Linked lists are more flexible but require extra memory for pointers.
Q2: What’s the advantage of a dynamic stack?
A dynamic stack grows as needed, avoiding overflow errors and making memory usage more efficient.
Q3: How does realloc() work here?
When the stack is full, realloc() increases its size, usually doubling the capacity, so more elements can be added without overflow.
Q4: Can a stack hold multiple data types?
Not directly with arrays. If you want multiple types, you can use void* pointers, unions, or structures that hold generic data.
Conclusion
We started with a basic stack implemented using arrays, then added helper functions like peek(), isEmpty(), and display(). Finally, we built a dynamic stack that can grow in size using malloc() and realloc().
This progression shows how a simple idea can grow into a powerful and flexible data structure. Stacks are fundamental in computer science, and understanding both static and dynamic implementations helps in building efficient software.
References & Additional Resources
A selection of textbooks, tutorials, and references for learning about stacks and their implementation in C.
- Kernighan, B.W., & Ritchie, D.M. (1988). The C Programming Language (2nd Edition). Prentice Hall – The classic text on C programming, covering arrays, pointers, and functions that are key to implementing stacks.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Comprehensive coverage of data structures, including stacks, with practical C examples.
- GeeksforGeeks – Stack Data Structure – Stack basics, operations (
push,pop,peek), and implementation using arrays and linked lists. - Tutorialspoint – Stack in Data Structure – Beginner-friendly guide to stack concepts, implementation, and operations.
- C Standard Library Documentation – Official reference for standard C functions and libraries often used in stack implementation.
