Datastructures: Queue

A queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. ^[1]

The operations of a queue make it a first-in-first-out (FIFO) data structure. ^[1]

Queue datastructures in SPHPlayground:

• The Queue is the base interface for all queues
  • The ArrayQueue is a simple implementation of the Queue interface. It uses PHP arrays as its inner data structure.
  • PriorityQueue interface
    • StablePriorityQueue implementation
    • IterablePriorityQueue implementation

Description of queue methods:

• Queue::enqueue(): Adds a new item to the end
• Queue::dequeue(): Removes and returns the first item
• Queue::peek(): Observes the first item without removing it
• Queue::isEmpty(): Determines if the queue is empty or not

Priority Queue data structures

In a priority queue, each element has an associated priority, which determines its order of service. Priority queue serves highest priority items first. ^[2]

A priority queue is stable if extractions of items with equal priority value occur in the order in which they were inserted. Both Implementations of priority queues here are stable.

The IterablePriorityQueue is a simple implementation of the PriorityQueue interface. It uses PHP arrays as its inner data structure.

The StablePriorityQueue class uses SplPriorityQueue as its inner queue but solves the stability problem of the SplPriorityQueue class. Thus The StablePriorityQueue is also stable.

Execution sequence

ExecutionSequence is a prioritized queue of callables that can be executed in the order of their priorities.