This post is a translation and is intended for beginners—or for those who have forgotten their introductory university lectures. Most likely, this material has already appeared on Habr in one form or another, but here the focus is on PHP and its specifics.
Data Structures, or Abstract Data Types (ADT), are models defined as a set of operations that can be applied to themselves, along with constraints on the results of those operations.
Most of us encounter stacks and queues in everyday life, but what do a supermarket queue and a data structure have in common? That’s what we’ll try to understand in this article, which will also cover trees.
---
Stack
Queue
Tree
---
Stack
A stack is usually described as a collection of objects grouped together, where each element follows the previous one—like a stack of books or trays. In computer science, a stack is a collection of objects with a specific rule: the last object added to the stack is the first one to be removed. This rule is called Last In, First Out (LIFO). The opposite rule is First In, First Out (FIFO), which we will discuss later.
The LIFO rule is used, for example, in vending machines—where the last item loaded is the first one dispensed.
Abstractly, a stack is a list where all operations are defined relative to one end—the top of the stack.
Basic stack operations:
init – create a stack
push – add an element to the top of the stack
pop – remove and return the top element
top – view the top element without removing it
isEmpty – check if the stack is empty
A stack can also have a maximum size. If it cannot accept more elements, it results in a stack overflow. Conversely, attempting to remove an element from an empty stack results in a stack underflow.
Knowing that a stack follows LIFO and has these basic operations, we can implement it using an array in PHP:
(code remains unchanged)
In this example, we used array_unshift() and array_shift() instead of array_push() and array_pop(), so the first element of the array is always the top of the stack. Otherwise, the top would be the last element. There’s no major difference.
Now let’s add some elements:
(code remains unchanged)
And remove a few:
(code remains unchanged)
What is now the top of the stack?
(code remains unchanged)
If we call pop() again, "A Feast for Crows" will be removed. If we push and then immediately pop, the stack remains unchanged due to the LIFO principle. Eventually, removing elements from an empty stack will throw an exception.
---
SplStack
PHP (via the SPL extension) provides built-in implementations of various data structures, including SplStack (since PHP 5.3). We can simplify our class:
(code remains unchanged)
SplStack provides more methods because it is implemented as a doubly linked list, which allows iteration and maintains capacity.
A linked list is another abstract structure consisting of nodes, each pointing to the next node.
A doubly linked list has two pointers per node—one to the previous node and one to the next—allowing traversal in both directions.
---
Queue
Now we move to First In, First Out (FIFO). Anyone who has stood in a real queue knows that the first person in line is the first to leave.
Basic queue operations:
init – create a queue
enqueue – add an element to the end (tail)
dequeue – remove an element from the front (head)
isEmpty – check if the queue is empty
PHP provides SplQueue, also based on a doubly linked list. Here, the head is the first element.
(code remains unchanged)
SplQueue extends SplDoublyLinkedList and allows array-like access:
(code remains unchanged)
Removing elements:
(code remains unchanged)
enqueue() is an alias of push(), but dequeue() is not the same as pop(). Using pop() would remove an element from the tail, which violates FIFO.
To inspect the front element without removing it, use bottom():
(code remains unchanged)
---
Trees
Working with ADTs usually involves three operations: insert, delete, and retrieve. For stacks and queues, these depend on position (xIFO). But what if we need to retrieve data by value?
In a simple list, searching may require scanning up to n/2 elements on average. The larger the list, the slower the search.
To improve search efficiency, data must be structured differently—this is where trees come in.
Basic tree operations:
create – create an empty structure
insert – add an element
delete – remove an element
retrieve – find an element
This resembles CRUD operations in databases, which is no coincidence—trees are widely used in database indexing.
Trees are hierarchical structures with parent-child relationships:
Root – top node
Leaf – node without children
Edge – connection between nodes
A binary tree node has at most two children.
Example implementation:
(code remains unchanged)
---
Inserting Values
Insertion rules for a simple binary search tree:
If the tree is empty → new node becomes root
If value is less → go left
If greater → go right
Ignore duplicates
(code remains unchanged)
---
Tree Traversal
There are four main traversal strategies:
Pre-order – process node, then left and right
In-order – left, node, right
Post-order – left, right, node
Level-order – breadth-first traversal
The first three are depth-first traversal methods.
Example of in-order traversal:
(code remains unchanged)
---
Conclusion
Thank you for reading!
Note that SplStack, SplQueue, and linked lists include many additional methods in the PHP documentation, such as counting elements and iteration.
In terms of performance, SplQueue is generally preferable. Stack implementations don’t offer much advantage over arrays, and doubly linked lists can even be slower due to overhead.
Data Structures, or Abstract Data Types (ADT), are models defined as a set of operations that can be applied to themselves, along with constraints on the results of those operations.
Most of us encounter stacks and queues in everyday life, but what do a supermarket queue and a data structure have in common? That’s what we’ll try to understand in this article, which will also cover trees.
---
Stack
Queue
Tree
---
Stack
A stack is usually described as a collection of objects grouped together, where each element follows the previous one—like a stack of books or trays. In computer science, a stack is a collection of objects with a specific rule: the last object added to the stack is the first one to be removed. This rule is called Last In, First Out (LIFO). The opposite rule is First In, First Out (FIFO), which we will discuss later.
The LIFO rule is used, for example, in vending machines—where the last item loaded is the first one dispensed.
Abstractly, a stack is a list where all operations are defined relative to one end—the top of the stack.
Basic stack operations:
init – create a stack
push – add an element to the top of the stack
pop – remove and return the top element
top – view the top element without removing it
isEmpty – check if the stack is empty
A stack can also have a maximum size. If it cannot accept more elements, it results in a stack overflow. Conversely, attempting to remove an element from an empty stack results in a stack underflow.
Knowing that a stack follows LIFO and has these basic operations, we can implement it using an array in PHP:
(code remains unchanged)
In this example, we used array_unshift() and array_shift() instead of array_push() and array_pop(), so the first element of the array is always the top of the stack. Otherwise, the top would be the last element. There’s no major difference.
Now let’s add some elements:
(code remains unchanged)
And remove a few:
(code remains unchanged)
What is now the top of the stack?
(code remains unchanged)
If we call pop() again, "A Feast for Crows" will be removed. If we push and then immediately pop, the stack remains unchanged due to the LIFO principle. Eventually, removing elements from an empty stack will throw an exception.
---
SplStack
PHP (via the SPL extension) provides built-in implementations of various data structures, including SplStack (since PHP 5.3). We can simplify our class:
(code remains unchanged)
SplStack provides more methods because it is implemented as a doubly linked list, which allows iteration and maintains capacity.
A linked list is another abstract structure consisting of nodes, each pointing to the next node.
A doubly linked list has two pointers per node—one to the previous node and one to the next—allowing traversal in both directions.
---
Queue
Now we move to First In, First Out (FIFO). Anyone who has stood in a real queue knows that the first person in line is the first to leave.
Basic queue operations:
init – create a queue
enqueue – add an element to the end (tail)
dequeue – remove an element from the front (head)
isEmpty – check if the queue is empty
PHP provides SplQueue, also based on a doubly linked list. Here, the head is the first element.
(code remains unchanged)
SplQueue extends SplDoublyLinkedList and allows array-like access:
(code remains unchanged)
Removing elements:
(code remains unchanged)
enqueue() is an alias of push(), but dequeue() is not the same as pop(). Using pop() would remove an element from the tail, which violates FIFO.
To inspect the front element without removing it, use bottom():
(code remains unchanged)
---
Trees
Working with ADTs usually involves three operations: insert, delete, and retrieve. For stacks and queues, these depend on position (xIFO). But what if we need to retrieve data by value?
In a simple list, searching may require scanning up to n/2 elements on average. The larger the list, the slower the search.
To improve search efficiency, data must be structured differently—this is where trees come in.
Basic tree operations:
create – create an empty structure
insert – add an element
delete – remove an element
retrieve – find an element
This resembles CRUD operations in databases, which is no coincidence—trees are widely used in database indexing.
Trees are hierarchical structures with parent-child relationships:
Root – top node
Leaf – node without children
Edge – connection between nodes
A binary tree node has at most two children.
Example implementation:
(code remains unchanged)
---
Inserting Values
Insertion rules for a simple binary search tree:
If the tree is empty → new node becomes root
If value is less → go left
If greater → go right
Ignore duplicates
(code remains unchanged)
---
Tree Traversal
There are four main traversal strategies:
Pre-order – process node, then left and right
In-order – left, node, right
Post-order – left, right, node
Level-order – breadth-first traversal
The first three are depth-first traversal methods.
Example of in-order traversal:
(code remains unchanged)
---
Conclusion
Thank you for reading!
Note that SplStack, SplQueue, and linked lists include many additional methods in the PHP documentation, such as counting elements and iteration.
In terms of performance, SplQueue is generally preferable. Stack implementations don’t offer much advantage over arrays, and doubly linked lists can even be slower due to overhead.
