[알고리즘] 이중연결리스트를 이용한 큐(queue)

<?

/* 

큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 

먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다 

http://terms.naver.com/entry.nhn?docId=834442&cid=42344&categoryId=42344

http://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

*/

// 시작노드와 끝노드만 남기고 나머지 노드 삭제

function clear_queue() {

    global $head, $tail;

    $t = new dnode;

    $s = new dnode;

    $t = $head->next;

    while ($t != $tail) {

        $s = $t;

        $t = $t->next;

        $s = null;

    }

    $head->next = $tail;

    $tail->prev = $head;

}

// 마지막 노드 앞에 새 노드 삽입

function put($k) {

    global $head, $tail;

    $t = new dnode;

    $t->key = $k;

    $tail->prev->next = $t;

    $t->prev = $tail->prev;

    $tail->prev = $t;

    $t->next = $tail;

    return $k;

}

// 큐에 시작노드 다음 노드의 key 값 가져오기

function get() {

    global $head, $tail;

    $t = new dnode;

    $i = 0;

    $t = $head->next;

    if ($t == $tail) {

        printf('<br />    Queue underflow.');

        return -1;

    }

    $i = $t->key;

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

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

    $t = null;

    return $i;

}

// 큐에 저장된 key 값 보여주기

function print_queue() {

    global $head, $tail;

    $t = $head->next;

    printf('<br />  Queue contents : Front ----> Rear<br />');

    while ($t != $tail) {

        printf('%2d', $t->key);

        $t = $t->next;

    }

}

// 노드정의

class dnode {

    public $key = 0, 

$prev = null, 

$next = null;

} 

$head = new dnode; // 시작노드

$tail = new dnode; // 끝노드

$head->prev = $head;

$head->next = $tail;

$tail->prev = $head;

$tail->next = $tail;

printf('<br />Put 1, 2, 3, 4, 5, 6');

put(1);

put(2);

put(3);

put(4);

put(5);

put(6);

print_queue();

echo ('<br /><br />Get');

$i = get();

printf('<br />   getting value is %d', $i);

print_queue();

printf('<br /><br />Put 7, 8, 9, 1');

put(7);

put(8);

put(9);

put(1);

print_queue();

printf('<br /><br />Put 2');

put(2);

print_queue();

printf('<br /><br />Initialize queue');

clear_queue();

print_queue();

printf('<br /><br />Now queue is empty');

echo ('<br />Get');

$i = get();

printf('<br />   getting value is %d', $i);

print_queue();

?>