Stacks and Their Applications in PHP | CodeSignal Learn

Stacks and Their Applications in PHP | CodeSignal Learn

Introduction

Greetings, Space Explorer! Today, we're diving into Stacks in PHP, a crucial data structure. A stack is like a pile of dishes: you add a dish to the top (Last In) and take it from the top (First Out). This Last-In, First-Out (LIFO) principle exemplifies the stack. In PHP, stacks are implemented using arrays. This lesson will illuminate the stack data structure, its operations, and its applications in PHP. Are you ready to start?

Utilizing Stacks in PHP

In PHP, the behavior of stacks is achieved with arrays. To add an element to the stack, we use the array_push() function, which adds an element to the end of the array. To remove the last element from the stack, simulating the 'top' element removal, we use the array_pop() function. Here's how it looks: <?php $stack = []; // A new empty stack // Push operations array_push($stack, "John"); array_push($stack, "Mary"); array_push($stack, "Steve"); array_pop($stack); // Pop operation removes 'Steve' echo implode(" -> ", $stack) . "\n"; // Outputs: John -> Mary ?> In the example provided, we push John, Mary, and Steve into the stack and then pop Steve from the stack. Note: An alternative way to implement a stack is to use the SplStack class from the standard library, feel free to ask me questions if you are curious about that!

Advanced Stack Operations

Stack operations go beyond merely Push and Pop. For example, to verify if a stack is empty, we can check if the count() of the array is 0. To peek at the top element of the stack without popping it, we use the end() function. Here's an example: <?php $stack = []; array_push($stack, "Steve"); array_push($stack, "Sam"); echo end($stack) . '\n'; // Outputs: 'Sam' echo empty($stack) ? 'true' : 'false'; // Outputs: false echo PHP_EOL; array_pop($stack); // Remove 'Sam' array_pop($stack); // Remove 'Steve' echo empty($stack) ? 'true' : 'false'; // Outputs: true echo PHP_EOL; ?> In this example, Sam is added (pushed), and then the topmost stack element, which is Sam, is peeked at.

Practical Stack Applications: Reversing a String

Sign up

Join the 1M+ learners on CodeSignal

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

PHP

<?php

$stack = []; // A new empty stack

// Push operations
array_push($stack, "John");
array_push($stack, "Mary");
array_push($stack, "Steve");

array_pop($stack); // Pop operation removes 'Steve'

echo implode(" -> ", $stack) . "\n"; // Outputs: John -> Mary

?>

PHP

<?php

$stack = [];
array_push($stack, "Steve");
array_push($stack, "Sam");

echo end($stack) . '\n'; // Outputs: 'Sam'

echo empty($stack) ? 'true' : 'false'; // Outputs: false
echo PHP_EOL;
array_pop($stack); // Remove 'Sam'
array_pop($stack); // Remove 'Steve'
echo empty($stack) ? 'true' : 'false'; // Outputs: true
echo PHP_EOL;

?>

Practical applications of stacks in PHP are plentiful. Here is one of them — reversing a string.

We will push all characters into a stack and then pop them out to get a reversed string!

PHP

<?php

function reverse($input)
{
    $stack = [];
    foreach (str_split($input) as $char) {
        array_push($stack, $char);
    }
    $reversedString = '';
    while (count($stack) > 0) {
        $reversedString .= array_pop($stack);
    }
    return $reversedString;
}

echo reverse("HELLO") . "\n"; // Outputs: OLLEH

?>

A stack can be utilized to verify if parentheses in an expression are well-matched; i.e., every bracket has a corresponding pair. For example, parentheses in the string "()[{}]" are well-matched, while those in the strings "([]()", ")()[]{}", "([)]", and "[{})" are not.

Let's break down the solution into simple steps:

We start by creating an associative array that maps each closing bracket to its corresponding opening bracket and an empty stack. Then, we iterate over each character paren in the string parenString:

If paren is an opening bracket, it gets appended to the stack.
If paren is a closing bracket and the top element in the stack is the corresponding opening bracket, we remove the top element from the stack.
If neither of the above conditions is met, we return false.

Finally, if the stack is empty (all opening brackets had matching closing brackets), we return true. If there are some unmatched opening brackets left, we return false.

PHP

<?php

function isParenBalanced($parenString)
{
    $stack = [];
    $openingParen = [
        ')' => '(',
        ']' => '[',
        '}' => '{'
    ];

    foreach (str_split($parenString) as $paren) {
        if (in_array($paren, $openingParen)) {
            array_push($stack, $paren);
        } elseif (isset($openingParen[$paren])) {
            if (empty($stack) || array_pop($stack) != $openingParen[$paren]) {
                return false;
            }
        }
    }

    return empty($stack);
}

echo isParenBalanced("(())") ? 'true' : 'false'; // Outputs: True
echo PHP_EOL;
echo isParenBalanced("({[)}") ? 'true' : 'false'; // Outputs: False
echo PHP_EOL;

?>