What is a Stack in Data Structures?
A stack is one of the most fundamental concepts in data structures and algorithms (DSA). It is a linear data structure used to store elements in a particular order so that operations like insertion and deletion follow a specific rule. In a stack, elements are added and removed only from one end called the top.
A stack mainly supports three operations: push (insert), pop (remove), and peek (view top element).
To understand it easily, imagine stacking plates in a kitchen. When you place plates on top of each other, the last plate placed will be the first one removed. You cannot remove a plate from the middle without removing the plates above it. This simple idea perfectly represents how a stack works inside a computer system.
Stacks are widely used in programming, compilers, operating systems, and algorithms. They are used for managing function calls, evaluating mathematical expressions, and implementing undo features in applications.
Operations such as push and pop generally run in constant time, meaning their speed does not depend on the number of elements in the stack. Understanding stacks makes it easier to learn more advanced structures such as queues, trees, and graphs.
Real-Life Examples of Stack Concept
The concept of a stack is not limited to computers. We use stack-like behavior in everyday life without even realizing it.
The last plate placed on the stack is the first plate removed — exactly how a stack data structure behaves.
To take a book from the bottom, you must first remove all books above it. Access is only possible from the top.
Each page visited is pushed onto a stack. The back button pops the latest page and returns to the previous one.
Every action is stored in a stack. When you press undo, the most recent action is removed first.
Stack Concept – LIFO Principle
Understanding LIFO (Last In First Out)
The fundamental concept behind stacks is called LIFO – Last In, First Out. This principle means the element inserted last into the stack will be the first element removed. The newest element is always processed before older elements.
In a stack structure, there are two main positions: top and bottom. Elements are always inserted and deleted from the top position. When a new element is added, it becomes the new top of the stack.
Consider the following sequence of operations:
Top → C
B
A
If we perform a pop operation, C will be removed first, because it was the last element inserted. This perfectly follows the LIFO rule.
Visual Example of LIFO
After pushing 10, 20, 30:
20
10
After popping all elements:
Pop → 20
Pop → 10
Notice how the last inserted value (30) is removed first. The LIFO principle is used in computer memory — when multiple functions run in a program, each function is pushed onto a call stack. When a function finishes execution, it is popped from the stack.
Basic Terminologies in Stack
Top Pointer
In a stack, the top pointer is extremely important. It indicates the position of the most recently inserted element. Every time an element is pushed onto the stack, the top pointer moves upward. When an element is popped, the top pointer moves downward.
For example, consider a stack implemented using an array of size 5. Initially, the stack is empty, and the top pointer is set to -1. When we push the first element, the top pointer becomes 0. When we push another element, the top pointer becomes 1, and so on.
The top pointer helps the system know where the next element should be inserted and which element should be removed. Understanding the top pointer is important when implementing stacks using arrays or linked lists.
Stack Overflow and Stack Underflow
Two common problems can occur while working with stacks:
🔺 Stack Overflow
Happens when we try to push an element into a stack that is already full (fixed array size).
Push A, B, C
Push D → Overflow
🔻 Stack Underflow
Occurs when we try to pop an element from an empty stack. No elements exist to remove.
Pop → Underflow
Building the Structure
Implementation of Stack
Array Implementation of Stack
One of the simplest ways to implement a stack is by using an array. A fixed-size array stores stack elements, and a variable called top keeps track of the index of the top element.
Push Algorithm
1. Check if stack is full
2. If full → Overflow
3. Otherwise increase top
4. Insert element at stack[top]
Pop Algorithm
1. Check if stack is empty
2. If empty → Underflow
3. Otherwise return stack[top]
4. Decrease top
Array Example (Stack size = 5, Top = 2):
| Index | Value |
|---|---|
| 0 | 10 |
| 1 | 20 |
| 2 ← top | 30 |
| 3 | - |
| 4 | - |
Array implementation is simple and fast because elements are stored in contiguous memory. However, its main limitation is that the stack size is fixed. If the stack becomes full, we cannot add more elements unless we increase the array size.
C++ PROGRAM — Stack Using Array
using namespace std;
#define MAX 5
int stackArr[MAX];
int top = -1;
void push(int value) {
if(top == MAX - 1) { cout << "Stack Overflow\n"; return; }
top++; stackArr[top] = value;
cout << value << " pushed into stack\n";
}
void pop() {
if(top == -1) { cout << "Stack Underflow\n"; return; }
cout << stackArr[top] << " popped from stack\n";
top--;
}
void peek() {
if(top == -1) cout << "Stack is empty\n";
else cout << "Top element is: " << stackArr[top] << endl;
}
void display() {
if(top == -1) { cout << "Stack is empty\n"; return; }
cout << "Stack elements:\n";
for(int i = top; i >= 0; i--) cout << stackArr[i] << endl;
}
int main() {
push(10); push(20); push(30);
peek(); display(); pop(); display();
return 0;
}
20 pushed into stack
30 pushed into stack
Top element is: 30
Stack elements: 30 / 20 / 10
30 popped from stack
Stack elements: 20 / 10
Linked List Implementation of Stack
Unlike arrays, linked lists use dynamic memory allocation, which means the stack can grow as needed. Each node contains data and a pointer to the next node.
Push Operation
1. Create a new node
2. Store data in the node
3. Point the node to the current top
4. Update top pointer
Pop Operation
1. Check if stack is empty
2. Store the top node temporarily
3. Move top pointer to next node
4. Delete old node
C++ PROGRAM — Stack Using Linked List
using namespace std;
struct Node { int data; Node* next; };
Node* top = NULL;
void push(int value) {
Node* newNode = new Node();
newNode->data = value; newNode->next = top; top = newNode;
cout << value << " pushed into stack\n";
}
void pop() {
if(top == NULL) { cout << "Stack Underflow\n"; return; }
Node* temp = top;
cout << temp->data << " popped from stack\n";
top = top->next; delete temp;
}
void peek() {
if(top == NULL) cout << "Stack is empty\n";
else cout << "Top element is: " << top->data << endl;
}
void display() {
Node* temp = top; cout << "Stack elements:\n";
while(temp != NULL) { cout << temp->data << endl; temp = temp->next; }
}
int main() {
push(5); push(15); push(25);
peek(); display(); pop(); display();
return 0;
}
15 pushed into stack
25 pushed into stack
Top element is: 25
Stack elements: 25 / 15 / 5
25 popped from stack
Stack elements: 15 / 5
Core Mechanics
Stack Operations
Push · Pop · Peek
Push Operation
The push operation is used to add an element to the top of the stack. When a push operation occurs, the element becomes the new top element. Push operations run in O(1) time complexity.
Before Push 30:
10
After Push 30:
20
10
Pop Operation
The pop operation removes the top element from the stack. After removing the element, the top pointer moves to the next element. Pop also runs in O(1) time complexity. Pop is used in expression evaluation, backtracking, and recursion management.
Before Pop:
40
30
After Pop:
30
Peek Operation
The peek operation allows us to view the top element without removing it. This is useful when we need to check the latest value stored in the stack while keeping the stack unchanged.
Stack:
60
50
Peek Result:
Stack remains unchanged
Real-World Usage
Applications of Stack
🔢 Expression Evaluation
Stacks are widely used to evaluate mathematical expressions such as infix, postfix, and prefix expressions. In compilers, stacks help process operators and operands in the correct order.
Push 5 → Push 3 → Pop both → Add → Push result 8
Result = 8
C++ PROGRAM — Postfix Expression
#include <stack>
using namespace std;
int main() {
stack<int> s;
int a = 5, b = 3;
s.push(a); s.push(b);
int x = s.top(); s.pop();
int y = s.top(); s.pop();
int result = x + y;
s.push(result);
cout << "Result of postfix expression: " << s.top();
return 0;
}
🔗 Parenthesis Matching
Stacks are very useful in checking whether parentheses in an expression are balanced. This technique is used in compilers and code editors to detect syntax errors.
• Push opening brackets onto the stack
• When a closing bracket appears, pop the stack
• If stack becomes empty at end → Balanced ✓
C++ PROGRAM — Parenthesis Matching
#include <stack>
using namespace std;
bool checkBalanced(string expr) {
stack<char> s;
for(char ch : expr) {
if(ch == '(') s.push(ch);
else if(ch == ')') {
if(s.empty()) return false;
s.pop();
}
}
return s.empty();
}
int main() {
string expression = "(a+b)*(c+d)";
if(checkBalanced(expression)) cout << "Parentheses are Balanced";
else cout << "Parentheses are NOT Balanced";
return 0;
}
📞 Function Calls (Call Stack)
When a program runs, functions call other functions. The system uses a call stack to manage these function calls. Every time a function is called, its information is pushed onto the stack. When the function finishes, it is popped.
Stack: Top → functionB / functionA / main
C++ PROGRAM — Function Call Stack
using namespace std;
void functionB() { cout << "Function B is executed\n"; }
void functionA() {
cout << "Function A is executed\n";
functionB();
}
int main() {
cout << "Main function starts\n";
functionA();
cout << "Main function ends\n";
return 0;
}
Function A is executed
Function B is executed
Main function ends
↩️ Undo Operations in Software
Many software applications such as text editors, graphics editors, and IDEs use stacks to implement undo operations. Every action a user performs is pushed onto the stack. When the user presses Undo, the latest action is popped and reversed.
Undo: Restore "World" → Remove "World" addition → Remove "Hello"
C++ PROGRAM — Undo Operation
#include <stack>
using namespace std;
int main() {
stack<string> actions;
actions.push("Type Hello");
actions.push("Type World");
actions.push("Delete World");
cout << "Undo operations:\n";
while(!actions.empty()) {
cout << "Undo: " << actions.top() << endl;
actions.pop();
}
return 0;
}
Undo: Delete World
Undo: Type World
Undo: Type Hello
Advantages and Limitations of Stack
✅ Advantages
⚠️ Limitations
Summary
| Concept | Description |
|---|---|
| Stack | Linear data structure |
| Principle | LIFO (Last In First Out) |
| Basic Operations | Push, Pop, Peek |
| Implementation | Array or Linked List |
| Applications | Expression evaluation, Parenthesis checking, Function calls, Undo operations |
Conclusion
Stacks are one of the most essential and widely used data structures in computer science. Their simple yet powerful LIFO principle allows programs to manage data efficiently. By allowing insertion and deletion only from the top, stacks provide predictable and fast operations.
Students learning programming will encounter stacks frequently while studying algorithms, compilers, operating systems, and software development. Understanding stack implementation using arrays and linked lists helps build strong programming fundamentals.
Beyond theoretical learning, stacks also power real-world applications such as expression evaluation, parenthesis checking, function call management, and undo features in software.
When learners truly understand stacks, many programming concepts suddenly become clearer. It acts as a gateway to understanding more advanced topics in data structures and algorithms.
Frequently Asked Questions
1. What is a stack in data structures?
A stack is a linear data structure that follows the Last In First Out (LIFO) principle where the last element inserted is the first element removed.
2. What are the main operations of a stack?
The three main operations are: Push — insert element, Pop — remove element, Peek — view top element.
3. What is stack overflow?
Stack overflow occurs when we try to insert an element into a full stack, especially in array-based implementations.
4. What is stack underflow?
Stack underflow occurs when we attempt to remove an element from an empty stack.
5. Where are stacks used in real life?
Stacks are used in expression evaluation, parenthesis checking, function calls in programming, and undo/redo operations in applications.
0 Comments
If you have any doubts, Please let me know