Review

Stacks

Queues

Deques (aka Double Ended Queues)

Implementation

GenericList Class

<?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

  • 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
<?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

  • 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.
<?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

  • 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.
<?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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Garrett Massey

I am a web designer and developer. I like to play the piano, write, and pet dogs. Coffee lover, gaybro, nerd. In no particular order. (garrettmassey.net)