Create Data Structures for PHP Devs: Stacks and Queues

View: 329    Dowload: 0   Comment: 0   Post by: hanhga  
Author: none   Category: Php&mySql   Fields: Other

0 point/1 review File has been tested

A data structure, or abstract data type (ADT), is a model that is defined by a collection of operations that can be performed on itself and is limited by the constraints on the effects of those operations. It creates a wall between what can be done to the underlying data and how it is to be done.

Introduction

A data structure, or abstract data type (ADT), is a model that is defined by a collection of operations that can be performed on itself and is limited by the constraints on the effects of those operations. It creates a wall between what can be done to the underlying data and how it is to be done.

Most of us are familiar with stacks and queues in normal everyday usage, but what do supermarket queues and vending machines have to do with data structures? Let’s find out. In this article I’ll introduce you to two basic abstract data types – stack and queue – which have their origins in everyday usage.

Stacks

In common usage, a stack is a pile of objects which are typically arranged in layers – for example, a stack of books on your desk, or a stack of trays in the school cafeteria. In computer science parlance, a stack is a sequential collection with a particular property, in that, the last object placed on the stack, will be the first object removed. This property is commonly referred to as last in first out, or LIFO. Candy, chip, and cigarette vending machines operate on the same principle; the last item loaded in the rack is dispensed first.

In abstract terms, a stack is a linear list of items in which all additions to (a “push”) and deletions from (a “pop”) the list are restricted to one end – defined as the “top” (of the stack). The basic operations which define a stack are:

init – create the stack.

push – add an item to the top of the stack.

pop – remove the last item added to the top of the stack.

top – look at the item on the top of the stack without removing it.

isEmpty – return whether the stack contains no more items.

A stack can also be implemented to have a maximum capacity. If the stack is full and does not contain enough slots to accept new entities, it is said to be an overflow – hence the phrase “stack overflow”. Likewise, if a pop operation is attempted on an empty stack then a “stack underflow” occurs.

Knowing that our stack is defined by the LIFO property and a number of basic operations, notably push and pop, we can easily implement a stack using arrays since arrays already provide push and pop operations.

Here’s what our simple stack looks like:

<?php
class ReadingList
{
    protected $stack;
    protected $limit;
    
    public function __construct($limit = 10) {
        // initialize the stack
        $this->stack = array();
        // stack can only contain this many items
        $this->limit = $limit;
    }

    public function push($item) {
        // trap for stack overflow
        if (count($this->stack) < $this->limit) {
            // prepend item to the start of the array
            array_unshift($this->stack, $item);
        } else {
            throw new RunTimeException('Stack is full!'); 
        }
    }

    public function pop() {
        if ($this->isEmpty()) {
            // trap for stack underflow
       throw new RunTimeException('Stack is empty!');
   } else {
            // pop item from the start of the array
            return array_shift($this->stack);
        }
    }

    public function top() {
        return current($this->stack);
    }

    public function isEmpty() {
        return empty($this->stack);
    }
}

In this example, I’ve used array_unshift() and array_shift(), rather than array_push() andarray_pop(), so that the first element of the stack is always the top. You could use array_push() andarray_pop() to maintain semantic consistency, in which case, the Nth element of the stack becomes the top. It makes no difference either way since the whole purpose of an abstract data type is to abstract the manipulation of the data from its actual implementation.

Let’s add some items to the stack:

<?php
$myBooks = new ReadingList();

$myBooks->push('A Dream of Spring');
$myBooks->push('The Winds of Winter');
$myBooks->push('A Dance with Dragons');
$myBooks->push('A Feast for Crows');
$myBooks->push('A Storm of Swords'); 
$myBooks->push('A Clash of Kings');
$myBooks->push('A Game of Thrones');

To remove some items from the stack:

<?php
echo $myBooks->pop(); // outputs 'A Game of Thrones'
echo $myBooks->pop(); // outputs 'A Clash of Kings'
echo $myBooks->pop(); // outputs 'A Storm of Swords'

Let’s see what’s at the top of the stack:

<?php
echo $myBooks->top(); // outputs 'A Feast for Crows'

