Stack Data Structure: Understanding LIFO
Learn how the Stack data structure works using the LIFO principle, with simple examples, basic operations, C implementation, and real-world applications.
Imagine a pile of plates in a restaurant. When someone adds a new plate, they place it on top. When someone needs a plate, they take the top one first.
The plate placed last is the first one to be removed. This is exactly how a Stack data structure works.
1. What Is a Stack?
A Stack is a linear data structure in which elements are added and removed from the same end, called the top.
It follows the LIFO (Last In, First Out) principle.
This means the last element inserted into the stack is the first one to be removed.
Example: Suppose we insert three elements:
Push 10
Push 20
Push 30
Our stack now looks like this:
TOP
┌────┐
│ 30 │
├────┤
│ 20 │
├────┤
│ 10 │
└────┘
If we remove an element, 30 will be removed first because it was inserted last.
The stack will then look like this:
TOP
┌────┐
│ 20 │
├────┤
│ 10 │
└────┘
This is the LIFO principle in action.
2. Basic Operations of a Stack
A stack mainly supports the following operations:
1. Push
Adds a new element to the top of the stack.
Example:
Before: 10, 20
Push 30
After: 10, 20, 30
2. Pop
Removes the top element from the stack.
Example:
Before: 10, 20, 30
Pop
After: 10, 20
Here, 30 is removed.
3. Peek (or Top)
Returns the top element without removing it.
Example:
Stack: 10, 20, 30
Peek → 30
The stack remains unchanged.
4. isEmpty
Checks whether the stack contains any elements.
It returns true if the stack is empty and false otherwise.
3. Stack Implementation Using an Array in C
A stack can be implemented using an array. We use a variable called top to keep track of the index of the top element.
Initially, top is set to -1, which indicates that the stack is empty.
Let’s implement the basic operations:
#include <stdio.h>
#define MAX 5
int stack[MAX];
int top = -1;
void push(int value) {
if (top == MAX - 1) {
printf("Stack Overflow\n");
return;
}
stack[++top] = value;
}
void pop() {
if (top == -1) {
printf("Stack Underflow\n");
return;
}
printf("Removed: %d\n", stack[top--]);
}
void peek() {
if (top == -1) {
printf("Stack is empty\n");
return;
}
printf("Top element: %d\n", stack[top]);
}
int main() {
push(10);
push(20);
push(30);
peek();
pop();
peek();
return 0;
}
Output:
Top element: 30
Removed: 30
Top element: 20
Let’s understand two important conditions in this implementation:
- Stack Overflow: Occurs when we try to insert an element into a full stack.
- Stack Underflow: Occurs when we try to remove an element from an empty stack.
4. Time Complexity of Stack Operations
Most basic stack operations take constant time because they work only with the top element.
| Operation | Time Complexity |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
| isEmpty | O(1) |
Here, O(1) means the operation takes a constant amount of time, regardless of how many elements are in the stack.
5. Applications of Stacks
Stacks are used in many real-world computing operations.
- Undo and Redo: Text editors use stacks to keep track of previous actions.
- Browser History: The Back operation can use a stack-like approach to return to previously visited pages.
- Function Calls: Programming languages use a call stack to manage function calls and their execution.
- Expression Evaluation: Stacks help evaluate mathematical expressions and check matching brackets.
- Backtracking: Algorithms can use stacks to return to an earlier state when a path does not work.
A Stack is a linear data structure that follows the LIFO principle: Last In, First Out.
Its main operations are Push, Pop, Peek, and isEmpty. Since elements are added and removed from the top, these operations generally take O(1) time.
In the next article, we’ll explore practical applications of stacks, including Parenthesis Checking, Infix to Postfix Conversion, and Expression Evaluation.
Originally published at farhanpaal.com — https://farhanpaal.com/articles/stack-data-structure-understanding-lifo/
Keep a copy
Read offline as a printout or PDF.
farhanpaal.com