Stack in C
Subject: Data Structures and Algorithms · Language: C · Level: intermediate · 6 min read
Implement stack operations push, pop, and peek using arrays.
A stack is a linear data structure that follows LIFO: Last In, First Out. The last inserted element is removed first.
Think of plates kept one above another. You add a new plate on the top, and you also remove a plate from the top. A stack works in the same way.
Stacks are used when the most recent item should be handled first, such as function calls, undo actions, expression evaluation, and backtracking.
Main Stack Operations
- `push` inserts an element
- `pop` removes the top element
- `peek` reads the top element without removing it
- `isEmpty` checks whether the stack has no elements
- `isFull` checks whether an array stack has no free space
Top Variable
In an array-based stack, `top` stores the index of the latest inserted element. When the stack is empty, `top` is usually `-1`.
When we push, `top` moves forward. When we pop, `top` moves backward.
Push Operation
Before pushing, check whether the stack is already full. If space is available, increase `top` and store the new value.
Pop Operation
Before popping, check whether the stack is empty. If it is not empty, return the top value and decrease `top`.
Peek Operation
`peek` is useful when we only want to see the top value. It does not remove anything from the stack.
```c
#include <stdio.h>
#define MAX 5
int stack[MAX];
int top = -1;
int isEmpty(void) {
return top == -1;
}
int isFull(void) {
return top == MAX - 1;
}
void push(int value) {
if (isFull()) {
printf("Stack overflow\n");
return;
}
top++;
stack[top] = value;
}
int pop(void) {
if (isEmpty()) {
printf("Stack underflow\n");
return -1;
}
int value = stack[top];
top--;
return value;
}
int peek(void) {
if (isEmpty()) {
printf("Stack is empty\n");
return -1;
}
return stack[top];
}
int main(void) {
push(10);
push(20);
printf("Top = %d\n", peek());
printf("Popped = %d\n", pop());
printf("Top after pop = %d\n", peek());
return 0;
}
```
Overflow and Underflow
- Overflow happens when we push into a full stack
- Underflow happens when we pop from an empty stack
These checks are important because they prevent invalid array access.
Array Stack and Linked List Stack
A stack can be implemented using an array or a linked list.
- Array stack is simple and easy for beginners
- Array stack has fixed capacity
- Linked list stack can grow dynamically
- Linked list stack needs pointer and memory handling
Stack and Function Calls
When a C function is called, information about that function call is stored on the call stack. When the function finishes, its stack frame is removed.
This is why recursion also uses stack memory. If recursion is too deep, stack overflow can happen.
Balanced Parentheses Idea
Stacks are commonly used to check brackets in expressions.
When an opening bracket appears, push it. When a closing bracket appears, pop and match it with the latest opening bracket. This works because the latest opened bracket must close first.
Time Complexity
`push`, `pop`, and `peek` take O(1) time because they work only at the top of the stack.
Uses
Stacks are used in recursion, undo operations, expression evaluation, syntax checking, backtracking, browser history, and depth-first search.
Practice Question
Write a C program that pushes five numbers into a stack, prints the top element, pops two numbers, and then prints the remaining top element.