What if we remove it?

<?php
echo $myBooks->pop(); // outputs 'A Feast for Crows'

And if we add a new item?

<?php
$myBooks->push('The Armageddon Rag');
echo $myBooks->pop(); // outputs 'The Armageddon Rag'

You can see the stack operates on a last in first out basis. Whatever is last added to the stack is the first to be removed. If you continue to pop items until the stack is empty, you’ll get a stack underflow runtime exception.

PHP Fatal error:  Uncaught exception 'RuntimeException' with message 'Stack is empty!' in /home/ignatius/Data Structures/code/array_stack.php:33
Stack trace:
#0 /home/ignatius/Data Structures/code/example.php(31): ReadingList->pop()
#1 /home/ignatius/Data Structures/code/array_stack.php(54): include('/home/ignatius/...')
#2 {main}
  thrown in /home/ignatius/Data Structures/code/array_stack.php on line 33

Oh, hello… PHP has kindly provided a stack trace showing the program execution call stack prior and up to the exception!

The SPLStack

The SPL extension provides a set of standard data structures, including the SplStack class (PHP5 >= 5.3.0). We can implement the same object, although much more tersely, using an SplStack as follows:

<?php
class ReadingList extends SplStack
{
}

The SplStack class implements a few more methods than we’ve originally defined. This is becauseSplStack is implemented as a doubly-linked list, which provides the capacity to implement a traversable stack.

A linked list, which is another abstract data type itself, is a linear collection of objects (nodes) used to represent a particular sequence, where each node in the collection maintains a pointer to the next node in collection. In its simplest form, a linked list looks something like this:

dstructure1-01

In a doubly-linked list, each node has two pointers, each pointing to the next and previous nodes in the collection. This type of data structure allows for traversal in both directions.

dstructure1-02

Nodes marked with a cross (X) denotes a null or sentinel node – which designates the end of the traversal path (i.e. the path terminator).

Since ReadingList is implemented as an SplStack, we can traverse the stack forward (top-down) andbackward (bottom-up). The default traversal mode for SplStack is LIFO:

<?php
// top-down traversal
// default traversal mode is SplDoublyLinkedList::IT_MODE_LIFO|SplDoublyLinkedList::IT_MODE_KEEP
foreach ($myBooks as $book) {
    echo $book . "n"; // prints last item first!
}

To traverse the stack in reverse order, we simply set the iterator mode to FIFO (first in, first out):

<?php
// bottom-up traversal
$myBooks->setIteratorMode(
    SplDoublyLinkedList::IT_MODE_FIFO|SplDoublyLinkedList::IT_MODE_KEEP
);
foreach ($myBooks as $book) {
    echo $book . "n";  // prints first added item first
}

Queues

If you’ve ever been in a line at the supermarket checkout, then you’ll know that the first person in line gets served first. In computer terminology, a queue is another abstract data type, which operates on a first in first out basis, or FIFO. Inventory is also managed on a FIFO basis, particularly if such items are of a perishable nature.

The basic operations which define a queue are:

init – create the queue.

enqueue – add an item to the “end” (tail) of the queue.

dequeue – remove an item from the “front” (head) of the queue.

isEmpty – return whether the queue contains no more items.

Since SplQueue is also implemented using a doubly-linked list, the semantic meaning of top and pop are reversed in this context. Let’s redefine our ReadingList class as a queue:

<?php
class ReadingList extends SplQueue
{
}

$myBooks = new ReadingList();

// add some items to the queue
$myBooks->enqueue('A Game of Thrones');
$myBooks->enqueue('A Clash of Kings');
$myBooks->enqueue('A Storm of Swords');

SplDoublyLinkedList also implements the ArrayAccess interface so you can also add items to bothSplQueue and SplStack as array elements:

<?php
$myBooks[] = 'A Feast of Crows';
$myBooks[] = 'A Dance with Dragons';

To remove items from the front of the queue:

<?php
echo $myBooks->dequeue() . "n"; // outputs 'A Game of Thrones'
echo $myBooks->dequeue() . "n"; // outputs 'A Clash of Kings'

