Stacks, Queues, and Deques — Data Structures in PHP
This article was originally published on garrettmassey.net on October 27, 2022.
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.
<?phpnamespace 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 stackpop()– removes the top node from the stack, returns the datapeek()– returns the data in the top node of the stack without removing the nodepeekNext()– returns the data of the second node in the stack without removing the data
<?phpnamespace 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 queuedequeue()– removes the first node in the queuepeek()– returns the data of the first node in the queue, without removing itpeekNext()– returns the data of the next node in the queue, without removing it.
<?phpnamespace 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 listaddLast()– 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 dataremoveLast()– removes the last node of the list and returns that node’s datapeekFirst()– returns the data of the first node in the list without removing the nodepeekLast()– returns the data of the last node of the list without removing the nodepeekNext()– returns the data of the second node in the list ($head->next), without altering the listpeekPrev()– returns the data of the second to last node in the list ($tail->prev), without altering the list.
<?phpnamespace 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.
