Reading Time: 7 minutes

Read the previous article on Doubly Linked Lists in PHP here!

All code in the series is available on Github

In my first post of this series on Singly Linked Lists, I mentioned that a list with the ability to add, get, or remove data from more than just the end of the list starts to behave more like a Deque. Then, I said I would cover those details in a later post. Well, later is now, and it’s time to talk about specific types of lists as Stacks, Queues, and Deques. Let’s get started.

Review

Stacks

Stacks are a fundamental data structure in computer science, used in recursive processing, functional logic, and more. A stack is a kind of list with a specific entry and exit point. Specifically, a stack implements a LIFO, or Last In, First Out system of data management. That means that the last thing you put in the list has to be the first thing you take out, and you can’t take out other data from the list until it is at the top of the stack.

Think of a stack of plates. It makes the most sense to take a plate for dinner off the top of the stack. You wouldn’t lift half of the plates to get to one in the middle, and you can’t just pull the bottom out without the plates falling over. So you take plates off the top until there are no plates left. That is the essence of a stack.

Queues

Queues are like stacks, but in reverse. They follow a FIFO system of data management. First In, First Out. This kind of management is exactly what we use in lines (for Americans, queues for Brits), and it’s exactly what is used for inventory management. The first items on the shelf (the oldest) are the first to be removed (purchased by customers). The first person in line is the first person to be helped. Queues and the FIFO system are useful for procedural systems where the order of addition is critical to the end result. A set of linear instructions is also a kind of Queue.

Deques (aka Double Ended Queues)

Deques are a special kind of list that can be added to on either end, and removed from either end. You can add to the beginning of the list, remove from the end of the list, add to the end of the list, and remove from the beginning. Deques behave like the first implementation of the Doubly Linked List, covered in the previous post in the series.

Because Deques can be altered from either end of the list, all Stacks are Deques and all Queues are Deques, as long as we don’t use the other methods available. Just like all squares are rectangles, but not all rectangles are squares, it depends on how we use the Deque that determines if it is uniquely different from or a different implementation of Stacks and Queues.

Deques allow more flexibility than standard Queues or Stacks, and can also serve as a basis for extending the class into your own data structure down the line.

Implementation

Now that we have some review out of the way, let’s take a look at the implementation. For this project, because Stacks, Deques, and Queues are all linear data structures, I created a GenericList class and extended that class with each implementation of the data type to reduce code duplication. There is still definitely duplicate code, but this is a start.

As a note, the Node class has not changed since the Doubly Linked List article, and the code can be found on both that post and on GitHub.

Also, to save on visual space in this article, I am not including the PHPDoc comments that I have included in previous posts. The full code with the PHPDoc comments can be found on GitHub.

GenericList Class

As mentioned, the GenericList class serves as the parent class for Stacks, Deques, and Queues. The GenericList class contains all methods necessary to implement a Doubly Linked List, and the subsequent child classes use these methods in specific ways to implement their unique list behavior.

In a later posting, I will add to this class some of the methods used for the Singly and Doubly Linked List classes, and implement some class abstraction.

Copy Code

<?php

namespace DataStructures;

class GenericList
{

    public Node|null $head;
    public Node|null $tail;
    public int $length;

    public function __construct()
    {
        $this->head = null;
        $this->tail = null;
        $this->length = 0;
    }

    public function getHead(): Node|null
    {
        return $this->head;
    }

    public function getTail(): Node|null
    {
        return $this->tail;
    }

    public function getLength(): int
    {
        return $this->length;
    }

    public function add($data): void
    {
        $node = new Node($data);
        if ($this->head === null) {
            $this->head = $node;
            $this->tail = $node;
        } else {
            $this->tail->next = $node;
            $node->prev = $this->tail;
            $this->tail = $node;
        }
        $this->length++;
    }

    public function addHead($data): void
    {
        $node = new Node($data);
        if ($this->head === null) {
            $this->head = $node;
            $this->tail = $node;
        } else {
            $node->next = $this->head;
            $this->head->prev = $node;
            $this->head = $node;
        }
        $this->length++;
    }

    public function remove(): mixed
    {
        if ($this->head === null) {
            return null;
        }
        $data = $this->tail->data;
        if ($this->head === $this->tail) {
            $this->head = null;
            $this->tail = null;
        } else {
            $this->tail = $this->tail->prev;
            $this->tail->next = null;
        }
        $this->length--;
        return $data;
    }

    public function removeHead(): mixed
    {
        if ($this->head === null) {
            return null;
        }
        $data = $this->head->data;
        if ($this->head === $this->tail) {
            $this->head = null;
            $this->tail = null;
        } else {
            $this->head = $this->head->next;
            $this->head->prev = null;
        }
        $this->length--;
        return $data;
    }

    public function removeAt($position)
    {
        if ($position < 0 || $position >= $this->length) {
            return null;
        }
        if ($position === 0) {
            return $this->removeHead();
        }
        if ($position === $this->length - 1) {
            return $this->remove();
        }
        $current = $this->head;
        $index = 0;
        while ($index !== $position) {
            $current = $current->next;
            $index++;
        }
        $current->prev->next = $current->next;
        $current->next->prev = $current->prev;
        $this->length--;
        return $current->data;
    }