enqueue() is an alias for push(), but note that dequeue() is not an alias for pop()pop() has a different meaning and function in the context of a queue. If we had used pop() here, it would remove the item from the end (tail) of the queue which violates the FIFO rule.

Similarly, to see what’s at the front (head) of the queue, we have to use bottom() instead of top():

<?php
echo $myBooks->bottom() . "n"; // outputs 'A Storm of Swords'

 

Create Data Structures for PHP Devs: Stacks and Queues

Create Data Structures for PHP Devs: Stacks and Queues Posted on 08-04-2016  A data structure, or abstract data type (ADT), is a model that is defined by a collection of operations that can be performed on itself and is limited by the constraints on the effects of those operations. It creates a wall between what can be done to the underlying data and how it is to be done. 5/10 329

Comment:

To comment you must be logged in members.

Files with category

  • How to Picking the Brains of Your Customers with Microsoft’s Text Analytics

    View: 4071    Download: 0   Comment: 0   Author: none  

    How to Picking the Brains of Your Customers with Microsoft’s Text Analytics

    Category: Php&mySql
    Fields: Other

    1.6666666666667/3 review
    With the explosion of machine learning services in recent years, it has become easier than ever for developers to create “smart apps”. In this article, I’ll introduce you to Microsoft’s offering for providing machine-learning capabilities to apps.

  • How to MySqli Tutorial PHP MySqli Extension

    View: 395    Download: 0   Comment: 0   Author: none  

    How to MySqli Tutorial PHP MySqli Extension

    Category: Php&mySql
    Fields: Other

    0/0 review
    PHP provides three api to connect mysql Database.

  • Make Laravel Artisan Commands

    View: 377    Download: 0   Comment: 0   Author: none  

    Make Laravel Artisan Commands

    Category: Php&mySql
    Fields: Other

    0/0 review
    Artisan is the command line tool used in Laravel framework. It offers a bunch of useful command that can help you develop application quickly. Apart from Artisan available commands, you can create your own custom commands to improve your workflow.

  • Check if a Number is a Power of 2

    View: 343    Download: 0   Comment: 0   Author: none  

    Check if a Number is a Power of 2

    Category: Php&mySql
    Fields: Other

    1.5/3 review
    How to check if a number is a power of 2. To understand this question, let’s take some example.

  • Concatenate columns in MySql

    View: 403    Download: 0   Comment: 0   Author: none  

    Concatenate columns in MySql

    Category: Php&mySql
    Fields: Other

    0/2 review
    Artisan is the command line tool used in Laravel framework. It offers a bunch of useful command that can help you develop application quickly. Apart from Artisan available commands, you can create your own custom commands to improve your workflow

  • How to Query NULL Value in MySql

    View: 336    Download: 0   Comment: 0   Author: none  

    How to Query NULL Value in MySql

    Category: Php&mySql
    Fields: Other

    5/1 review
    Misunderstanding NULL is common mistake beginners do while writing MySql query. While quering in MySql they compare column name with NULL. In MySql NULL is nothing or in simple word it isUnknown Value so if you use comparison operator for NULL values...

  • How to Abstract Class in PHP

    View: 374    Download: 0   Comment: 0   Author: none  

    How to Abstract Class in PHP

    Category: Php&mySql
    Fields: Other

    0/0 review
    What is an abstract class in PHP and when to use an abstract class in your application. In this tutorial, we’ll learn about abstract class and their implementation.

  • Use Enums in Rails for Mapped Values

    View: 337    Download: 0   Comment: 0   Author: none  

    Use Enums in Rails for Mapped Values

    Category: Php&mySql
    Fields: Other

    2.5/2 review
    When I worked in a call center, we used to mark cases with different statuses. This allowed upper management to get a handle on where cases stood, what the bottlenecks were and flow of calls. Thankfully it has been a long time since I worked in a...

 

File suggestion for you

File top downloads

logo codetitle
Codetitle.com - library source code to share, download the file to the community
Copyright © 2015. All rights reserved. codetitle.com Develope by Vinagon .Ltd