슈

[알고리즘] 단순 연결 리스트를 이용한 스택(stack)

/*

연결 리스트, 링크드 리스트(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
3
2
1
Pop 3
Stack contents : Top ----> Bottom
2
1
Push 4, 5, 6
Stack contents : Top ----> Bottom
6
5
4
2
1
Initialize stack
Stack contents : Top ----> Bottom
Now stack is empty,
Pop
Stack underflow.

Stack contents : Top ----> Bottom 

*/

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

프로그램

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,375
15-04-16 조회 4,528
15-04-13 조회 4,275
15-04-12 조회 3,835
15-04-10 조회 3,752
15-04-09 조회 4,043
15-04-09 조회 3,634
15-04-07 조회 3,261
15-04-06 조회 4,026
15-04-04 조회 4,677
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,695
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,605
15-03-02 조회 7,966
15-02-27 조회 3,396
15-02-27 조회 3,850
15-02-25 조회 3,922
15-02-23 조회 4,227
15-02-20 조회 3,897
15-02-19 조회 3,897
15-02-12 조회 4,197
15-02-11 조회 4,697
15-02-11 조회 4,423
15-02-11 조회 5,287
15-02-10 조회 4,678
15-02-09 조회 4,816
15-02-06 조회 3,798
15-02-04 조회 4,098
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,474
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,306
15-01-16 조회 3,885
15-01-15 조회 3,440
15-01-13 조회 6,085
15-01-12 조회 4,051
15-01-09 조회 3,782
15-01-09 조회 3,285
15-01-09 조회 3,561
15-01-08 조회 4,488
15-01-08 조회 6,762
15-01-07 조회 5,026
15-01-06 조회 3,615
15-01-06 조회 3,163
15-01-05 조회 4,085
15-01-05 조회 4,199
15-01-04 조회 6,301
15-01-03 조회 3,884
14-12-31 조회 5,661
14-12-30 조회 4,879
14-12-30 조회 3,510
14-12-30 조회 3,974
14-12-30 조회 5,492
14-12-27 조회 4,049
14-12-27 조회 4,140