슈

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

· 2014-10-04 (토) 14:41:39 · 5016

<?

/* 

큐(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();

?> 

댓글을 작성하시려면 로그인이 필요합니다.

프로그램

8,187건
+
제목 글쓴이 날짜 조회
15-05-06 조회 3,642
15-04-30 조회 3,887
15-04-30 조회 5,631
15-04-28 조회 4,055
15-04-28 조회 3,374
15-04-16 조회 4,528
15-04-13 조회 4,275
15-04-12 조회 3,835
15-04-10 조회 3,750
15-04-09 조회 4,043
15-04-09 조회 3,634
15-04-07 조회 3,261
15-04-06 조회 4,026
15-04-04 조회 4,676
15-04-04 조회 4,188
15-04-03 조회 4,352
15-04-02 조회 4,862
15-04-01 조회 6,030
15-04-01 조회 3,526
15-03-30 조회 3,398
15-03-30 조회 4,043
15-03-28 조회 4,691
15-03-27 조회 3,719
15-03-26 조회 3,441
15-03-24 조회 3,527
15-03-23 조회 3,593
15-03-23 조회 3,911
15-03-20 조회 4,030
15-03-20 조회 4,795
15-03-18 조회 3,397
15-03-18 조회 3,604
15-03-02 조회 7,966
15-02-27 조회 3,396
15-02-27 조회 3,850
15-02-25 조회 3,922
15-02-23 조회 4,225
15-02-20 조회 3,897
15-02-19 조회 3,897
15-02-12 조회 4,197
15-02-11 조회 4,696
15-02-11 조회 4,420
15-02-11 조회 5,287
15-02-10 조회 4,678
15-02-09 조회 4,816
15-02-06 조회 3,798
15-02-04 조회 4,097
15-02-04 조회 3,871
15-02-04 조회 3,561
15-02-03 조회 3,408
15-02-02 조회 3,540
15-02-02 조회 4,474
15-01-31 조회 3,566
15-01-31 조회 4,654
15-01-30 조회 6,417
15-01-30 조회 4,005
15-01-30 조회 3,961
15-01-29 조회 3,880
15-01-29 조회 3,775
15-01-29 조회 3,450
15-01-29 조회 4,732
15-01-28 조회 3,339
15-01-28 조회 3,776
15-01-26 조회 4,051
15-01-26 조회 3,990
15-01-24 조회 5,486
15-01-23 조회 3,762
15-01-23 조회 4,298
15-01-22 조회 3,604
15-01-22 조회 3,579
15-01-22 조회 4,472
15-01-20 조회 3,891
15-01-19 조회 3,698
15-01-18 조회 4,474
15-01-17 조회 3,410
15-01-16 조회 4,177
15-01-16 조회 4,060
15-01-16 조회 7,305
15-01-16 조회 3,884
15-01-15 조회 3,439
15-01-13 조회 6,084
15-01-12 조회 4,050
15-01-09 조회 3,781
15-01-09 조회 3,284
15-01-09 조회 3,559
15-01-08 조회 4,487
15-01-08 조회 6,761
15-01-07 조회 5,025
15-01-06 조회 3,614
15-01-06 조회 3,162
15-01-05 조회 4,085
15-01-05 조회 4,198
15-01-04 조회 6,300
15-01-03 조회 3,883
14-12-31 조회 5,660
14-12-30 조회 4,878
14-12-30 조회 3,509
14-12-30 조회 3,973
14-12-30 조회 5,491
14-12-27 조회 4,048
14-12-27 조회 4,139