Table of Contents
Stack
A stack is a type of data structure in which items are added and removed in a last-in, first-out (LIFO) order. Inserting an element into a stack is referred to as a "push" operation, and removing an element is called a "pop" operation.
Simple example: Image you open your browser and visit youtube.com and then google.com and finally gmail.com.
Your current browsing history looks like this (where 'gmail.com' is your currently open website):
youtube.com->google.com->gmail.com
An example of using a stack in practice is when clicking the "back" button in a web browser, which allows you to return to the previous webpage google.com after navigating away from it, with the current webpage gmail.com being removed from the top of the stack.
youtube.com->google.com
If you click back again you are back at the start.
youtube.com
Node in Stack
A node is a basic unit that stores a piece of data and a reference to the next and previous node in the list. Similar to singly linked list.
class Node
{
public $value;
public $next;
public function __construct($value)
{
$this->value = $value;
$this->next = null;
}
}
This Node class has two fields:
1, data, which stores a value of the element,
2, next, which is a reference to the next node in the list
Constructor in Stack
Let's create a class that represents a stack data structure.
This class has two instance variables:
-
$top: a reference to the first node in the list, -
$height: an integer that counts the number of nodes in the stack(it is 1 because we create a new node in the constructor).
class Stack
{
public $top;
public $height;
public function __construct(public $value)
{
$newNode = new Node($value);
$this->top = $newNode;
$this->height = 1;
}
}
Before we move to main operations, let's create a helper method to print all nodes in the stack.
EXPLANATION:
In the method printStack() we define a local variable $temp and assigns it the value of $this->top, which is a reference to the first node in the list.
It then enters a while loop that continues until $temp is not null, meaning there is no more next node.
After echoing the value, the function assigns $temp the value of $temp->next, which moves $temp to the next node in the list, to continue the loop.
public function printStack()
{
$temp = $this->top;
while ($temp != null) {
echo $temp->value."\n";
$temp = $temp->next;
}
}
Push
When we "push" a node onto a stack, we are adding a new element to the top of the stack. A stack follows the LIFO (Last In First Out) principle, which means that the last element added to the stack will be the first one to be removed. So when you push a new node into a stack, this new node will be the new top node of the stack.
From left to right in the image, we are adding values. First, 7, then 1, and finally 6. Notice that the reference to the top is changing with the newly added value.
EXPLANATION:
- We create a new node.
- If the stack is empty, the new node is assigned as the first node and the top reference is pointing to it.
- If the stack is not empty, the new node is connected to the current top node using the next reference.
- The top reference is updated to the new node.
- finally, we increment the count (height) of the stack.
From top to bottom, we are visiting websites that are "stacked" on top of each other.
public function push($value)
{
$newNode = new Node($value);
if ($this->height == 0) {
$this->top = $newNode;
} else {
$newNode->next = $this->top;
$this->top = $newNode;
}
$this->height++;
}
// $s = new Stack('youtube.com');
// $s->push('google.com');
// $s->push('gmail.com');
// $s->printStack();
//
// gmail.com
// google.com
// youtube.com
Pop
"Pop" is an operation on a stack that removes the element at the top of the stack and returns it. This operation also updates the top reference of the stack to the next element and decrements the count (height) of the stack.
Remember: For something to be a stack you just have to add and remove from the same end.
From left to right in the image, we are removing values. First, 6, then 1, and finally 7. Notice that the reference to the top is changing with the newly added value.
EXPLANATION:
- If the stack is empty, we return null.
- Else, we assign a temporary variable to the current top of the stack.
- We change the top reference to the next element in the stack.
- Once the top is changed, we can reset the previous top (stored in the temporary variable) to null.
- Finally, we decrease the count (height) of the stack.
From top to bottom, when we click the "back" button, we visit previous websites that are "stacked" on top of each other.
public function pop()
{
if ($this->height == 0) {
return null;
}
$temp = $this->top;
$this->top = $this->top->next;
$temp->next = null;
$this->height--;
return $temp;
}
// $s = new Stack('youtube.com');
// $s->push('google.com');
// $s->push('gmail.com');
// $s->pop(); // removes top
// $s->printStack();
//
// google.com
// youtube.com
Stack in Arrays
In PHP, built-in functions like array_push and array_pop can be used to implement a stack using an array data structure.
$stack = [];
array_push($stack, 'youtube.com');
array_push($stack, 'google.com');
array_push($stack, 'gmail.com');
array_pop($stack);
// $stack = [
// "youtube.com",
// "google.com",
// ]
The time complexity of array push and pop operations in PHP, when implemented using the array_push and array_pop functions, is O(1) on average.
NOTICE: You can achieve the stack principle also when you prepend and pop first element in array, when implemented using array_unshift and array_shift functions, but is O(n) in the worst case.
Time Complexity in Stack
Push: O(1) - This operation takes constant time, as it only involves adding an element to the top of the stack.
Pop: O(1) - This operation also takes constant time, as it only involves removing the top element from the stack.
NOTE: These complexities are for basic implementations of stacks and queues using arrays or linked lists.
Queue
A Queue is a linear data structure, in which the first element added is the first one to be removed. This order is known as First-In-First-Out (FIFO).
A common example of a queue is a line of people waiting for an order, where the person who arrived first will be served first. The main difference between a queue and a stack is in how elements are removed. In a stack, the most recently added element is removed first, while in a queue, the least recently added element is removed first.
FULL SCRIPT:
https://gist.github.com/matusstafura/4bd1beeba61f1995b3fcd18a77bf87c6
Node in Queue
We use the same definition as in stack.
class Node
{
public $value;
public $next;
public function __construct($value)
{
$this->value = $value;
$this->next = null;
}
}
Constructor in Queue
Let's create a class that represents a queue data structure.
This LinkedList class has three instance variables:
-
$first: a reference to the first node in the list, -
$last: a reference to the last node in the list, -
$length: an integer that counts the number of nodes in the list.
class Queue
{
public $first;
public $last;
public $length;
public function __construct(public $value)
{
$newNode = new Node($value);
$this->first = $newNode;
$this->last = $newNode;
$this->length = 1;
}
}
For printing we use the same logic of echoing values as in the stack.
public function printQueue()
{
$temp = $this->first;
while ($temp != null) {
echo $temp->value."\n";
$temp = $temp->next;
}
}
Enqueue
To enqueue means to add new node to a queue(also known as push, add or insert operation).
From top to bottom, we are adding values to the queue.
EXPLANATION:
- We create a new node.
- If the queue is empty, the new node is assigned as the first and last node.
- If the queue is not empty, the next reference of the last node is connected to the new node.
- The last reference is updated to the new node.
- We increase the length of a queue.
public function enqueue($value)
{
$newNode = new Node($value);
if ($this->length == 0) {
$this->first = $newNode;
$this->last = $newNode;
} else {
$this->last->next = $newNode;
$this->last = $newNode;
}
$this->length++;
}
// $q = new Queue("first customer");
// $q->enqueue("second customer");
// $q->enqueue("third customer");
//
// $q->printQueue();
// first customer
// second customer
// third customer
Dequeue
To "dequeue" (also known as pop, remove or delete) refers to the operation of removing the element at the front of the queue.
From top to bottom, we are removing values to the queue
The queue follows the First-In-First-Out (FIFO) ordering principle so we need to remove first one.
EXPLANATION:
- We return null if the queue is empty.
- If the queue has only one node, we reset its first and last references to null.
- Otherwise, we assign the first reference to the next node.
- We unlink the previous first node by resetting it to null.
- Finally, we decrease the length of the queue.
public function dequeue()
{
if ($this->length == 0) {
return null;
}
$temp = $this->first;
if ($this->length == 1) {
$this->first = null;
$this->last = null;
} else {
$this->first = $this->first->next;
$temp->next = null;
}
$this->length--;
return $temp;
}
// $q = new Queue("first customer");
// $q->enqueue("second customer");
// $q->enqueue("third customer");
// $q->dequeue();
//
// $q->printQueue();
// second customer
// third customer
Queues in Arrays
$stack = [];
array_push($stack, 'youtube.com');
array_push($stack, 'google.com');
array_push($stack, 'gmail.com');
array_shift($queue);
// $stack = [
// "google.com",
// "gmail.com",
// ]
The time complexity of array_push function in this example is O(1) and for the array_shift function in PHP is O(n), where n is the size of the input array.
Time Complexity in Queue
In our example for linked list:
Enqueue: O(1) - This operation takes constant time, as it only involves adding an element to the back of the queue.
Dequeue: O(1) - This operation takes constant time, as it only involves removing the front element from the queue.
FULL SCRIPT:
https://gist.github.com/matusstafura/e70b13f3cbf38a3efc00b3dcb561bb59
Top comments (0)