Posted By

mscribellito on 01/03/11


Tagged

php array stack


Versions (?)

PHP Stack


 / Published in: PHP
 

  1. <?php
  2.  
  3. /*
  4.  * @class: Stack
  5.  * @author: Michael Scribellito
  6.  * @date: 7-5-11
  7.  */
  8.  
  9. require 'Node.php';
  10.  
  11. /*
  12.  * Stack
  13.  * =====
  14.  *
  15.  * Represents a last-in-first-out (LIFO) stack of generic items. It supports
  16.  * the usual push and pop operations, along with methods for peeking at the top
  17.  * item, testing if the stack is empty, and iterating through the items in LIFO
  18.  * order.
  19.  *
  20.  * All stack operations are constant time.
  21.  */
  22.  
  23. class Stack {
  24.  
  25. // size of the stack
  26. private $N;
  27. // top of stack
  28. private $first;
  29.  
  30. // create an empty stack.
  31. public function __construct() {
  32.  
  33. $this->N = 0;
  34. $this->first = NULL;
  35.  
  36. }
  37.  
  38. // is the stack empty?
  39. public function isEmpty() {
  40.  
  41. return $this->first == NULL;
  42.  
  43. }
  44.  
  45. // return the number of items in the stack.
  46. public function size() {
  47.  
  48. return $this->N;
  49.  
  50. }
  51.  
  52. // add the item to the stack.
  53. public function push($item) {
  54.  
  55. // save a link to the list
  56. $oldfirst = $this->first;
  57. // create a new node for the beginning
  58. $this->first = new Node();
  59. // set the instance variables in the new node
  60. $this->first->item = $item;
  61. $this->first->next = $oldfirst;
  62. // increment size
  63. $this->N++;
  64.  
  65. }
  66.  
  67. // return the item most recently added to the stack.
  68. // * throw an exception if the queue is empty.
  69. public function peek() {
  70.  
  71. if ($this->isEmpty())
  72. throw new Exception("Stack underflow");
  73. return $this->first->item;
  74.  
  75. }
  76.  
  77. // delete and return the item most recently added to the stack.
  78. // * throw an exception if the queue is empty.
  79. public function pop() {
  80.  
  81. if ($this->isEmpty())
  82. throw new Exception("Stack underflow");
  83. // save the most recently added item
  84. $item = $this->first->item;
  85. // remove the first node
  86. $this->first = $this->first->next;
  87. // decrement size
  88. $this->N--;
  89. return $item;
  90.  
  91. }
  92.  
  93. }

Report this snippet  

You need to login to post a comment.