Stack
A Stack is a linear data structure that follows the rule:
LIFO — Last In, First Out
This means:
The element that is inserted last is removed first.
Real-life example: Stack of plates 🍽️
Imagine plates stacked on top of each other:
┌───────┐ │ Plate │ ← Last added ├───────┤ │ Plate │ ├───────┤ │ Plate │ ← First added └───────┘
You normally take the top plate first.
That's exactly how a stack works.
1. Understanding LIFO
Suppose we insert:
10 20 30 40
The stack becomes:
TOP ↓ ┌────┐ │ 40 │ ← Last inserted ├────┤ │ 30 │ ├────┤ │ 20 │ ├────┤ │ 10 │ ← First inserted └────┘
Now remove one element.
40 comes out first.
TOP ↓ ┌────┐ │ 30 │ ├────┤ │ 20 │ ├────┤ │ 10 │ └────┘
Then 30.
Then 20.
Then 10.
So:
Inserted: 10 → 20 → 30 → 40 Removed: 40 → 30 → 20 → 10
That's LIFO.
2. Basic Stack Operations
A stack mainly has four important operations:
| Operation | Meaning |
|---|---|
push() | Add an element |
pop() | Remove the top element |
top() / peek() | See the top element |
empty() | Check whether stack is empty |
There is also:
size()
to find the number of elements.
3. Push
Push means adding an element to the top.
Initially:
EMPTY
Push 10:
TOP ↓ ┌────┐ │ 10 │ └────┘
Push 20:
TOP ↓ ┌────┐ │ 20 │ ├────┤ │ 10 │ └────┘
Push 30:
TOP ↓ ┌────┐ │ 30 │ ├────┤ │ 20 │ ├────┤ │ 10 │ └────┘
So:
push(10) push(20) push(30)
gives:
30 20 10
with 30 at the top.
4. Pop
Pop means removing the top element.
Suppose:
TOP ↓ ┌────┐ │ 30 │ ├────┤ │ 20 │ ├────┤ │ 10 │ └────┘
Perform:
pop()
30 is removed.
Now:
TOP ↓ ┌────┐ │ 20 │ ├────┤ │ 10 │ └────┘
Another pop():
TOP ↓ ┌────┐ │ 10 │ └────┘
5. Peek / Top
Sometimes we don't want to remove the element.
We only want to know what is currently on top.
That's what top() or peek does.
Suppose:
TOP ↓ ┌────┐ │ 30 │ ├────┤ │ 20 │ ├────┤ │ 10 │ └────┘
Then:
top() → 30
The stack remains unchanged:
TOP ↓ 30 20 10
6. Stack Using an Array
A stack can be implemented using an array.
Example:
int stack[5];
We need a variable to track the top.
For example:
int top = -1;
Why -1?
Because initially there is no element.
top = -1 Stack: EMPTY
After inserting 10:
top = 0
10 ↑ top
After inserting 20:
top = 1
20 ← top 10
7. Push Using an Array
Basic implementation:
int stack[5]; int top = -1;
Push:
stack[++top] = 10;
Then:
top = 0 [10]
Push 20:
stack[++top] = 20;
Now:
top = 1 [10] [20] ← top
Push 30:
stack[++top] = 30;
Now:
[10] [20] [30] ← top
8. Pop Using an Array
To remove the top element:
top--;
Suppose:
[10] [20] [30] ← top
After:
top--;
we logically have:
[10] [20] ← top
The old 30 is no longer considered part of the stack.
A safer pop implementation can first check whether the stack is empty.
9. Stack Overflow
Suppose our stack has capacity:
5 elements
And it already contains:
10 20 30 40 50
Now we try:
push(60)
There is no available space.
This situation is called:
Stack Overflow
With an array-based fixed-size stack:
Capacity = 5 Current size = 5 push() → Overflow
10. Stack Underflow
Now suppose:
Stack = EMPTY
We try:
pop()
There is nothing to remove.
This is called:
Stack Underflow
So remember:
Overflow → trying to add when stack is full Underflow → trying to remove when stack is empty
11. Stack Using std::stack in C++
In C++, the STL provides:
stack
We can use:
#include <iostream> #include <stack> using namespace std; int main() { stack<int> s; s.push(10); s.push(20); s.push(30); cout << s.top(); return 0; }
Output:
30
Because 30 was inserted last.
12. Complete Basic Example
#include <iostream> #include <stack> using namespace std; int main() { stack<int> s; s.push(10); s.push(20); s.push(30); cout << "Top: " << s.top() << endl; s.pop(); cout << "Top after pop: " << s.top() << endl; cout << "Size: " << s.size() << endl; return 0; }
Output:
Top: 30 Top after pop: 20 Size: 2
13. Checking Whether Stack Is Empty
Use:
s.empty()
Example:
if (s.empty()) { cout << "Stack is empty"; } else { cout << "Stack is not empty"; }
It returns:
true
or:
false
14. Printing All Stack Elements
Suppose:
10 20 30 40
We can repeatedly look at the top and pop:
while (!s.empty()) { cout << s.top() << " "; s.pop(); }
Output:
40 30 20 10
Notice:
This empties the stack.
If you need to preserve it, you can work on a copy:
stack<int> temp = s;
15. Stack Using Linked List
A stack doesn't have to use an array.
We can also implement it using a linked list.
Remember our linked list:
10 → 20 → 30 → NULL
For a stack, we can treat the beginning as the top:
TOP ↓ 30 → 20 → 10 → NULL
Push
Insert at the beginning:
Before: TOP ↓ 20 → 10 → NULL
Push 30:
TOP ↓ 30 → 20 → 10 → NULL
This is:
O(1)
Pop
Remove from the beginning:
TOP ↓ 30 → 20 → 10
Pop:
TOP ↓ 20 → 10
Also:
O(1)
So a linked-list implementation can provide constant-time push and pop.
16. Stack Using Linked List — Concept
Node:
struct Node { int data; Node* next; };
Top:
Node* top = nullptr;
Push:
new node ↓ TOP → new node → old top
Pop:
TOP → next node
This is directly connected to the linked-list topic you just learned.
17. Stack Complexity
For a normal stack implementation:
| Operation | Time |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Top/Peek | O(1) |
| Empty | O(1) |
| Size | O(1) |
This is one reason stacks are extremely useful.
18. Where Are Stacks Used?
Stacks are used everywhere in computer science.
Important applications include:
1. Function calls
When a function calls another function:
main() ↓ functionA() ↓ functionB()
The system needs to remember where to return.
This is handled using a call stack.
19. Call Stack
Consider:
void C() { cout << "C"; } void B() { C(); } void A() { B(); } int main() { A(); }
Execution:
main() ↓ A() ↓ B() ↓ C()
Conceptually the call stack grows:
TOP ↓ C() B() A() main()
When C() finishes:
C() → removed
Then:
TOP ↓ B() A() main()
Then B() finishes.
This is why function calls naturally follow a stack-like structure.
20. Undo / Redo
Think about a text editor.
You perform:
Type A Type B Type C
History:
A → B → C
Press Undo:
C removed
Press Undo again:
B removed
The latest action is undone first.
That's LIFO.
21. Browser Back Button
Suppose you visit:
Google ↓ YouTube ↓ GitHub ↓ Wikipedia
Press Back.
You go:
Wikipedia → GitHub
Then:
GitHub → YouTube
Then:
YouTube → Google
The most recent page is handled first.
Stack-like behavior is useful for browser history.
22. Balanced Parentheses
Stacks are extremely important for checking parentheses.
Example:
( [ { } ] )
This is balanced.
But:
( [ } )
is not balanced.
The basic idea:
When we see an opening bracket:
( [ {
we push it.
When we see a closing bracket:
) ] }
we check the top.
Example:
Input: ( [ ] )
Process:
( ↓ push '(' [ ↓ push '[' ] ↓ top is '[' → pop ) ↓ top is '(' → pop
At the end:
Stack = empty
Therefore balanced.
23. Example: Balanced Parentheses in C++
A simple version:
#include <iostream> #include <stack> using namespace std; int main() { string s = "({[]})"; stack<char> st; for(char ch : s) { if(ch == '(' || ch == '{' || ch == '[') { st.push(ch); } else if(ch == ')' || ch == '}' || ch == ']') { if(st.empty()) { cout << "Not Balanced"; return 0; } char top = st.top(); if((ch == ')' && top != '(') || (ch == '}' && top != '{') || (ch == ']' && top != '[')) { cout << "Not Balanced"; return 0; } st.pop(); } } if(st.empty()) cout << "Balanced"; else cout << "Not Balanced"; return 0; }
Output:
Balanced
This is a classic stack problem.
24. Expression Evaluation
Stacks are also used for mathematical expressions.
For example:
2 + 3 * 4
Computer programs use stack-based techniques for expression processing.
Important concepts include:
Infix Prefix Postfix
For example:
Infix: A + B Postfix: A B + Prefix: + A B
Stacks are heavily used when converting and evaluating these expressions.
25. Recursion and Stack
This becomes very important in your next DSA topics.
Suppose:
void fun(int n) { if(n == 0) return; cout << n << " "; fun(n - 1); }
Calling:
fun(3);
creates calls:
fun(3) ↓ fun(2) ↓ fun(1) ↓ fun(0)
These function calls are managed using the call stack.
So when you study:
Recursion
you will see stacks again.
26. Stack vs Queue
These two are easy to confuse.
Stack
LIFO Last In ↓ First Out
Example:
10 20 30 ← removed first
Queue
FIFO First In ↓ First Out
Example:
10 → 20 → 30 ↑ removed first
Think:
Stack = pile of plates Queue = people standing in a line
Your next roadmap topic after Stack is Queue, where this difference becomes very important.
27. Stack vs Array vs Linked List
| Feature | Array | Linked List | Stack |
|---|---|---|---|
| Main idea | Indexed collection | Connected nodes | LIFO collection |
| Access | Random | Sequential | Top only |
| Insert | Depends on position | Depends on position | Top |
| Delete | Depends on position | Depends on position | Top |
| Main operation | Index access | Links | Push/Pop |
| Typical access | arr[i] | Traverse | top() |
Important:
A stack is an abstract data structure/behavior. It can be implemented using an array, vector, or linked list.
For example:
Stack │ ├── Array implementation │ ├── Vector implementation │ └── Linked List implementation
28. Common Stack Problems
As you progress in DSA, you will encounter:
- Implement stack using array
- Implement stack using linked list
- Reverse a string using stack
- Balanced parentheses
- Remove adjacent duplicates
- Evaluate postfix expression
- Convert infix to postfix
- Convert infix to prefix
- Next Greater Element
- Previous Greater Element
- Next Smaller Element
- Min Stack
- Stock Span Problem
- Largest Rectangle in Histogram
- Valid Parentheses
- Undo/Redo systems
Some of these later become monotonic stack problems.
29. Important Concept: Top
The most important pointer/index in a stack is:
top
Visualize:
TOP ↓ ┌────┐ │ 40 │ ├────┤ │ 30 │ ├────┤ │ 20 │ ├────┤ │ 10 │ └────┘
All normal stack operations happen at the top.
push → top pop → top peek → top
That's why these operations are usually O(1).
30. The Most Important Mental Model
Remember:
PUSH ↓ ┌────┐ │ 40 │ ← TOP ├────┤ │ 30 │ ├────┤ │ 20 │ ├────┤ │ 10 │ └────┘ ↑ POP
You add and remove from the same end.
Therefore:
Stack = LIFO = Last In, First Out
Final Summary
Stack
LIFO Last In → First Out
Main operations
push() → add pop() → remove top top() → see top empty() → check empty size() → number of elements
Complexity
push() → O(1) pop() → O(1) top() → O(1) empty() → O(1)
Implementations
Stack ├── Array ├── Vector └── Linked List
Important applications
Function calls Recursion Undo/Redo Browser history Parentheses matching Expression evaluation DFS Backtracking
The key thing to remember is simply:
STACK 30 ← last inserted 20 10 ← first inserted pop() ↓ 30 ← removed first