Stacks and Queues for app.codility.com/programmers Explained in PHP

Category of Article : Technology | Computers and Software | Algorithms

By: Chrysanthus Date Published: 4 Jul 2025

A data structure is like an array. However, its size can grow or shrink, unlike the size of a C/C++ array, which can neither grow nor shrink. A typical data structure also has attributes (associated data variables) and methods (associated functions). In this tutorial (lesson), is described two data structures used for storage of elements. The two data structures of interest here, are called, the stack and the queue. Both structures have the push() and pop() methods. The push() method behaves in the same way for both structures, but the pop() method behaves differently by acting at opposite ends of the data structures.

Stack

The stack container (or stack for short), is a data structure in which the insertion of a new element takes place at the top, and the deletion (removal) of an element, also takes place from the top. The idea of the stack can be illustrated by plates stacked on top of one another. Each new plate is placed on top of the stack of plates (operation push), and plates can only be taken off the top of the stack (operation pop). This is a Last-In-First-Out (LIFO) data structure.

Use of the push() and pop() methods for the Stack

The following program pushes the list of integers,

4, 8, 6, 3

one-by-one onto a stack, and then pops them out one-by-one from the top of the stack. The stack begins with the number 4 and then ends with the number 3. So, in the popping operations, 3 will be sent out first. The program is:

<?php
        $stack = new SplStack();    //new Standard PHP Library stack

        $stack->push(4); $stack->push(8); $stack->push(6); $stack->push(3);
        
        $int1 = $stack[0]; $stack->pop(); 
        $int2 = $stack[0]; $stack->pop(); 
        $int3 = $stack[0]; $stack->pop(); 
        $int4 = $stack[0]; $stack->pop(); 
        
        echo $int1 . ', ' . $int2 . ', ' . $int3 . ', ' . $int4 . ', ' . "\n";
?>

The output is:

3, 6, 8, 4

in reverse order, as expected, since it is last-in-first-out. The top() method (stack[0]) copies out the last (top) element, while the pop() method removes the last (top) element and "throws it away". Note: The push() or top() or pop() method takes O(1) time. The sequence of operations for the whole list takes O(n) time, with pushing or with popping.

Queue

The queue container (or queue for short), is a data structure in which a new element is inserted at the back, but an old element is removed from the front, in order. The idea of the queue can be illustrated by a line of customers at a grocery store. New people join the back of the queue (push operation) and the next person to be served, is the one in front (pop operation), of the line (queue). After serving, he/she goes away. This is a First-In-First-Out (FIFO) data structure.

With the Standard PHP Library, the push() method is enqueue() and the pop() method is dequeue.

Use of enqueue() and dequeue() methods for the Queue

The following program pushes (enqueues) the list of integers,

4, 8, 6, 3

one-by-one into a queue from the back, and then dequeues them out one-by-one from the front (top) of the queue. The queue begins with the number 4 and then ends with the number 3. So, in the popping (dequeue) operations, 4 will be sent out first. The program is:

<?php
        $queue = new SplQueue();    //for new Standard PHP Library queue

        $queue->enqueue(4); $queue->enqueue(8); $queue->enqueue(6); $queue->enqueue(3);
        
        $int1 = $queue[0]; $queue->dequeue();
        $int2 = $queue[0]; $queue->dequeue();
        $int3 = $queue[0]; $queue->dequeue();
        $int4 = $queue[0]; $queue->dequeue();
        
        echo $int1 . ', ' . $int2 . ', ' . $int3 . ', ' . $int4 . "\n";
?>

The output is:

4, 8, 6, 3

in same order, as expected, since it is first-in-first-out. The top() method (queue[0]) copies out the first (top) element, while the pop() method (dequeue()) removes the first(top) element and "throws it away". Note: The push() or top() or pop() method takes O(1) time. The sequence of operations for the whole list takes O(n) time, with pushing or with popping.

The length of the Stack and the Queue

The Standard PHP Library stack and queue do not have the length (same as size) attribute. Instead, the count() predefined function is used to determine the length (or size) of the stack or queue. The following program illustrates this:

<?php
        $stack = new SplStack(); 
        $stack->push(4); $stack->push(8); $stack->push(6); $stack->push(3);
    
        $queue = new SplQueue();
        $queue->enqueue(4); $queue->enqueue(8); $queue->enqueue(6); $queue->enqueue(3);
        
        echo 'The size of the stack is: ' . count($stack) . " and the size of the queue is: " . count($queue) . "\n";
?>

The output is:

The size of the stack is: 4 and the size of the queue is: 4

Conclusion

A data structure is like an array. However, its size can grow or shrink, unlike the size of an array, which can neither grow nor shrink. A typical data structure has attributes (associated data variables) and methods (associated functions). The stack is a Last-In-First-Out data structure. The queue is a First-In-First-Out data structure.

The Standard PHP Library stack and queue do not have the length (same as size) attribute. Instead, the count() predefined function is used to determine the length (or size) of the stack or queue.

The rest of the 17 lessons, with explanation of lessons, explanation of tasks, and explanation of solutions, can be found at (click): Explanations in PHP for the 17 Algorithm Lessons at https://app.codility.com/programmers with Problems and Solutions

Cousins

NEXT

Broad Network

Series Articles