[자료구조] 리스트로 된 스택

main.c

#include <stdio.h>

#include "array.h"

int main(){

struct data stack;

init(&stack);

push(&stack, 1);

push(&stack, 2);

push(&stack, 3);

push(&stack, 4);

while (!empty(&stack)){

printf("%d ", pop(&stack));

}

return 0;

}

array.c (정의문)

#include <stdio.h>

#include <stdlib.h>

#include "array.h"

void init(struct data *a){

a->head = NULL;

}

int empty(struct data *a){

if (a->head == NULL){

return 1;

}

else{

return 0;

}

}

void push(struct data *a, int num){

struct data *newnode = (struct data *)malloc(sizeof(struct data));  // 노드를 새로 생성한다.

newnode->num = num;  // 새로운 노드에 받아온 값을 입력한다.

newnode->next = a->head;  // 새로운 노드는 헤더를 가리킨다. 즉 처음엔 NULL을 넣음

a->head = newnode;  // 헤더에는 새로운 노드를 넣는다.

// 중요한건 다음번 차례가 왔을 때 a->head 에는 1이 들어간 newnode1이 있다.

// 새로운 newnode2는 newnode->next를 통해 newnode1을 가리킨다.

// a->head에는 다시 newnode2를 넣고 반복한다.

// 이렇게 되면 newnode2->next는 newnode1을 가리키고 있다.

// a->head에는 newnode2가 들어가있다.

}

int pop(struct data *a){

if (empty(a)){

exit(-1);

}

int i;  // 값을 출력

struct data *del;  // 다음 노드를 가리키기 위해

i = a->head->num;  // head는 마지막 입력한 값을 가지고 있다. i에 가장 최근 입력한 값을 넣는다.

del = a->head;  // del는 해제할 노드이다.

a->head = a->head->next;  // a->head->next 의미는 a->head에는 마지막 노드가 있었다.

// 그 노드의 ->next는 그 전에 입력한 노드이다. 그걸 헤더에 넣는다는건 하나씩 옮겨가며 해제하겠다는 뜻이다.

free(del);

return i;

}

int peek(struct data *a){

if (empty(a)){

exit(-1);

}

return a->head->num;

}

array.h (선언문)

struct data{

int num;

struct data *next;

      struct data *head;

};

void init(struct data *a);

void push(struct data *a, int num);

int empty(struct data *a);

int pop(struct data *a);

int peek(struct data *a);

}

// 답 4 3 2 1

// 입력한 반대인 역순으로 출력한다.

[stack]

head = NULL    --   &malloc1  --  &malloc2 -- ...

                        [malloc1]      [malloc2]

                        num = 1        num = 2

                        next = null      next = &malloc1

         

                             l                 l

                        [newnode]     [newnode]

                         &malloc1        &malloc2

push일때

1. newnode->next = num;   // malloc1에 1을 저장하는 것

2. newnode->next = a->head // malloc1에 head의 주소였던 null을 저장

3. a->head = newnode  // stack에 &malloc1을 저장함

stack은 이동하면서 malloc에 접근하고 malloc 안에 next는 다음 순서를 가리킨다.

그러면서 num을 출력한다.

pop일때

1.  i = a->head->num;   // 거꾸로 출력해야하기 때문에 malloc2의 num 2를 가리킴

2.  del = a->head;  // a->head는 &malloc2를 del에 담는다.

3.  a->head = a->head->next;  // &malloc2 가 담겨있던 stack의 head를 &malloc1으로 교체한다.

4.  free(del); //  &malloc2를 해제한다.

5.  return i;  // malloc2에 있던 2를 보낸다.

------------------------------------------------------------------------------------------------

2017.01.03 

다시 정리한다.

#include <stdio.h>

#include <stdlib.h>

struct data{

int num;

struct data *next;

struct data *head;

};

void init(struct data *a){

a->head = NULL;

}

int empty(struct data * a){

if(a->head == NULL){

return 0;

}else{

return 1;

}

}

int pop(struct data *a){

struct data *del;

int i;

del = a->head;

i = a->head->num;

a->head = a->head->next;

free(del);

return i;

}

void push(struct data *a, int num){

struct data *newnode = (struct data *)malloc(sizeof(struct data));

newnode->num = num;

newnode->next = a->head; 

a->head = newnode; 

}

int main(){

struct data node;

init(&node);

push(&node, 1);

push(&node, 2);

push(&node, 3);

while(empty(&node)){

printf("%d ", pop(&node));

}

return 0;

}

쉽게 생각하면 처음 선언한 node란 것은 head만 쓴다.

head는 마지막 노드의 위치를 저장을 한다.

계속 생성되는 newnode는 num과 next만 쓴다.

num은 값이고 next는 head가 가리키는 위치의 바로 전 위치를 가리킨다.