슈

[알고리즘] 단순 연결 리스트를 이용한 스택(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건
+
제목 글쓴이 날짜 조회
14-12-27 조회 5,061
14-12-26 조회 4,724
14-12-25 조회 3,527
14-12-24 조회 3,730
14-12-24 조회 6,171
14-12-23 조회 4,064
14-12-23 조회 4,312
14-12-20 조회 3,703
14-12-20 조회 3,424
14-12-20 조회 3,563
14-12-19 조회 3,989
14-12-18 조회 5,530
14-12-18 조회 3,825
14-12-17 조회 4,359
14-12-16 조회 3,832
14-12-16 조회 3,631
14-12-15 조회 6,943
14-12-15 조회 3,774
14-12-14 조회 3,932
14-12-13 조회 3,532
14-12-12 조회 3,895
14-12-12 조회 3,527
14-12-12 조회 3,207
14-12-11 조회 3,127
14-12-11 조회 3,709
14-12-10 조회 3,699
14-12-10 조회 3,685
14-12-10 조회 3,743
14-12-09 조회 3,314
14-12-09 조회 3,440
14-12-08 조회 6,306
14-12-08 조회 4,249
14-12-07 조회 3,033
14-12-07 조회 3,510
14-12-07 조회 3,351
14-12-05 조회 5,038
14-12-05 조회 3,290
14-12-05 조회 3,440
14-12-04 조회 3,151
14-12-03 조회 3,650
14-12-03 조회 3,310
14-12-02 조회 3,537
14-12-02 조회 4,350
14-12-02 조회 3,111
14-12-01 조회 3,101
14-12-01 조회 4,336
14-11-29 조회 3,984
14-11-28 조회 3,932
14-11-27 조회 3,312
14-11-27 조회 4,053
14-11-27 조회 3,593
14-11-26 조회 3,444
14-11-26 조회 3,743
14-11-26 조회 3,843
14-11-25 조회 3,964
14-11-25 조회 3,847
14-11-25 조회 6,747
14-11-24 조회 5,519
14-11-24 조회 3,848
14-11-21 조회 4,181
14-11-20 조회 7,920
14-11-20 조회 4,555
14-11-19 조회 3,997
14-11-18 조회 3,541
14-11-18 조회 4,163
14-11-17 조회 4,095
14-11-16 조회 3,884
14-11-13 조회 3,184
14-11-13 조회 3,485
14-11-13 조회 3,400
14-11-12 조회 3,658
14-11-12 조회 4,152
14-11-12 조회 4,400
14-11-11 조회 3,325
14-11-11 조회 4,052
14-11-09 조회 3,810
14-11-08 조회 3,625
14-11-07 조회 7,767
14-11-06 조회 7,308
14-11-06 조회 3,742
14-11-06 조회 7,232
14-11-05 조회 6,929
14-11-05 조회 7,235
14-11-05 조회 8,090
14-11-04 조회 7,759
14-11-04 조회 7,198
14-11-04 조회 3,528
14-11-03 조회 8,497
14-11-03 조회 4,308
14-10-31 조회 3,865
14-10-31 조회 5,910
14-10-30 조회 3,734
14-10-30 조회 5,807
14-10-30 조회 5,219
14-10-28 조회 4,174
14-10-27 조회 4,346
14-10-27 조회 3,709
14-10-25 조회 5,151
14-10-25 조회 3,750
14-10-25 조회 8,412