Data Structures in PHP: Implementing Stacks, Queues, Linked Lists, and SPL Classes

Data structures are an integral part of programming, offering efficient ways to store and organize data. As PHP evolves, understanding how to implement and utilize common data structures like Stacks, Queues, and Linked Lists will make you a more proficient PHP developer. PHP 8 provides a range of options, from manual implementations to built-in SPL (Standard PHP Library) classes that offer high performance and easy integration into your projects.

In this article, we'll explore how to implement basic data structures in PHP 8 and how to leverage PHP’s SPL classes for enhanced functionality.

1. Introduction to Data Structures in PHP

• Data structures are ways of organizing and storing data so that they can be accessed and modified efficiently.
• By understanding the strengths and weaknesses of various data structures, developers can optimize their code for performance and readability.

In PHP 8, developers can choose between building their own data structures or using the built-in SPL classes.

Let's start with manual implementations for three common data structures: Stacks, Queues, and Linked Lists.

2. Implementing Stacks in PHP

A stack is a simple data structure that follows the Last In, First Out (LIFO) principle. The last element pushed onto the stack is the first to be popped out.

Stack Operations:

• push(): Add an element to the top of the stack.
• pop(): Remove and return the top element.
• peek(): View the top element without removing it.
• isEmpty(): Check if the stack is empty.

Manual Implementation:

class Stack {

    private $stack = [];

    public function push($item) {

        array_push($this->stack, $item);

    }

    public function pop() {

        if (!$this->isEmpty()) {

            return array_pop($this->stack);

        }

        return null; // Stack is empty

    }

    public function peek() {

        return end($this->stack);

    }

    public function isEmpty() {

        return empty($this->stack);

    }

}

$stack = new Stack();

$stack->push(1);

$stack->push(2);

echo $stack->pop(); // 2

echo $stack->peek(); // 1

SPL Stack Implementation:

PHP offers a built-in stack class SplStack in the SPL library:

$stack = new SplStack();

$stack->push(1);

$stack->push(2);

echo $stack->pop(); // 2

echo $stack->top(); // 1

3. Implementing Queues in PHP

A queue is a data structure that follows the First In, First Out (FIFO) principle. The first element added to the queue will be the first to be removed.

Queue Operations:

• enqueue(): Add an element to the back of the queue.
• dequeue(): Remove and return the front element.
• peek(): View the front element without removing it.
• isEmpty(): Check if the queue is empty.

Manual Implementation:

class Queue {

    private $queue = [];

    public function enqueue($item) {

        array_push($this->queue, $item);

    }

    public function dequeue() {

        if (!$this->isEmpty()) {

            return array_shift($this->queue);

        }

        return null; // Queue is empty

    }

    public function peek() {

        return reset($this->queue);

    }

    public function isEmpty() {

        return empty($this->queue);

    }

}

$queue = new Queue();

$queue->enqueue(1);

$queue->enqueue(2);

echo $queue->dequeue(); // 1

echo $queue->peek(); // 2

SPL Queue Implementation:

PHP’s SplQueue class implements a queue with optimized methods:

$queue = new SplQueue();

$queue->enqueue(1);

$queue->enqueue(2);

echo $queue->dequeue(); // 1

echo $queue->bottom(); // 2

4. Implementing Linked Lists in PHP

A linked list is a collection of nodes, where each node contains data and a reference to the next node. Linked lists can be singly or doubly linked, depending on whether nodes have a reference to the next node only or both the next and previous nodes.

Linked List Operations:

• insert(): Add a new node.
• delete(): Remove a node.
• traverse(): Iterate over the nodes.

Manual Implementation (Singly Linked List):

class Node {

    public $data;

    public $next;

    public function __construct($data) {

        $this->data = $data;

        $this->next = null;

    }

}

class LinkedList {

    private $head;

    public function __construct() {

        $this->head = null;

    }

    public function insert($data) {

        $newNode = new Node($data);

        $newNode->next = $this->head;

        $this->head = $newNode;

    }

    public function delete($data) {

        $current = $this->head;

        $previous = null;

        while ($current !== null && $current->data !== $data) {

            $previous = $current;

            $current = $current->next;

        }

        if ($current !== null) {

            if ($previous === null) {

                $this->head = $current->next;

            } else {

                $previous->next = $current->next;

            }

        }

    }

    public function traverse() {

        $current = $this->head;

        while ($current !== null) {

            echo $current->data . ' ';

            $current = $current->next;

        }

    }

}

$list = new LinkedList();

$list->insert(1);

$list->insert(2);

$list->insert(3);

$list->traverse(); // 3 2 1

$list->delete(2);

$list->traverse(); // 3 1

SPL Doubly Linked List Implementation:

The SplDoublyLinkedList class in PHP provides an easy way to manage linked lists with both forward and backward traversal:

$list = new SplDoublyLinkedList();

$list->push(1);

$list->push(2);

$list->push(3);

$list->rewind(); // Reset pointer to the first element

echo $list->current(); // 1

5. Using PHP's SPL Data Structures

PHP’s SPL extension provides several useful built-in data structures that are highly optimized for performance. Let’s take a quick look at the most popular SPL classes for handling data structures.

• SplStack: PHP’s built-in stack class that provides methods like push(), pop(), and top().
• SplQueue: An optimized queue implementation with methods such as enqueue(), dequeue(), and bottom().
• SplDoublyLinkedList: A doubly linked list class that supports both forward and backward traversal using methods like push(), pop(), rewind(), and current().
• SplHeap: A heap class useful for creating priority queues.
• SplFixedArray: A fixed-size array class that can be used for efficient memory management when the size of the array is known in advance.

6. Conclusion

In PHP 8, understanding and utilizing common data structures like Stacks, Queues, and Linked Lists is vital for writing efficient and scalable code. While you can implement these structures manually for more flexibility, PHP’s SPL classes provide highly optimized and easy-to-use alternatives that save time and effort.

By mastering these data structures and knowing when to use each one, you can significantly improve the performance and maintainability of your PHP applications. Whether you build your own or leverage SPL, the right data structure can make all the difference in solving problems efficiently.

By implementing these data structures and understanding their use cases, you’ll become more adept at solving complex problems with PHP. Whether you're building a small application or a large-scale system, these foundational concepts will serve you well in your development journey.

Thanks for reading the article, for more Science & Technology related articles read and subscribe to peoples blog articles.