Stack — Data Structures

Stack – Understanding the Last-In-First-Out Magic

Imagine a pile of plates in your kitchen.
When you add a plate, you place it on top of the pile.
And when you need a plate, you take the top one first.

That’s exactly how a stack works in programming!
It’s a special type of data structure that follows the rule:

👉 Last In, First Out (LIFO)

Meaning, the last item you put in will be the first one to come out — just like that top plate.

---

💡 What is a Stack?

A stack is a simple data structure that stores elements in a particular order —
the element that goes in last is the first to be removed.

You can imagine it like a vertical tube where data enters and leaves only from the top.

---

⚙️ Main Operations of a Stack

There are only two main actions you can perform on a stack — but these two are enough to do a lot!

1. PUSH → Add (insert) an element to the top of the stack.
2. POP → Remove (delete) the element from the top of the stack.

There’s also one more handy action:

• PEEK (or TOP) → Just look at the top element without removing it.

---

🧩 Diagram – Stack Operations

Initial Stack: (empty)

     ↓ PUSH 10
+----+
| 10 |
+----+

     ↓ PUSH 20
+----+
| 20 |
+----+
| 10 |
+----+

     ↓ PUSH 30
+----+
| 30 |  ← Top
+----+
| 20 |
+----+
| 10 |
+----+

     ↑ POP
(Remove 30)
+----+
| 20 |  ← Top
+----+
| 10 |
+----+

Every time you push, the stack grows upward.
Every time you pop, it shrinks from the top.

---

🧠 Real-Life Analogy

Think of a stack of books on your desk:

• When you put a new book down, it goes on top.
• When you pick one to read, you take the top one.
  You can’t easily grab the book at the bottom without first removing the ones above — that’s the LIFO principle in action.

---

📘 Stack in Memory (Call Stack)

Inside your computer, stacks are used all the time, even when you don’t realize it!

When a program runs, every time a function is called, its details are pushed onto a call stack.
When that function finishes, its details are popped off.

Example:

main() calls A()
A() calls B()

Call stack (top to bottom):
B()
A()
main()

When B() finishes, it’s removed from the stack, and control goes back to A().
This makes function calls organized and efficient.

---

🧮 Stack Implementation

A stack can be built using:

1. Array – fixed-size stack.
2. Linked List – flexible size, grows as needed.

Example (Array Implementation):

int stack[10];
int top = -1;

// Push operation
stack[++top] = value;

// Pop operation
value = stack[top--];

Here, top keeps track of the topmost element.

---

⚠️ Stack Overflow and Underflow

Just like a pile of plates can fall if you stack too many,
a computer stack can also run into problems:

• Stack Overflow: When you push an element into a full stack.
• Stack Underflow: When you try to pop from an empty stack.

These errors show that every structure has its limits!

---

🧩 Diagram – Stack Concept

   +---------+
   |   40    |  ← Top (last pushed)
   +---------+
   |   30    |
   +---------+
   |   20    |
   +---------+
   |   10    |
   +---------+
   |  Bottom |
   +---------+

Top: The most recent element.
Bottom: The first element that was pushed.

---

🌍 Applications of Stack

Stacks are used everywhere in computer science:

• Function calls (as we discussed)
• Expression evaluation (like converting infix to postfix)
• Undo/Redo in text editors
• Backtracking (like maze solving or recursion)
• Browser history (go back to the last page you visited)

---

✅ Advantages of Stack

• Simple and easy to use
• Helps in managing function calls and recursion
• Efficient for problems where data is processed in reverse order

---

❌ Disadvantages of Stack

• Limited access — you can only work with the top element
• Fixed size (if implemented using an array)

---