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.
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.
php1<?php 2 3class StackOfPlates { 4 private array $stack; 5 6 public function __construct() { 7 $this->stack = array(); 8 } 9 10 // Inserts a plate at the top of the stack 11 public function addPlate(mixed $plate): void { 12 array_push($this->stack, $plate); // Using array_push to add a plate 13 } 14 15 // Removes the top plate from the stack 16 public function removePlate(): mixed { 17 if (empty($this->stack)) { // Using isEmpty to check if stack is empty 18 return "No plates left to remove!"; 19 } 20 return array_pop($this->stack); // Using array_pop to remove and return the top plate 21 } 22 23 public function isEmpty(): bool { 24 return empty($this->stack); 25 } 26 27 public function top(): mixed { 28 if (empty($this->stack)) { 29 return "No plates in the stack!"; 30 } 31 return end($this->stack); // Using end to get the top element 32 } 33} 34 35// Example usage: 36$plates = new StackOfPlates(); 37$plates->addPlate("Plate"); 38$plates->addPlate("Another Plate"); 39 40echo "Removed: " . $plates->removePlate() . "\n"; // Outputs: Removed: Another Plate 41 42?>
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.
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.
php1<?php 2 3class QueueOfPeople { 4 private SplQueue $queue; 5 6 public function __construct() { 7 $this->queue = new SplQueue(); 8 } 9 10 // Adds a person to the end of the queue 11 public function enqueuePerson(mixed $person): void { 12 $this->queue->enqueue($person); // Using enqueue to add a person 13 } 14 15 // Removes the first person from the queue (who has been waiting the longest) 16 public function dequeuePerson(): mixed { 17 if ($this->queue->isEmpty()) { // Using isEmpty to check if queue is empty 18 return "No people left to dequeue!"; 19 } 20 return $this->queue->dequeue(); // Using dequeue to remove and return the first person 21 } 22 23 // Checks whether the queue is empty 24 public function isEmpty(): bool { 25 return $this->queue->isEmpty(); 26 } 27 28 // Returns the first person of the queue without removing them 29 public function frontPerson(): mixed { 30 if ($this->queue->isEmpty()) { 31 return "No people in the queue!"; 32 } 33 return $this->queue->bottom(); // or use $this->queue->bottom() 34 } 35} 36 37// Example usage: 38$people = new QueueOfPeople(); 39$people->enqueuePerson("Person 1"); 40$people->enqueuePerson("Person 2"); 41 42echo "Removed: " . $people->dequeuePerson() . "\n"; // Outputs: Removed: Person 1 43 44?>
Here, Person 1, the first to join the queue, left before Person 2, demonstrating the FIFO property of a queue.
Let's depict the two structures in a text editor that features an Undo mechanism (a Stack) and a Print Queue.
php1<?php 2 3class TextEditor { 4 private array $undoStack; 5 private SplQueue $printQueue; 6 7 public function __construct() { 8 $this->undoStack = array(); 9 $this->printQueue = new SplQueue(); 10 } 11 12 // Makes a change (e.g., edits text, inserts image, changes font) 13 public function makeChange(mixed $action): void { 14 array_push($this->undoStack, $action); // Adds to the stack of actions 15 } 16 17 // Undoes the most recent change 18 public function undoChange(): mixed { 19 if (empty($this->undoStack)) { 20 return "No changes to undo!"; 21 } 22 return array_pop($this->undoStack); 23 } 24 25 // Adds a document to the queue for printing 26 public function addToPrint(mixed $doc): void { 27 $this->printQueue->enqueue($doc); 28 } 29 30 // Prints the document that has been waiting the longest 31 public function printDoc(): mixed { 32 if ($this->printQueue->isEmpty()) { 33 return "No documents in the print queue!"; 34 } 35 return $this->printQueue->dequeue(); 36 } 37} 38 39// Example usage: 40$editor = new TextEditor(); 41$editor->makeChange("Changed font size"); 42$editor->makeChange("Inserted image"); 43 44echo "Undo: " . $editor->undoChange() . "\n"; // Outputs: Undo: Inserted image 45 46$editor->addToPrint("Proposal.docx"); 47$editor->addToPrint("Report.xlsx"); 48 49echo "Print: " . $editor->printDoc() . "\n"; // Outputs: Print: Proposal.docx 50 51?>
This code reintroduces the concepts of a Stack (Undo feature) and Queue (Print queue) in the context of a real-life scenario.
Great work! You have explored the mechanics of Stacks and Queues using arrays and PHP's SplQueue. Remember to practice these concepts in your PHP projects. Happy coding!