In Chapter 3, Using Linked Lists, we learned how to implement linked lists. We saw that in a linked list we can insert a node at the end, remove it from the end, insert it into the middle of the list, at the beginning, and so on. If we consider the insert at the end and remove at the end operations of a single linked list data structure, we can easily perform something similar with stack. So let us use our LinkedList class from the previous chapter to implement with the stack. This is how the code will look:

class BookList implements Stack { 

    private $stack; 

    public function __construct() { 
      $this->stack = new LinkedList(); 
    }

    public function pop(): string { 

      if ($this->isEmpty()) { 
          throw new UnderflowException('Stack is empty'); 
      } else { 
          $lastItem = $this->top(); 
          $this->stack->deleteLast(); 
          return $lastItem; 
      } 
    } 

    public function push(string $newItem) { 

      $this->stack->insert($newItem); 
    } 


public function top(): string { 
  return $this->stack->getNthNode($this->stack->getSize())->data; 
} 

    public function isEmpty(): bool { 
      return $this->stack->getSize() == 0; 
    } 
}

Let us go through each of the code blocks to understand what is happening here. If we start from the top, we can see that in the constructor method, we are creating a new LinkedList object and assigning it to our stack property instead of the array in the previous example. We are assuming that the LinkedList class is autoloaded, or the file is included in the script. Let us now focus on the push operation. The push operation is as simple as it can get. We just need to insert a new node in the linked list. Since we do not have any size limit for the linked list, we are not checking any overflow here.

In our linked list implementation, there was no method for displaying the last node. We had inserted a new last node and removed the previous last node, but here, we need to get the value of the last node without deleting it. In order to achieve that functionality, which is exactly the top operation for our stack, we can utilize the getNthNode method along with getSize from the LinkedList implementation. This way, we can get the node. But we have to remember one thing: we want the string value of the node, not the full node object. That is why we return the data property of the returned node.

Similar to the top operation, the pop operation also needs to return the last node's data before removing it from the list. In order to achieve that, we use the top() method and then the deleteLast() method from the LinkedList class. Now let us run a sample code to use this newly implemented BookList class for stack operations. Here is the code:

try { 
    $programmingBooks = new BookList(); 
    $programmingBooks->push("Introduction to PHP7"); 
    $programmingBooks->push("Mastering JavaScript"); 
    $programmingBooks->push("MySQL Workbench tutorial"); 
    echo $programmingBooks->pop()."
"; 
    echo $programmingBooks->pop()."
"; 
    echo $programmingBooks->top()."
"; 
} catch (Exception $e) { 
    echo $e->getMessage(); 
}

It looks quite similar to the last example we ran, but here we are trying to do two pop operations and then the top one. So the output will look like the following:

MySQL Workbench tutorial
Mastering JavaScript
Introduction to PHP7

If we know the basic behavior of the stack and how to achieve it, we can use an array, linked list, doubly linked list to implement stack. Since we have already seen the array and linked list implementations, we are now going to explore the SPL implementation of a stack, which actually uses a doubly linked list.