Understanding Stacks in DSA
When you start learning Data Structures and Algorithms (DSA), one of the first and most useful concepts you’ll come across is a Stack. A stack is a type of data structure that works on a very simple principle called LIFO, which stands for Last In, First Out. This means that the last item you add to the stack will be the first one to be removed, just like a real stack of objects.
Imagine a stack of plates in your kitchen. When you wash a plate, you place it on top of the pile. When you need a plate to eat, you take the one from the top. You don’t pull one out from the middle or bottom. This is how a stack works in programming too, you can only add or remove items from the top.
The LIFO Principle in Real Life
The LIFO (Last In, First Out) behavior of a stack can be seen in many everyday situations. Think about the undo and redo buttons in a text editor. The most recent action you did is the first one to be undone when you press Ctrl + Z. Similarly, when you're browsing the internet and press the back button, your browser takes you to the last page you visited, the one most recently added to your browsing history. These are all examples of stacks working quietly in the background.
How Does a Stack Work?
A stack is a linear data structure that allows a few basic operations to manage data efficiently. You can push an element to add it to the top of the stack, and pop to remove the top element. If you want to view the top element without removing it, you can use peek() (also called top() in some languages). You can also check if the stack is empty using the isEmpty() method. These simple operations make stacks powerful for solving various programming problems.
The four main operations on a stack are:
- push(x): Adds an element x to the top of the stack.
- pop(): Removes the top element from the stack.
- peek() or top(): Returns the top element without removing it.
- isEmpty(): Checks whether the stack is empty.
Example. Stack Implementation
A program that uses C++ STL stack and shows all basic operations.
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> myStack;
myStack.push(10);
myStack.push(20);
myStack.push(30);
cout << "Top element: " << myStack.top() << endl;
myStack.pop();
cout << "Top element after pop: " << myStack.top() << endl;
if (myStack.empty()) {
cout << "Stack is empty" << endl;
} else {
cout << "Stack is not empty" << endl;
}
return 0;
}
Output
![Output]()
Real-Life Uses of Stack in Software
Stacks are used everywhere in software development. A common example is function calls, where each function is placed on the call stack, allowing the computer to remember where to return after a function finishes. Stacks also power features like undo-redo in text editors, backtracking in algorithms, expression evaluation, and browser history navigation. Even compilers use stacks to check if parentheses and tags are properly balanced in your code.
Here are some real-world uses of stacks:
- Function calls (Call Stack)
- Undo/Redo functionality in text editors like MS Word or Notepad
- Backtracking algorithms, such as solving mazes or puzzles
- Expression parsing and evaluation
- HTML/XML tag matching for correctness
Common Coding Questions Using Stack
Balanced Parentheses
Question: Check whether the brackets in a string are balanced (e.g., "(a+b)" is valid, but "((a+b)" is not).
#include <iostream>
#include <stack>
using namespace std;
bool isBalanced(string expr) {
stack<char> s;
for (char ch : expr) {
if (ch == '(' || ch == '{' || ch == '[') {
s.push(ch);
} else if (ch == ')' || ch == '}' || ch == ']') {
if (s.empty()) return false;
char top = s.top();
s.pop();
if ((ch == ')' && top != '(') ||
(ch == '}' && top != '{') ||
(ch == ']' && top != '[')) {
return false;
}
}
}
return s.empty();
}
int main() {
string expr = "{[()]}";
if (isBalanced(expr))
cout << "Balanced" << endl;
else
cout << "Not Balanced" << endl;
return 0;
}
#Output: Balanced
Reverse a String Using a Stack
Question: Reverse the characters of a string using a stack.
#include <iostream>
#include <stack>
using namespace std;
string reverseString(string input) {
stack<char> s;
for (char ch : input) {
s.push(ch);
}
string reversed = "";
while (!s.empty()) {
reversed += s.top();
s.pop();
}
return reversed;
}
int main() {
string str = "hello";
cout << "Original: " << str << endl;
cout << "Reversed: " << reverseString(str) << endl;
return 0;
}
#Output
#Original: Aishwarya
#Reversed: ayrawhsiA
Evaluate Postfix Expression
Problem: Given a postfix expression like "23*4+", evaluate it.
This means: (2 * 3) + 4 = 10
#include <iostream>
#include <stack>
#include <cctype>
using namespace std;
int evaluatePostfix(string expr) {
stack<int> s;
for (char ch : expr) {
if (isdigit(ch)) {
s.push(ch - '0'); // Convert char to int
} else {
int b = s.top(); s.pop();
int a = s.top(); s.pop();
switch (ch) {
case '+': s.push(a + b); break;
case '-': s.push(a - b); break;
case '*': s.push(a * b); break;
case '/': s.push(a / b); break;
}
}
}
return s.top();
}
int main() {
string expr = "23*4+";
cout << "Result of postfix expression: " << evaluatePostfix(expr) << endl;
return 0;
}
#Output: Result of postfix expression: 10
Summary
A stack is a simple yet powerful data structure that works on the Last In, First Out (LIFO) principle. It allows four basic operations: push to add an element, pop to remove the top element, peek (or top) to view the top element, and isEmpty to check if the stack is empty. In C++, you can easily implement stacks using the Standard Template Library (STL) with the stack class. Stacks are widely used in real-world applications like function call management (call stack), undo-redo features, browser history, parsing expressions, and algorithmic backtracking. Practicing classic stack problems such as balanced parentheses, string reversal, and postfix evaluation strengthens your understanding of DSA and prepares you for coding interviews and real-world software development.