    public function getAt($position): mixed
    {
        if ($position < 0 || $position >= $this->length) {
            return null;
        }
        $current = $this->head;
        $index = 0;
        while ($index !== $position) {
            $current = $current->next;
            $index++;
        }
        return $current->data;
    }

    public function indexOf($data): int
    {
        $current = $this->head;
        $index = 0;
        while ($current !== null) {
            if ($current->data === $data) {
                return $index;
            }
            $current = $current->next;
            $index++;
        }
        return -1;
    }

    public function lastIndexOf($data): int
    {
        $current = $this->tail;
        $index = $this->length - 1;
        while ($current !== null) {
            if ($current->data === $data) {
                return $index;
            }
            $current = $current->prev;
            $index--;
        }
        return -1;
    }

    public function contains($data): bool
    {
        return $this->indexOf($data) !== -1;
    }

    public function isEmpty(): bool
    {
        return $this->length === 0;
    }

    public function clear(): void
    {
        $this->head = null;
        $this->tail = null;
        $this->length = 0;
    }

    public function toArray(): array
    {
        $array = [];
        $current = $this->head;
        while ($current !== null) {
            $array[] = $current->data;
            $current = $current->next;
        }
        return $array;
    }

    public function toString(): string
    {
        $string = '';
        $current = $this->head;
        while ($current !== null) {
            $string .= $current->data . '|';
            $current = $current->next;
        }

        return $string;
    }
}

Stacks Implementation

The Stack class has the following methods:

push() – adds an element to the top of the stack
pop() – removes the top node from the stack, returns the data
peek() – returns the data in the top node of the stack without removing the node
peekNext() – returns the data of the second node in the stack without removing the data

Copy Code

<?php

namespace DataStructures;

class Stack extends GenericList
{

    public Node|null $top;
    public Node|null $bottom;

    public function __construct()
    {
        parent::__construct();
        $this->top = $this->tail;
        $this->bottom = $this->head;
    }

    public function push($data): void
    {
        $this->add($data);
        $this->top = $this->tail;
    }

    public function pop(): mixed
    {
        return $this->remove();
    }

    public function peek(): mixed
    {
        return $this->top->data;
    }

    public function peekNext(): mixed
    {
        return $this->top->prev->data;
    }
}

Queue Implementation

The Queue class has the following methods:

enqueue() – adds a node to the end of the queue
dequeue() – removes the first node in the queue
peek() – returns the data of the first node in the queue, without removing it
peekNext() – returns the data of the next node in the queue, without removing it.

Copy Code

<?php

namespace DataStructures;

class Queue extends GenericList
{

    public Node|null $front;
    public Node|null $back;

    public function __construct()
    {
        parent::__construct();
        $this->front = $this->head;
        $this->back = $this->tail;
    }

    public function enqueue($data): void
    {
        $this->add($data);
        $this->back = $this->tail;
    }

    public function dequeue(): mixed
    {
        return $this->removeHead();
    }

    public function peek(): mixed
    {
        return $this->front->data;
    }

    public function peekNext(): mixed
    {
        return $this->front->next->data;
    }
}

Deque Implementation

The Deque class has the following methods:

addFirst() – adds a new node to the head of the list
addLast() – adds a new node to the end of the list (the tail)
removeFirst() – removes the first node of the list and returns that node’s data
removeLast() – removes the last node of the list and returns that node’s data
peekFirst() – returns the data of the first node in the list without removing the node
peekLast() – returns the data of the last node of the list without removing the node
peekNext() – returns the data of the second node in the list ($head->next), without altering the list
peekPrev() – returns the data of the second to last node in the list ($tail->prev), without altering the list.

Copy Code

<?php

namespace DataStructures;

class Deque extends GenericList
{
    public function __construct()
    {
        parent::__construct();
    }

    public function addFirst($data): void
    {
        $this->addHead($data);
    }

    public function addLast($data): void
    {
        $this->add($data);
    }

    public function removeLast(): mixed
    {
        return $this->remove();
    }

    public function removeFirst(): mixed
    {
        return $this->removeHead();
    }

    public function peekFirst(): mixed
    {
        return $this->head->data;
    }

    public function peekLast(): mixed
    {
        return $this->tail->data;
    }

    public function peekNext(): mixed
    {
        return $this->head->next->data;
    }

    public function peekPrev(): mixed
    {
        return $this->tail->prev->data;
    }

}

Conclusion

In addition to implementing three different types of Linked Lists, I have started the process of abstracting the code and using class inheritance to simplify the development process. This is still only the beginning stages of the exploration of these data structures, and in the next post, I will be using more abstraction to create a class structure that is capable of implementing all of the previous Linked List types covered in this series.

The next post in the series will dive into the concepts of abstraction for these data structures, and the subsequent post will cover usage, testing, and various implementations of these structures with practical examples.

If you have been following along, thank you! I hope you continue to find this series interesting and useful. It has been a surprisingly fun project to work on in my free time, and I hope to continue work on these kinds of explorations into the future.

Stacks, Queues, and Deques – Data Structures in PHP

Review

Stacks

Queues

Deques (aka Double Ended Queues)

Implementation

GenericList Class

Stacks Implementation

Queue Implementation

Deque Implementation

Conclusion