Stacks (last-in, first-out) in Intro to Computing - Full Explanation

Introduction

Imagine you have a stack of plates on a table. You can only add or remove the top plate. This problem of managing items in a strict order is solved by a stack in computing.

Explanation

Last-In, First-Out (LIFO) Principle

A stack works like a pile where the last item added is the first one to be taken out. This means you always interact with the top item only. No items can be removed from the middle or bottom until the ones above are removed first.

Stacks follow the last-in, first-out rule, meaning the newest item is accessed first.

Push Operation

Adding an item to the stack is called a push. This places the new item on the top of the stack, making it the first to be removed next time. The stack grows upward as more items are pushed.

Push adds a new item to the top of the stack.

Pop Operation

Removing an item from the stack is called a pop. This takes the top item off the stack and returns it. After popping, the next item below becomes the new top.

Pop removes the top item from the stack.

Peek Operation

Peeking means looking at the top item without removing it. This lets you see what is next to be popped without changing the stack. It helps check the current top safely.

Peek shows the top item without removing it.

Stack Overflow and Underflow

Stack overflow happens when you try to push an item but the stack is full. Underflow happens when you try to pop from an empty stack. Both are errors that need careful handling.

Overflow and underflow are errors when pushing to a full stack or popping from an empty one.

Real World Analogy

Think of a stack of books on a desk. You add new books on top and remove books only from the top. You cannot take a book from the middle without removing the ones above it first.

Last-In, First-Out (LIFO) Principle → Books stacked so the last placed book is the first one you pick up

Push Operation → Placing a new book on top of the stack

Pop Operation → Taking the top book off the stack

Peek Operation → Looking at the top book without removing it

Stack Overflow and Underflow → Trying to add a book when the stack is too high or removing a book when none are left

Diagram

Diagram

┌─────────┐
│  Top    │ ← Newest item (last pushed)
├─────────┤
│  Item 3 │
├─────────┤
│  Item 2 │
├─────────┤
│  Item 1 │
└─────────┘
(push adds here, pop removes here)

This diagram shows a stack with items added and removed only from the top.

Key Facts

Stack → A data structure where items are added and removed from the top only.

LIFO → Last-In, First-Out means the last item added is the first removed.

Push → Operation to add an item to the top of the stack.

Pop → Operation to remove the top item from the stack.

Peek → Operation to view the top item without removing it.

Stack Overflow → Error when pushing to a full stack.

Stack Underflow → Error when popping from an empty stack.

Common Confusions

Thinking stacks allow removing items from anywhere inside the stack.

Thinking stacks allow removing items from anywhere inside the stack. Stacks only allow removing the top item; you cannot remove items from the middle or bottom without popping the ones above.

Believing peek removes the top item.

Believing peek removes the top item. Peek only shows the top item without removing it, unlike pop which removes it.

Summary

Stacks let you add and remove items only from the top, following last-in, first-out order.

Push adds an item on top; pop removes the top item; peek views the top without removing.

Trying to pop from empty or push to full stacks causes errors called underflow and overflow.