Stacks

Welcome to the World of Stacks!

Hello! Today, we are going to explore one of the most fundamental and useful tools in a programmer's toolkit: the Stack. This data structure belongs to the "Fundamental Data Structures" section of your Oxford AQA syllabus.

Think of a stack like a real-life stack of cafeteria trays or a pile of books. If you put a new book on top of the pile, it is the first one you have to take off to get to the others. It sounds simple, but this concept helps computers manage everything from your "Undo" button to complex mathematical calculations!

What is a Stack?

A stack is a linear data structure that follows a very specific rule called LIFO.
LIFO stands for Last-In, First-Out.

Imagine a Pez candy dispenser. The last candy you push into the top is the very first one that pops out when you use it. This is exactly how a stack works in computer science: the last item added is the first one to be removed.

Key Terms to Remember:

• LIFO: Last-In, First-Out. The core rule of a stack.
• Static Data Structure: If we implement a stack using an array, it has a fixed size that cannot change while the program is running.
• Dynamic Data Structure: If a stack can grow or shrink in size, it is considered dynamic.

Quick Review: Why is it called LIFO? Because the item that went in last is the first one to leave!

Standard Stack Operations

To use a stack, we primarily use three main "actions" or operations. Don't worry if these names sound fancy; they are just simple instructions for the computer.

1. Push

The push operation adds a new item to the top of the stack.
Analogy: Placing a new plate on top of a stack of dishes.

2. Pop

The pop operation removes the item that is currently at the top of the stack.
Analogy: Taking the top plate off the stack to use it.

3. Peek (or Top)

The peek operation lets you look at the value of the item on the top of the stack without removing it.
Analogy: Looking at the cover of the top book in a pile without picking it up.

Common Mistake: Students often think pop just looks at the item. Remember: pop removes it; peek only looks at it!

Key Takeaway: Use push to add, pop to remove, and peek to see what's on top.

How to Implement a Stack Using an Array

In your exam, you need to understand how a stack is built using a one-dimensional array.

To keep track of where we are, we use a special variable called a Top Pointer. This pointer stores the index (the position number) of the item currently at the top of the stack.

Step-by-Step: Adding an Item (Pushing)

1. Check if the stack is full (to avoid "Stack Overflow").
2. Increment the top pointer: \( top = top + 1 \).
3. Insert the new item into the array at the new \( top \) position.

Step-by-Step: Removing an Item (Popping)

1. Check if the stack is empty (to avoid "Stack Underflow").
2. Access/return the item at the current \( top \) position.
3. Decrement the top pointer: \( top = top - 1 \).

Checking for "Full" or "Empty"

• Empty Stack: Usually, the top pointer is set to \( -1 \) (or \( 0 \), depending on the starting index) to show there are no items yet.
• Full Stack: If the top pointer is equal to the maximum size of the array, the stack is full. Trying to push more data now causes a Stack Overflow error!

Key Takeaway: An array-based stack uses a Top Pointer to navigate. Always check if the stack is full before pushing or empty before popping!

Where Do We Use Stacks?

Computers love stacks! Here are a few real-world situations where a stack is the perfect tool:

• The "Undo" Button: Your word processor keeps a stack of every change you make. When you click undo, it "pops" the last change off the top to go back in time.
• Web Browser History: When you click the "Back" button, the browser pops the last URL you visited off a stack.
• Subroutine Calls (Stack Frames): This is a very important concept for your syllabus! When a program calls a subroutine (a function), it uses a stack frame to store:
    1. The return address (where to go back to when the function ends).
    2. Parameters (data passed into the function).
    3. Local variables (data used only inside that function).

Did you know? The reason your computer "crashes" if a recursive function goes on forever is often because it runs out of memory for these stack frames—this is literally where the website name "Stack Overflow" comes from!

Summary Checklist

Before you finish, make sure you can answer these questions:
• Can I explain what LIFO means? (Last-In, First-Out)
• Do I know the difference between push, pop, and peek?
• Can I describe how a top pointer changes during a push or pop?
• Do I understand what a Stack Overflow and Stack Underflow are?
• Can I list two or three real-world uses for a stack?

Don't worry if this feels like a lot to take in! Just remember the "pile of plates" analogy and the rest will start to click into place. You've got this!