<?php
class Pilha {
    private $size;
    private $pilha;
    private $last = -1;
    
    public function Pilha($sz) {
        $this->size = $sz;
        $this->pilha = array();
    }
    
    public function push($elem) {
        if($elem !== null) {
            $this->pilha[++$this->last] = $elem;
        }
    }
    
    public function pop() {
        if($this->last >= 0) {
            return $this->pilha[$this->last--];
        } else {
            return null;
        }
    }
    
    public function is_full() {
        return $this->size-1 == $this->last;
    }
}    

class ElementoLista {
    private $prev;
    private $next;
    private $value;
    
    public function ElementoLista($elem) {
        $this->value = $elem;
    }
    
    public function get() { return $this->value; }
    public function set($e)  { $this->value = $e; }
    
    public function setPrev($p) { $this->prev = $p; }
    public function setNext($n) { $this->next = $n; }
    
    public function getPrev() { return $this->prev; }
    public function getNext() { return $this->next; }
}

class ListaEncadeada {
    private $size;
    private $lista = array();
    
    private $vazios;
    
    private $pointer = null;
    
    private $first = null;
    private $last = null;
    
    public function ListaEncadeada($sz) {
        $this->size = $sz;
        $this->vazios = new Pilha($this->size);
        
        for($x = 0; $x < $this->size; $x++) {
            $this->vazios->push($x);
        }
    }
    
    public function add($elem) {
        $i = $this->vazios->pop();
        
        if($i !== null) {
            $e = new ElementoLista($elem);
            $this->lista[$i] = $e;
            $this->pointer = $e;
            
            if($this->first === null) {
                $this->first = $e;
                $this->last = $e;
                $e->setNext($e);
                $e->setPrev($e);
            } else {
                $this->last->setNext($e);
                $e->setPrev($this->last);
                $this->last = $e;
            }
        } else {
            die("sem mais espaço na lista para adicionar <b>".$elem."</b>");
        }
    }
    
    public function tostring() {
        $n = $this->first;
        
        if($n !== null) {
            while($n !== $this->last) {
                echo $n->get()."<br />";
                $n = $n->getNext();
            }
            echo $this->last->get()."<br />";
        }
    }
}

$le = new ListaEncadeada(5);

$le->add("a");
$le->add("b");
$le->add("c");
$le->add("d");
$le->add("e");

$le->tostring();
?>