Stack

Udemy Generic 728x90

Overview

A stack is a linear data structure. It is very useful in many applications of computer science. It is a list in which all insertions and deletions are made at one end, called the top of the stack.

Definition

In computer science, a stack is a particular kind of abstract data type or collection in which the principal (or only) operations on the collection are the addition of an entity to the collection, known as push and removal of an entity, known as pop.

The relation between the push and pop operations is such that the stack is a Last-In-First-Out (LIFO) data structure. In a LIFO data structure, the last element added to the structure must be the first one to be removed. This is equivalent to the requirement that, considered as a linear data structure, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure, referred to as the top of the stack. Often a peek or top operation is also implemented, returning the value of the top element without removing it.
A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space to accept an entity to be pushed, the stack is then considered to be in an overflow state. The pop operation removes an item from the top of the stack. A pop either reveals previously concealed items or results in an empty stack, but, if the stack is empty, it goes into underflow state, which means no items are present in stack to be removed.
A stack is a restricted data structure, because only a small number of operations are performed on it. The nature of the pop and push operations also means that stack elements have a natural order. Elements are removed from the stack in the reverse order to the order of their addition. Therefore, the lower elements are those that have been on the stack the longest.
There are basically three operations that can be performed on stacks . They are

  1. Inserting an item into a stack (push).
  2. Deleting an item from the stack (pop).
  3. Displaying the contents of the stack(pip).

 

391px-Data_stack.svg

 

In terms of PHP 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.

Example

Array Implementation of Stacks

In PHP arrays can used as stacks (Last In, First Out, or LIFO). Here we can see with below example.

<br />
&lt;?php<br />
    $stackArray = array();<br />
    array_push($stackArray, 'Delhi');<br />
    array_push($stackArray, 'Gurgaon');<br />
    var_dump($stackArray);<br />
    $last_in = array_pop($stackArray);<br />
    var_dump($last_in, $stackArray);<br />
?&gt;<br />

In the above example, we had first created an array, then added two elements to it using array_push(). Again by using  array_pop(),we extracted the last element added to the array, which will result following output:

</p>
<p>array(2) { [0]=&gt; string(5) 'Delhi' [1]=&gt; string(7) 'Gurgaon' }</p>
<p>string(7) 'Gurgaon' array(1) { [0]=&gt; string(5) 'Delhi' }</p>
<p>

Going with a broader view we can take below example to see how stack in php is look alike.

<br />
class CityList {<br />
 protected $stack;<br />
 protected $limit; </p>
<p> public function __construct($limit = 10) {<br />
 // initialize the stack<br />
 $this-&gt;stack = array();<br />
 // stack can only contain this many items<br />
 $this-&gt;limit = $limit;<br />
 } </p>
<p> public function push($item) {<br />
 // trap for stack overflow<br />
 if (count($this-&gt;stack) &amp;amp;lt; $this-&gt;limit) {<br />
 // prepend item to the start of the array<br />
 array_unshift($this-&gt;stack, $item);<br />
 } else {<br />
 throw new RunTimeException('Stack is full!');<br />
 }<br />
 }</p>
<p> public function pop() {<br />
 if ($this-&gt;isEmpty()) {<br />
 // trap for stack underflow<br />
 throw new RunTimeException('Stack is empty!');<br />
 } else {<br />
 // pop item from the start of the array<br />
 return array_shift($this-&gt;stack);<br />
 }<br />
 }</p>
<p> public function top() {<br />
 return current($this-&gt;stack);<br />
 }</p>
<p> public function isEmpty() {<br />
 return empty($this-&gt;stack);<br />
 }<br />
}<br />

In this example, array_unshift() and array_shift() has been used, so that the first element of the stack is always at the top. We could use array_push() and array_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.

Now we will use some cities to add in stack.

<br />
&lt;?php</p>
<p>$cities = new CityList();<br />
$cities-&gt;push('Delhi');<br />
$cities-&gt;push('Noida');<br />
$cities-&gt;push('Gurgaon');<br />
$cities-&gt;push('Mumbai');<br />
$cities-&gt;push('Bangalore');<br />
$cities-&gt;push('Chennai');<br />
$cities-&gt;push('Kolkata');</p>
<p>?&gt;</p>
<p>

Now remove some cities from stack

<br />
&lt;?php</p>
<p>echo $cities&gt;pop(); // outputs 'Kolkata'</p>
<p>echo $cities&gt;pop(); // outputs 'Chennai'</p>
<p>echo $cities&gt;pop(); // outputs 'Bangalore'</p>
<p>?&gt;<br />

Lets see what will be on the top of stack now.

<br />
&lt;?php</p>
<p>echo $cities-&amp;amp;gt;top(); // outputs 'Mumbai'</p>
<p>?&gt;</p>
<p>

Linked List Implementation of a Stack

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:

<br />
&lt;?php</p>
<p>class CityList extends SplStack {</p>
<p>}</p>
<p>?&gt;<br />

The SplStack class is implemented as a doubly-linked list, which provides the capacity to implement a traversable stack.A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a references (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.

 

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.

610px-Doubly-linked-list.svg

Example

CityList is splStack so we can traverse forward and backward (top-down and bottom-up).Default approach is LIFO.

<br />
&lt;?php</p>
<p># Think of the stack as an array reversed, where the last element has index zero<br />
 $stack = new SplStack();<br />
 $stack-&gt;push('Delhi');<br />
 $stack-&gt;push('Noida');<br />
 $stack-&gt;push('Gurgaon');<br />
 $stack-&gt;offsetSet(0, 'Gurgaon');<br />
# the last element has index zero<br />
 $stack-&gt;rewind();<br />
 while( $stack-&gt;valid() )<br />
 {<br />
 echo $stack-&gt;current(), PHP_EOL;<br />
 $stack-&gt;next();<br />
 }<br />
?&gt;<br />

OUTPUT

<br />
Gurgaon</p>
<p>Noida</p>
<p>Delhi<br />

Sources

http://www.phpmoot.com/other-sorting-options/

http://php.net/manual/en/class.splstack.php

http://en.wikipedia.org/wiki/Stack_(abstract_data_type)

http://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues

 

Udemy Generic 728x90

Spread the word. Share this post!