Stacks and Queues in PHP: Concepts and Implementation

Introduction: Stacks and Queues

Welcome to an exciting exploration of two fundamental data structures: Stacks and Queues in PHP! In computing, these structures help organize data efficiently. Stacks and Queues are akin to stacking plates and standing in a line, respectively. For queues, we will use PHP's SplQueue, and for stacks, we will utilize a simple array, though SplStack is also an option, as we'll mention later.

Stacks: Last In, First Out (LIFO)

A Stack adheres to the "Last In, First Out" or LIFO principle. It's similar to a pile of plates where the last plate added is the first one to be removed. In this section, we will use a simple array to implement a stack. The primary operations for stacks involve adding and removing elements: push: Adds an element to the top of the stack. pop: Removes the top element from the stack. isEmpty: Checks whether the stack is empty. top: Returns the top element of the stack without removing it. Let's explore this concept using a pile of plates as an analogy. PHP<?php class StackOfPlates { private array $stack; public function __construct() { $this->stack = array(); } // Inserts a plate at the top of the stack public function addPlate(mixed $plate): void { array_push($this->stack, $plate); // Using array_push to add a plate } // Removes the top plate from the stack public function removePlate(): mixed { if (empty($this->stack)) { // Using isEmpty to check if stack is empty return "No plates left to remove!"; } return array_pop($this->stack); // Using array_pop to remove and return the top plate } public function isEmpty(): bool { return empty($this->stack); } public function top(): mixed { if (empty($this->stack)) { return "No plates in the stack!"; } return end($this->stack); // Using end to get the top element } } // Example usage: $plates = new StackOfPlates(); $plates->addPlate("Plate"); $plates->addPlate("Another Plate"); echo "Removed: " . $plates->removePlate() . "\n"; // Outputs: Removed: Another Plate ?> The last plate added was removed first, demonstrating the LIFO property of a stack. While we used an array here for illustration, PHP's Standard PHP Library contains the SplStack class that can also be used for stack operations, providing more functionality and consistency.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Queues: First In, First Out (FIFO)

A Queue represents the "First In, First Out" or FIFO principle, much like waiting in line at the grocery store. PHP provides the SplQueue class from the SPL to work with queues. The primary methods used with queues are enqueue, dequeue, isEmpty, and bottom (or front):

enqueue: Adds an element to the end of the queue.
dequeue: Removes the first element from the queue.
isEmpty: Checks whether the queue is empty.
bottom (or front): Returns the first element of the queue without removing it.

Let's examine this through a queue of people.

PHP

<?php

class QueueOfPeople {
    private SplQueue $queue;

    public function __construct() {
        $this->queue = new SplQueue();
    }

    // Adds a person to the end of the queue
    public function enqueuePerson(mixed $person): void {
        $this->queue->enqueue($person); // Using enqueue to add a person
    }

    // Removes the first person from the queue (who has been waiting the longest)
    public function dequeuePerson(): mixed {
        if ($this->queue->isEmpty()) { // Using isEmpty to check if queue is empty
            return "No people left to dequeue!";
        }
        return $this->queue->dequeue(); // Using dequeue to remove and return the first person
    }

    // Checks whether the queue is empty
    public function isEmpty(): bool {
        return $this->queue->isEmpty();
    }

    // Returns the first person of the queue without removing them
    public function frontPerson(): mixed {
        if ($this->queue->isEmpty()) {
            return "No people in the queue!";
        }
        return $this->queue->bottom(); // or use $this->queue->bottom()
    }
}

// Example usage:
$people = new QueueOfPeople();
$people->enqueuePerson("Person 1");
$people->enqueuePerson("Person 2");

echo "Removed: " . $people->dequeuePerson() . "\n"; // Outputs: Removed: Person 1

?>

Here, Person 1, the first to join the queue, left before Person 2, demonstrating the FIFO property of a queue.

Introduction: Stacks and Queues

Stacks: Last In, First Out (LIFO)

Join the 1M+ learners on CodeSignal

Queues: First In, First Out (FIFO)

Mastering Stack and Queue Operations With a Class

Lesson Summary