Introduction to Stacks
Welcome! In this chapter, we are going to explore one of the most fundamental and frequently used data structures in Computer Science: the Stack. Stacks are incredibly useful for keeping track of tasks, reversing data, and even helping your computer run subroutines. By the end of these notes, you’ll understand how they work, how to use them, and why they are essential for your AQA A Level exams.
Don’t worry if data structures seem a bit abstract at first—we’ll use plenty of everyday examples to make it clear!
What is a Stack?
A stack is an Abstract Data Type (ADT). This means it is a conceptual model of how data should be organized and accessed. It follows a very specific rule called LIFO, which stands for Last-In, First-Out.
The Analogy: Imagine a stack of cafeteria trays.
1. You put a new tray on the top of the pile.
2. If you want to take a tray, you take the one from the top.
3. The very first tray put down (the bottom one) stays there until every other tray above it has been removed.
Key Term: LIFO
In a stack, the last item you add is the first one you must remove. You can only ever interact with the "top" of the stack.
Quick Review: The LIFO Rule
• Last In
• First Out
• Think of it like a Pringles can—the last crisp put in the factory is the first one you eat!
Essential Stack Operations
According to your syllabus, you need to know exactly how to describe and apply these five operations:
1. Push
The push operation adds a new item to the top of the stack.
Step-by-step:
1. Check if the stack is already full (to avoid Stack Overflow).
2. Increment the top pointer (move it up one space).
3. Insert the new data at that position.
2. Pop
The pop operation removes the item from the top of the stack and usually returns its value.
Step-by-step:
1. Check if the stack is empty (to avoid Stack Underflow).
2. Access the data at the current top pointer.
3. Decrement the top pointer (move it down one space).
3. Peek (or Top)
The peek operation returns the value of the top element without removing it. It’s like glancing at the top tray to see what color it is without picking it up.
4. Test for Empty Stack (isEmpty)
This checks if there are any items in the stack. If the top pointer is at its starting position (often -1 or 0 depending on implementation), the stack is empty.
5. Test for Stack Full (isFull)
If a stack is implemented using an array with a fixed size (a static data structure), it can run out of space. This operation checks if the top pointer has reached the maximum capacity.
Key Takeaway
Push to add, Pop to remove, Peek to look. Always check if the stack is Full before pushing or Empty before popping!
Implementation: How it works in Memory
In your exam, you might be asked how a stack is actually built. Most commonly, a stack is implemented using an array and a top pointer.
• The Array: A sequence of memory locations that store the data.
• The Top Pointer: A variable that stores the index (the position) of the current top element.
Did you know?
When we "remove" an item during a pop operation, the data isn't actually deleted from memory immediately. We simply move the top pointer down. The computer then treats that "popped" space as empty, even though the old bits are still there until they get overwritten by a new push!
Common Mistakes to Avoid
• The Pointer Position: Some programmers start the top pointer at \( -1 \) (meaning the stack is empty), while others start it at \( 0 \). Make sure you read the exam question carefully to see how they define "Empty."
• The Order of Operations: When pushing, you must increment the pointer before adding the data. When popping, you usually capture the data before decrementing the pointer.
Real-World Applications of Stacks
Stacks aren't just for textbooks; they are used in almost every piece of software you use!
1. Undo Buttons
Every time you type a letter in a word processor, it is pushed onto a stack. When you hit "Undo," the computer pops the last action off the stack to reverse it.
2. The Back Button in Browsers
As you navigate websites, each URL is pushed onto a stack. When you click "Back," the current page is popped off, revealing the previous one.
3. Subroutine Calls (Stack Frames)
This is a specific part of the AQA syllabus (Section 4.1.1.15). When a program calls a function (subroutine), it uses a stack frame to store:
• Return addresses: Where to go back to when the function finishes.
• Parameters: The data being passed into the function.
• Local variables: Variables that only exist inside that function.
4. Reverse Polish Notation (RPN)
Stacks are used to evaluate mathematical expressions in RPN (Section 4.3.3.1). For example, \( 3 + 4 \) is written as \( 3 \ 4 \ + \). The computer pushes 3 and 4 onto the stack, then when it sees the \( + \), it pops them both, adds them, and pushes the result back on.
Quick Review: Stack Uses
• Backtracking (Undo/Back button)
• Function calls (Recursion and Stack Frames)
• Reversing data
• Expression evaluation (RPN)
Summary Table
Operation | Description
Push | Adds an item to the top. Increases pointer.
Pop | Removes and returns the top item. Decreases pointer.
Peek | Returns the top item without removing it.
isEmpty | Returns True if the stack has no items.
isFull | Returns True if a static stack is at max capacity.
Key Takeaway for Exams
If you see a question about Stacks, remember LIFO. Always check for Overflow (pushing to a full stack) and Underflow (popping from an empty stack). If you can describe these and draw a simple array with a moving pointer, you are well on your way to top marks!