Ugenz Academy/Tutorial

Stack

12 min read2,316 words

Reading progress

Keep learning

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:

OperationMeaning
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:

OperationTime
PushO(1)
PopO(1)
Top/PeekO(1)
EmptyO(1)
SizeO(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

FeatureArrayLinked ListStack
Main ideaIndexed collectionConnected nodesLIFO collection
AccessRandomSequentialTop only
InsertDepends on positionDepends on positionTop
DeleteDepends on positionDepends on positionTop
Main operationIndex accessLinksPush/Pop
Typical accessarr[i]Traversetop()

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:

  1. Implement stack using array
  2. Implement stack using linked list
  3. Reverse a string using stack
  4. Balanced parentheses
  5. Remove adjacent duplicates
  6. Evaluate postfix expression
  7. Convert infix to postfix
  8. Convert infix to prefix
  9. Next Greater Element
  10. Previous Greater Element
  11. Next Smaller Element
  12. Min Stack
  13. Stock Span Problem
  14. Largest Rectangle in Histogram
  15. Valid Parentheses
  16. 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

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy