/*

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 

데이터를 저장하는 자료 구조이다. 

이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 

노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 

연결 리스트의 종류로는 단순 연결 리스트, 이중 연결 리스트 등이 있다. 

*/

// 단순 연결 리스트를 이용한 스택의 구현

class Node {

    public $key;

    public $next = Node;

} 

$head = new Node;

$tail = new Node;

function init_stack() {

    Global $head, $tail;

    $head->next = $tail;

    $tail->next = $tail;

}

function clear_stack() {

    Global $head, $tail;

    $t = Node;

    $s = Node;

    $t = $head->next;

    while ($t != $tail) {

        $s = $t;

        $t = $t->next;

        $s = null;

    }

    $head->next = $tail;

}

function push($k) {

    Global $head, $tail;

    $t = new Node;

    if ($t == NULL) {

        println("   Out of memory...");        

    }

    $t->key = $k;

    $t->next = $head->next;

    $head->next = $t;

}

function pop() {

    Global $head, $tail;

    $t = new Node;

    if ($head->next == $tail)  /* if empty */ {

        println("  Stack underflow.");

        return -1;

    }

    $t = $head->next;

    $i = $t->key;

    $head->next = $t->next;

    $t = null;

    return $i;

}

function print_stack() {

    Global $head, $tail;

    $t = new Node;

    $t = $head->next;

    println("  Stack contents : Top ----> Bottom");

    while ($t != $tail) {

        println($t->key);

        $t = $t->next;

    }

}

init_stack();

println('Push 1, 2, 3');

push(1);

push(2);

push(3);

print_stack();

$i = pop();

println('Pop '.$i);

print_stack();

println('Push 4, 5, 6');

push(4);

push(5);

push(6);

print_stack();

println('Initialize stack');

clear_stack();

print_stack();

println('Now stack is empty,');

println('Pop');

$i = pop();

print_stack();

function println($str=''){

    echo $str.'<br />';

} 

/* output

Push 1, 2, 3

Stack contents : Top ----> Bottom 

*/