[알고리즘] 단순 연결 리스트를 이용한 스택(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 

*/

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

프로그램

+
제목 글쓴이 날짜 조회
11년 전 조회 2,144
11년 전 조회 2,367
11년 전 조회 773
11년 전 조회 1,645
11년 전 조회 1,168
11년 전 조회 3,775
11년 전 조회 1,576
11년 전 조회 1,561
11년 전 조회 1,726
11년 전 조회 3,819
11년 전 조회 3,786
11년 전 조회 3,577
11년 전 조회 1,257
11년 전 조회 3,616
11년 전 조회 2,835
11년 전 조회 3,364
11년 전 조회 892
11년 전 조회 2,646
11년 전 조회 2,617
11년 전 조회 2,690
11년 전 조회 1,695
11년 전 조회 2,163
11년 전 조회 1,483
11년 전 조회 1,271
11년 전 조회 1,898
11년 전 조회 1,198
11년 전 조회 4,067
11년 전 조회 3,854
11년 전 조회 1,486
11년 전 조회 2,725
11년 전 조회 1,159
11년 전 조회 1,948
11년 전 조회 3,551
11년 전 조회 3,852
11년 전 조회 4,781
11년 전 조회 1,179
11년 전 조회 1,717
11년 전 조회 3,124
11년 전 조회 1,329
11년 전 조회 1,329
11년 전 조회 1,897
11년 전 조회 1,206
11년 전 조회 2,453
11년 전 조회 1,955
11년 전 조회 4,025
11년 전 조회 2,477
11년 전 조회 4,745
11년 전 조회 1,541
11년 전 조회 1,392
11년 전 조회 2,032
11년 전 조회 1,998
11년 전 조회 1,582
11년 전 조회 1,208
11년 전 조회 1,854
11년 전 조회 1,246
11년 전 조회 1,344
11년 전 조회 1,553
11년 전 조회 1,366
11년 전 조회 1,108
11년 전 조회 2,302
11년 전 조회 2,116
11년 전 조회 3,296
11년 전 조회 1,265
11년 전 조회 1,027
11년 전 조회 1,116
11년 전 조회 2,993
11년 전 조회 1,237
11년 전 조회 1,454
11년 전 조회 982
11년 전 조회 1,746
11년 전 조회 1,742
11년 전 조회 1,156
11년 전 조회 1,337
11년 전 조회 1,013
11년 전 조회 976
11년 전 조회 1,792
11년 전 조회 1,128
11년 전 조회 1,035
11년 전 조회 1,157
11년 전 조회 1,281
11년 전 조회 989
11년 전 조회 1,027
11년 전 조회 1,472
11년 전 조회 1,082
11년 전 조회 1,497
11년 전 조회 1,081
11년 전 조회 1,161
11년 전 조회 1,259
11년 전 조회 1,001
11년 전 조회 1,029
11년 전 조회 1,252
11년 전 조회 2,160
11년 전 조회 1,035
11년 전 조회 1,041
11년 전 조회 977
11년 전 조회 1,414
11년 전 조회 1,048
11년 전 조회 976
11년 전 조회 1,271
11년 전 조회 1,626