Stack Data Structure in C Programming
What is a Stack?
A stack is a linear data structure that follows the LIFO (Last In First Out) principle. The last element added to the stack will be the first one to be removed. It has two main operations:
📌 Basic Stack Concepts
Stack Operations
- Push: Add element to top O(1)
- Pop: Remove top element O(1)
- Peek/Top: View top element O(1)
- isEmpty: Check if empty O(1)
LIFO Principle (Last In First Out)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 100
int stack[MAX_SIZE];
int top = -1;
bool isEmpty() {
return top == -1;
}
bool isFull() {
return top == MAX_SIZE - 1;
}
void push(int value) {
if (isFull()) {
printf("Stack Overflow!\n");
return;
}
stack[++top] = value;
}
int pop() {
if (isEmpty()) {
printf("Stack Underflow!\n");
exit(1);
}
return stack[top--];
}
int peek() {
if (isEmpty()) {
printf("Stack is empty\n");
exit(1);
}
return stack[top];
}
Stack Operations
Push Operation
Adds an element to the top of the stack:
- Check if stack is full (stack overflow)
- Increment top pointer
- Add new element at top position
Pop Operation
Removes the top element from the stack:
- Check if stack is empty (stack underflow)
- Return the top element
- Decrement top pointer
Stack Operations
Push
Adds an element to the top of the stack.
void push(int value) {
if (top == SIZE-1) {
printf("Stack Overflow");
} else {
stack[++top] = value;
}
}
Pop
Removes and returns the top element from the stack.
int pop() {
if (top == -1) {
printf("Stack Underflow");
return -1;
} else {
return stack[top--];
}
}
Peek
Returns the top element without removing it.
int peek() {
if (top == -1) {
printf("Stack is Empty");
return -1;
} else {
return stack[top];
}
}
🚀 Stack Applications
Function Calls
Call stack manages function execution and local variables
Expression Evaluation
Infix to postfix conversion and evaluation
Undo Mechanisms
Text editors use stacks for undo/redo operations
DFS Algorithm
Depth-First Search uses stack for traversal
Compiler Design
Syntax parsing and memory management
Backtracking
Maze solving and pathfinding algorithms
Stack Applications
1. Expression Evaluation
Stacks are used to evaluate expressions (infix to postfix conversion) and for syntax parsing.
// Example: Evaluating postfix expression // "2 3 * 5 +" becomes 2*3 + 5 = 11
2. Function Call Management
The call stack stores information about active subroutines/functions in a program.
// When function A calls function B: // A's state is pushed to stack // B executes // A's state is popped from stack
3. Backtracking Algorithms
Used in maze solving, puzzle games, and depth-first search where you need to backtrack.
// Example: Maze solving // Push current position // If dead end, pop to backtrack // Continue until exit found
4. Balanced Parentheses
Checking for balanced parentheses, brackets, or tags in code/HTML/XML.
// Example: Check "{([])}"
// Push opening brackets
// When closing bracket found, pop and match
// Stack empty at end = balanced
Practice Questions
1. Implement a stack using linked list
struct Node {
int data;
struct Node* next;
};
struct Node* top = NULL;
void push(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = top;
top = newNode;
}
int pop() {
if (top == NULL) {
printf("Stack Underflow\n");
exit(1);
}
struct Node* temp = top;
int val = temp->data;
top = top->next;
free(temp);
return val;
}
2. Check for balanced parentheses
bool isBalanced(char exp[]) {
char stack[MAX_SIZE];
int top = -1;
for (int i = 0; exp[i] != '\0'; i++) {
if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[') {
stack[++top] = exp[i];
} else {
if (top == -1) return false;
char top_char = stack[top--];
if ((exp[i] == ')' && top_char != '(') ||
(exp[i] == '}' && top_char != '{') ||
(exp[i] == ']' && top_char != '[')) {
return false;
}
}
}
return top == -1;
}