Algorithms in PHP: Deques (and circular buffers + linked lists)

If you’ve ever tried to use an array as a queue or stack (via array_pop, array_push, array_unshift and array_shift), you may have discovered they are slow, particularly array_unshift which requires shifting the entire array. Here are the limits of the awesome PHP array: prepending. Prepending to an array is a very costly operation in PHP, and there isn’t really any way to get around it, or is there?

Queues and Stacks

In computer science, there are two fundamental things for batch processing: queues and stacks. A queue is a first-in-first-out (FIFO) construct, and it works just like a queue at a grocery store. The first person in the line is the first person who gets checked out.

A stack, on the other hand, is a first-in-last-out (FILO) construct. You can imagine this just like a stack of plates. As you “push” plates onto the stack, the first plate you place is the last plate you’ll “pop” off the stack.

Both of these structures are amazing for being able to do any kind of bulk work. However, sometimes you must utilize a sequence as a stack and a queue. For example, if you require storing the last 500 items of something, but want to iterate it in reverse (undo features come to mind here).

The Deque

Enter the deque (pronounced “deck”). Deques are slightly magical in being able to use them like a queue and a stack. Taking items off and on from either end is O(1) while accessing the middle is still O(n). They are usually implemented on top of linked lists or a circular buffer.

A deque is incredibly powerful for “undo” features. You push operations onto the deque and shift items at the bottom once it gets above a specific size, allowing you to easily “undo the last X actions.” So, if you ever see some requirements for a “limited size stack” or “limited size queue,” you’re probably looking to use a deque.

A short disclaimer

Before we get into implementation of a Deque, I feel like a disclaimer is needed. The code shown on these posts shouldn’t be used in production. I’m not doing a lot of error handling, and in some cases, ignoring edge cases altogether. I’m merely trying to illustrate the principles for those cases where you need to implement it yourself. For example, WordPress implements a priority queue similar to the last post to support filters/actions in order to support insertion/deletion while iterating the queue. Beanstalkd uses a custom heap sort to support

Nieve implementation

First, let us look at a very nieve implementation:

<?php

namespace Withinboredom\Deque;

class Nieve {
	private array $buffer = [];

	/**
	 * Append to the end of the array
	 *
	 * @param mixed $value
	 *
	 * @return void
	 */
	public function push( mixed $value ): void {
		array_push($this->buffer, $value);
	}

	/**
	 * Get from the end of the array
	 * @return mixed
	 */
	public function pop(): mixed {
		return array_pop($this->buffer);
	}

	/**
	 * Get from the beginning of the array
	 * @return mixed
	 */
	public function shift(): mixed {
		return array_shift($this->buffer);
	}

	/**
	 * Append to the beginning of the array
	 *
	 * @param mixed $value
	 *
	 * @return void
	 */
	public function unshift( mixed $value ): void {
		array_unshift($this->buffer, $value);
	}
}

As you can see, it is pretty simple. You should note that it is also very slow and gets slower as the array gets bigger.

Don’t do this unless you only have a very small list (~100-200 items).

Implementing a circular buffer

We can use a regular array, just like our nieve implementation, but implement a circular buffer. This would make the major cost of our implementation be the overhead of array accesses. To implement a circular buffer, we must understand what a circular buffer is and its requirements.

I’m not going to go into depth on how a regular one works, so I highly recommend pausing here and learning about regular circular buffers. We need a special circular buffer: a double-ended circular buffer.

This works similarly to a regular circular buffer, except we have two cursors: the “head” and the “tail.” These allow us to insert items at “the front” and “the back” while also allowing us to read those items.

To add an item to the head of the buffer:

1. Check if the deque is full.
2. If we are already at our initial position, move to the end of the array.
3. Else decrement the pointer.
4. Add the item to the array.

To add an item at the tail of the buffer:

1. Check if the deque is full.
2. If we are already at the end of the array, move to the beginning of the array.
3. Else increment the pointer.
4. Add the item to the array.