Use a stack, queue and linked list to store data

10.4 Introduction to Abstract Data Types (ADT)

An Abstract Data Type (ADT) is a mathematical model for data that defines a set of operations without specifying how those operations are implemented. Think of it as a contract: it tells you what you can do with the data, not how the data is stored. In this lesson we’ll explore three classic ADTs – Stack, Queue, and Linked List – and see how they help us store and manipulate data efficiently.

What is an ADT?

An ADT specifies:

• the data it holds
• the operations that can be performed on that data
• the behaviour of those operations (what they return, how they change the data)

The implementation – how we actually store the data in memory – is hidden from the user. This separation lets us change the underlying code without affecting the rest of the program.

Stack – LIFO (Last In, First Out)

Imagine a stack of plates 🍽️. The last plate you put on the stack is the first one you take off. A stack ADT has the following operations:

Operation	Description
$push(x)$	Add element $x$ to the top of the stack.
$pop()$	Remove and return the top element. If the stack is empty, return an error.
$peek()$	Return the top element without removing it.
$isEmpty()$	Check whether the stack has no elements.

Pseudocode example:

stack = []
push(stack, 5)   // stack: [5]
push(stack, 10)  // stack: [5, 10]
top = peek(stack) // top = 10
value = pop(stack) // value = 10, stack: [5]
  

Queue – FIFO (First In, First Out)

Picture a line at a movie ticket booth 🎟️. The first person in line is the first to get a ticket. A queue ADT offers:

Operation	Description
$enqueue(x)$	Add element $x$ to the rear of the queue.
$dequeue()$	Remove and return the front element. If the queue is empty, return an error.
$peek()$	Return the front element without removing it.
$isEmpty()$	Check whether the queue has no elements.

Pseudocode example:

queue = []
enqueue(queue, 'Alice')   // queue: ['Alice']
enqueue(queue, 'Bob')     // queue: ['Alice', 'Bob']
front = peek(queue)       // front = 'Alice'
name = dequeue(queue)     // name = 'Alice', queue: ['Bob']
  

Linked List – Nodes connected by pointers

Think of a chain of beads 🌈. Each bead (node) knows the next bead in the chain. A singly linked list ADT supports:

Operation	Description
$insert(pos, x)$	Insert element $x$ at position $pos$ (0 = head).
$delete(pos)$	Remove element at position $pos$.
$search(x)$	Return the position of element $x$ (or -1 if not found).
$traverse()$	Visit every node in order.

Pseudocode example:

head = null
insert(head, 0, 10)   // list: 10
insert(head, 1, 20)   // list: 10 -> 20
insert(head, 1, 15)   // list: 10 -> 15 -> 20
delete(head, 0)       // list: 15 -> 20
  

Implementing ADTs in Python – Quick Demo

1. Define a class for each ADT (e.g., class Stack:).
2. Use a Python list for the underlying storage of Stack and Queue.
3. For Linked List, create a Node class with data and next attributes.
4. Implement the operations as methods.
5. Test each ADT with simple unit tests or print statements.

Why use ADTs? They let you think about what you need to do (e.g., “add to the end” or “remove from the front”) without worrying about the how (array, linked nodes, etc.). This makes your code cleaner, easier to change, and often more efficient.