Stacks

Welcome, students! In this lesson, you will learn about stacks, one of the most important abstract data structures in computer science. Stacks are used in real software, from undo buttons in text editors to function calls in programming languages. By the end of this lesson, you should be able to explain what a stack is, describe its terminology, show how it works step by step, and connect it to the bigger idea of abstraction in computer science. 🎯

Introduction: Why Stacks Matter

A stack is a data structure that follows the rule last in, first out or LIFO. This means the most recent item added is the first item removed. A helpful real-world example is a stack of plates in a cafeteria 🍽️. If you place plates on top of one another, you usually take the top plate first. You do not remove one from the bottom unless you take the whole stack apart.

Stacks are important in IB Computer Science HL because they show how data can be organized in a controlled and efficient way. They also help explain abstraction: a programmer uses the stack through operations like pushing and popping, without needing to worry about every low-level detail of how memory is managed.

Learning goals for students

Explain the main ideas and terms related to stacks
Apply stack operations to problem-solving situations
Connect stacks to HL Extension — Abstract Data Structures
Describe how stacks support computation in real systems
Use examples to show why stacks are useful and efficient

What Is a Stack?

A stack is an abstract data structure that stores items in a linear order, but with restricted access. Items can only be added or removed from one end, called the top. The opposite end is the bottom.

The key operations are:

Push: add an item to the top of the stack
Pop: remove the item from the top of the stack
Peek or top: look at the top item without removing it
Is empty: check whether the stack has no items
Is full: check whether the stack is at maximum capacity, if implemented with a fixed-size array

These operations are simple, but they are powerful. A stack does not let you remove random items from the middle. This restriction is what makes it different from structures like arrays or lists.

For example, imagine students is editing a document. Each action, like typing a word or deleting a sentence, can be stored on a stack. If students presses Undo, the most recent action is reversed first. That is a perfect example of LIFO in action.

Core Terminology and How Stacks Work

In IB Computer Science, terminology matters because it helps you describe the structure accurately.

Abstract data structure: a model for organizing data by describing what operations are available, not necessarily how they are implemented
LIFO: last in, first out
Top: the end where items are added and removed
Overflow: trying to push onto a full stack
Underflow: trying to pop from an empty stack

Suppose a stack contains the values $A$, $B$, and $C$, where $C$ is at the top. If you perform pop, $C$ is removed first. If you then perform push with $D$, the stack becomes $A$, $B$, $D$ with $D$ on top.

A common way to show a stack is vertically:

$\text{Top} \\$

D \\

B \\

A \\

$\text{Bottom}$

This visual layout helps emphasize that only the top is directly accessible.

Stacks in Action: Step-by-Step Example

Let’s trace a simple sequence of operations. Start with an empty stack.

push $5$
push $9$
push $2$
pop
peek

After step 1, the stack is $[5]$.

After step 2, the stack is $[5, 9]$.

After step 3, the stack is $[5, 9, 2]$.

After step 4, $2$ is removed, so the stack becomes $[5, 9]$.

After step 5, peek returns $9$ because it is now the top item.

This example shows the defining behavior of a stack. The newest item is always the first one removed.

Stacks can store many types of data, such as numbers, characters, or even more complex objects. For example, a browser may store pages in a stack-like history. When students clicks Back, the most recently visited page is opened first.

How Stacks Are Implemented

A stack can be implemented in more than one way. Two common methods are using an array or a linked list.

Array-based stack

An array-based stack uses a fixed block of memory. One variable keeps track of the index of the top element. If the stack is empty, the top index may be set to $-1$. When an item is pushed, the top index increases by $1$. When an item is popped, the top index decreases by $1$.

This implementation is easy to understand and can be very efficient. However, if the array reaches its capacity, an overflow condition occurs. That is why fixed-size stacks are limited.

Linked-list-based stack

A linked list stack uses nodes connected by pointers. Each node stores data and a reference to the next node. The top of the stack points to the first node. Pushing creates a new node at the front, and popping removes the first node.

This version does not need a fixed maximum size in the same way an array does, although it is still limited by available memory. It is flexible and matches the idea of a dynamic collection.

Both implementations support the same stack behavior. This is an important example of abstraction: the user sees the same operations, even though the internal structure is different.

Why Stacks Are Efficient

Stacks are efficient because the main operations usually take constant time, written as $O(1)$, when the implementation is done well. That means push and pop do not depend on the number of items already in the stack.

This efficiency matters in real systems. For example:

A compiler may use a stack to manage function calls
A program may use a stack to evaluate expressions
An application may use a stack for undo and redo features

When a function is called, details like local variables and the return address are stored on the call stack. When the function ends, those details are removed in the reverse order. This is another powerful LIFO example.

Real-World Uses of Stacks

Stacks appear in many computing tasks.

1. Undo and redo systems

Each action is stored so that the most recent action can be reversed first. If students types three words, then deletes the last one, Undo should restore that last deletion before changing earlier actions.

2. Function calls and recursion

The call stack keeps track of which function is currently active. If one function calls another, the system remembers where to return after the second function finishes.

3. Expression evaluation

Stacks can help convert or evaluate mathematical expressions. For example, computers often use stacks when working with brackets or order of operations.

4. Browser history

Many browsers use stack-like behavior when going backward through pages.

5. Syntax checking

A stack can check whether brackets are balanced in code. For example, every opening bracket $($ should match a closing bracket $)$ in the correct order.

These examples show that stacks are not just theory. They are practical tools used in everyday software.

Stacks and Abstract Data Structures

Stacks belong to the larger topic of HL Extension — Abstract Data Structures because they show the difference between what data does and how it is stored.

The abstract idea of a stack is simple:

add to the top
remove from the top
access only the top

The implementation can vary:

array-based
linked-list-based

This separation is central to computer science. It allows programmers to choose the best implementation for a situation while still using the same stack concept. In IB Computer Science HL, understanding this connection helps you explain both the behavior and the efficiency of the structure.

Conclusion

Stacks are a simple but powerful abstract data structure built on the principle of last in, first out. students should remember the main operations: push, pop, and peek. Stacks are used in many important computing processes, including function calls, undo systems, browser history, and bracket checking. They connect directly to abstraction because the same stack behavior can be implemented in different ways, such as with arrays or linked lists. Understanding stacks helps you understand how computer systems organize work efficiently and logically. ✅

Study Notes

A stack is an abstract data structure that follows LIFO.
The top of the stack is the only end where items are added and removed.
Main operations: push, pop, peek, is empty, and is full.
Overflow happens when pushing to a full fixed-size stack.
Underflow happens when popping from an empty stack.
Array-based stacks use an index to track the top.
Linked-list-based stacks use nodes and pointers.
Stack operations are usually $O(1)$.
Real-world uses include undo/redo, function calls, browser history, syntax checking, and expression evaluation.
Stacks are part of HL Extension — Abstract Data Structures because they show abstraction and efficient data organization.