📋 Blogger Post Content Generator
Topic: Stack Data Structure Explained with C Program — Copy the HTML below and paste directly into Blogger's HTML editor.
What is a Stack?
A Stack is a linear data structure that follows a specific order for inserting and removing elements. Unlike arrays where you can access any element by index, a stack restricts access to only one end — called the top of the stack.
A stack works exactly like a real-world stack of plates. You can only add a new plate on top, and you can only remove the topmost plate. You cannot access plates in the middle without removing the ones above them.
💡 Key Point: Stack is based on the LIFO (Last In, First Out) principle — the last element inserted is the first one to be removed.
📊 Stack Diagram
Elements are pushed on top and popped from the top only.
Real-World Analogies
- 🍽️ Stack of plates: You place and remove plates from the top only.
- 📚 Stack of books: The last book placed is the first one you pick up.
- 🌐 Browser back button: Every page visited is pushed; clicking Back pops the latest.
- ⌨️ Ctrl+Z (Undo): Each action is pushed onto a stack; Undo pops the most recent action.
The LIFO Principle
LIFO stands for Last In, First Out. This is the core rule of a stack. The element added most recently will be the first one removed. Consider the following sequence:
| Step | Operation | Stack State (bottom → top) | Top |
|---|---|---|---|
| 1 | Push(10) | [10] | 10 |
| 2 | Push(20) | [10, 20] | 20 |
| 3 | Push(30) | [10, 20, 30] | 30 |
| 4 | Pop() | [10, 20] | 20 |
| 5 | Pop() | [10] | 10 |
| 6 | Push(40) | [10, 40] | 40 |
Stack Operations
A stack supports the following fundamental operations:
🔹 Push
Inserts a new element at the top of the stack. If the stack is already full (in a fixed-size array), this causes a Stack Overflow error.
🔹 Pop
Removes and returns the top element. If the stack is empty, this causes a Stack Underflow error.
🔹 Peek / Top
Returns the top element without removing it. Useful when you want to inspect the top value without modifying the stack.
🔹 isEmpty
Returns true if the stack has no elements, otherwise false.
🔹 isFull
Returns true if the stack has reached its maximum capacity (applicable for array-based stacks).
| Operation | Description | Time Complexity |
|---|---|---|
| Push(x) | Insert element x at top | O(1) |
| Pop() | Remove and return top element | O(1) |
| Peek() | View top element | O(1) |
| isEmpty() | Check if stack is empty | O(1) |
| isFull() | Check if stack is full | O(1) |
Stack Implementation Using Array in C
The simplest and most common way to implement a stack in C is using an array. We use an integer variable top to track the index of the topmost element. When the stack is empty, top = -1.
Advantages: Simple to implement, fast access. Disadvantages: Fixed size — cannot grow beyond the defined maximum.
#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // Maximum size of stack
// Stack structure
struct Stack {
int arr[MAX];
int top;
};
// Initialize the stack
void initStack(struct Stack* s) {
s->top = -1;
}
// Check if the stack is empty
int isEmpty(struct Stack* s) {
return s->top == -1;
}
// Check if the stack is full
int isFull(struct Stack* s) {
return s->top == MAX - 1;
}
// Push an element onto the stack
void push(struct Stack* s, int value) {
if (isFull(s)) {
printf("Stack Overflow! Cannot push %d\n", value);
return;
}
s->arr[++s->top] = value;
printf("Pushed: %d\n", value);
}
// Pop an element from the stack
int pop(struct Stack* s) {
if (isEmpty(s)) {
printf("Stack Underflow! Stack is empty.\n");
return -1;
}
return s->arr[s->top--];
}
// Peek at the top element without removing
int peek(struct Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
return -1;
}
return s->arr[s->top];
}
// Display all stack elements
void display(struct Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
return;
}
printf("Stack (top to bottom): ");
for (int i = s->top; i >= 0; i--) {
printf("%d ", s->arr[i]);
}
printf("\n");
}
int main() {
struct Stack s;
initStack(&s);
printf("=== Stack Using Array in C ===\n\n");
push(&s, 10);
push(&s, 20);
push(&s, 30);
push(&s, 40);
printf("\n");
display(&s);
printf("Top element (peek): %d\n", peek(&s));
printf("\nPopping elements:\n");
printf("Popped: %d\n", pop(&s));
printf("Popped: %d\n", pop(&s));
printf("\nAfter popping:\n");
display(&s);
return 0;
}📤 Output
=== Stack Using Array in C ===
Pushed: 10
Pushed: 20
Pushed: 30
Pushed: 40
Stack (top to bottom): 40 30 20 10
Top element (peek): 40
Popping elements:
Popped: 40
Popped: 30
After popping:
Stack (top to bottom): 20 10🔍 How it works: We start with top = -1 meaning the stack is empty. Each push() increments top first (pre-increment), then stores the value. Each pop() returns the value at top and then decrements it (post-decrement).
Stack Implementation Using Linked List in C
The array-based stack has a major limitation — it has a fixed size. If you don't know how many elements you'll store in advance, a Linked List-based stack is a better choice. It grows dynamically and uses only as much memory as needed.
In this approach, the head node of the linked list represents the top of the stack. Pushing adds a new node at the head, and popping removes it from the head.
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
};
// Stack structure
struct Stack {
struct Node* top;
int size;
};
// Initialize the stack
void initStack(struct Stack* s) {
s->top = NULL;
s->size = 0;
}
// Check if stack is empty
int isEmpty(struct Stack* s) {
return s->top == NULL;
}
// Push element onto the stack
void push(struct Stack* s, int value) {
struct Node* newNode =
(struct Node*) malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = value;
newNode->next = s->top; // point to old top
s->top = newNode; // update top
s->size++;
printf("Pushed: %d (Stack size: %d)\n", value, s->size);
}
// Pop element from the stack
int pop(struct Stack* s) {
if (isEmpty(s)) {
printf("Stack Underflow! Stack is empty.\n");
return -1;
}
struct Node* temp = s->top;
int val = temp->data;
s->top = temp->next;
free(temp);
s->size--;
return val;
}
// Peek at the top element
int peek(struct Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
return -1;
}
return s->top->data;
}
// Display all elements
void display(struct Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
return;
}
struct Node* curr = s->top;
printf("Stack (top to bottom): ");
while (curr != NULL) {
printf("%d ", curr->data);
curr = curr->next;
}
printf("\n");
}
// Free all allocated memory
void freeStack(struct Stack* s) {
while (!isEmpty(s)) pop(s);
}
int main() {
struct Stack s;
initStack(&s);
printf("=== Stack Using Linked List in C ===\n\n");
push(&s, 100);
push(&s, 200);
push(&s, 300);
printf("\n");
display(&s);
printf("Top element: %d\n", peek(&s));
printf("\nPopping elements:\n");
printf("Popped: %d\n", pop(&s));
printf("Popped: %d\n", pop(&s));
printf("\n");
display(&s);
freeStack(&s);
printf("\nAll memory freed successfully.\n");
return 0;
}Stack Overflow and Stack Underflow
🔴 Stack Overflow
This error occurs when you attempt to push an element onto a stack that is already full. In array-based stacks, this happens when top == MAX - 1. In recursive programs, infinite recursion without a proper base case also causes a system-level stack overflow.
⚠️ Warning: Infinite recursion in C will crash your program with a segmentation fault due to stack overflow. Always define a proper base case in recursive functions!
🔵 Stack Underflow
This error occurs when you try to pop from an empty stack. We guard against this by checking top == -1 (array) or top == NULL (linked list) before performing the pop operation.
#include <stdio.h>
#define MAX 3 // Small size to trigger overflow easily
int stack[MAX];
int top = -1;
void push(int val) {
if (top == MAX - 1) {
printf("[OVERFLOW] Cannot push %d — Stack is full!\n", val);
return;
}
stack[++top] = val;
printf("Pushed: %d\n", val);
}
int pop() {
if (top == -1) {
printf("[UNDERFLOW] Cannot pop — Stack is empty!\n");
return -1;
}
return stack[top--];
}
int main() {
printf("-- Testing Stack Overflow --\n");
push(1); push(2); push(3);
push(4); // Triggers overflow
printf("\n-- Testing Stack Underflow --\n");
printf("Popped: %d\n", pop());
printf("Popped: %d\n", pop());
printf("Popped: %d\n", pop());
pop(); // Triggers underflow
return 0;
}Real-World Applications of Stack
Stacks are one of the most widely used data structures in computer science and software development. Here are the major areas where stacks are applied:
When a function is called, it is pushed onto the system call stack. When it returns, it is popped. This is how recursion works internally.
Compilers use stacks to evaluate arithmetic expressions and convert between infix, prefix, and postfix notations.
IDEs and compilers use stacks to verify that parentheses
(), braces {}, and brackets [] are correctly matched.Applications like MS Word and Photoshop store actions in a stack. Undo pops the most recent action, and Redo re-applies it.
Each page you visit is pushed onto a history stack. The Back button pops the most recent page.
Depth-First Search in graphs uses a stack (or recursion) to explore nodes by going as deep as possible before backtracking.
📌 Bonus Program: Balanced Parentheses Checker in C
This is a classic and popular interview question that uses a stack to verify whether all brackets in a string are properly matched and closed.
#include <stdio.h>
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) { stack[++top] = c; }
char pop() { return (top == -1) ? '\0' : stack[top--]; }
int isEmpty() { return top == -1; }
int isBalanced(char* expr) {
int n = strlen(expr);
top = -1; // reset stack before each check
for (int i = 0; i < n; i++) {
char ch = expr[i];
// Push opening brackets onto stack
if (ch == '(' || ch == '{' || ch == '[')
push(ch);
// Match closing brackets with top of stack
else if (ch == ')' || ch == '}' || ch == ']') {
char t = pop();
if ((ch == ')' && t != '(') ||
(ch == '}' && t != '{') ||
(ch == ']' && t != '['))
return 0; // Mismatch found
}
}
return isEmpty(); // Balanced only if stack is empty
}
int main() {
char* tests[] = {
"({[]})",
"((()))",
"{[()}",
"[(])",
"{a + (b * c)}"
};
printf("=== Balanced Parentheses Checker ===\n\n");
for (int i = 0; i < 5; i++) {
printf("%-20s => %s\n",
tests[i],
isBalanced(tests[i]) ? "Balanced ✓" : "Not Balanced ✗"
);
}
return 0;
}Time & Space Complexity
All core stack operations run in constant time, making the stack extremely efficient for its use cases.
| Operation | Array Stack | Linked List Stack | Notes |
|---|---|---|---|
| Push | O(1) | O(1) | Always constant time |
| Pop | O(1) | O(1) | Always constant time |
| Peek | O(1) | O(1) | Just read top pointer |
| isEmpty | O(1) | O(1) | Simple comparison |
| Space | O(n) | O(n) | n = number of elements |
| Feature | Array Stack | Linked List Stack |
|---|---|---|
| Memory | Static / Fixed | Dynamic / Grows as needed |
| Overflow Risk | Yes (when full) | No (until RAM runs out) |
| Ease of Implementation | Simple | Moderate (uses pointers) |
| Cache Performance | Better (contiguous memory) | Slower (scattered nodes) |
| Memory Waste | Possible (pre-allocated) | No (exact usage) |
Conclusion
In this tutorial, we covered the Stack data structure completely with working C programs:
- ✅ We understood what a stack is and its LIFO principle
- ✅ We explored all stack operations — push, pop, peek, isEmpty, isFull
- ✅ We implemented a stack using an Array in C
- ✅ We implemented a stack using a Linked List in C
- ✅ We handled Stack Overflow and Underflow with proper error messages
- ✅ We built a Balanced Parentheses Checker — a real interview problem
- ✅ We compared Array vs Linked List stack implementations
The Stack is one of the most important data structures in computer science. Mastering it will help you understand recursion, compiler design, expression evaluation, graph traversal, and much more. Practice the programs above by running them locally and experimenting with different inputs.
📌 What's Next? Now that you've mastered Stacks, explore Queues (FIFO), Linked Lists, and Binary Trees to continue building your data structures foundation!
👇 Copy everything below and paste into your Blogger post's HTML editor:
Post a Comment