Language 자료구조 Part6. "연결리스트로 구현한 스택"의 모든 것

자료구조가 무엇인지는 본 블로그의 "자료구조알고리즘" 항목의
 
첫번째 글에 자료구조에 대한 설명이 대략 있음을 알린다.
 
 
Part6 스택 - 연결리스트로 구현한 스택
--------------------------------------
이 강의를 펴기전에, 배열로 구현한 스택 및 연결리스트의 강의가 본 블로그에 있음을 알린다.
 
연결리스트로 구현한 스택. 또는 링크드 스택 (Linkedstack) 또는 링크드리스트스택(Linkedliststack)
 
이라고 부르는데, 뭐 사람마다 취향이 다르니. 정도로 생각해 두면 좋을 것 같다.
 
기존의 배열로 구현한 스택 + 연결리스트 기법 => 링크드 스택 라고 한마디로 할 수 있다.
 
그럼 배열로 구현한 스택과 연결리스트기법을 추가한 스택은 어떠한 차이점이 있을까?
 
연결리스트는 먼저 논리상의 오버플로우가 없다.
 
즉, 자료를 무한대로 삽입, 출력이 가능하단 소리이다!
(말이 무한이지 컴퓨터상의 메모리의 한계까지. 라고 해야 정확할 것 같다.)
 
이 것이 연결리스트를 쓰는 가장 큰 매리트라고 생각된다.
 
단, 언더플로우는 배열과 마찬가지로 있다.
 
 
또 다른 큰 매리트는 삽입, 출력이 배열보다 간편하다.
 
배열의 경우

 
하지만 연결리스트는

로 간단히 삽입이 가능하다.
(마찬가지로 출력도 배열보다 연결리스트가 간단하다)
 
여기까진 연결리스트의 장점이었다.
 
그럼 스택을 왜 연결리스트로 구현해야 하는가?
->큰 프로젝트에서 대량의 용량으로 구현한 스택을 필요로 하기 때문에.
->push나 pop이 편하기 때문에. (입출력이 편하기 때문에.)
 
자, 이쯤에서 소스를 보인다.
//시작-----------------------이 줄은 소스에 포함되지 않습니다.

·미리보기 | 소스복사·

1. #include<stdio.h>   
2. #include<malloc.h>   
3. struct aa   
4. {   
5.  int data;   
6.  struct aa *ptr;   
7. };   
8. struct aa *head, *tail;   
9. void push(int x)   
10. {   
11.  struct aa *New, *temp;   
12.  temp = head->ptr;   
13.  New = (struct aa *)malloc(sizeof(struct aa));   
14.  New->data = x;   
15.  New->ptr = temp;   
16.     head->ptr = New;   
17. }   
18. void init_queue()   
19. {   
20.  head = (struct aa *)malloc(sizeof(struct aa));   
21.  tail = (struct aa *)malloc(sizeof(struct aa));   
22.  head->ptr = tail;   
23. }   
24. void print_stack()   
25. {   
26.  struct aa *Now;   
27.  for (Now=head->ptr;Now!=tail;Now=Now->ptr)   
28.  {   
29.   printf("%dt",Now->data);   
30.     }   
31.  printf("n");   
32. }   
33. void pop()   
34. {   
35.     struct aa *del;   
36.  if(head->ptr == tail)   
37.  {   
38.   printf("stack underflown");   
39.   return;   
40.  }   
41.  del = head->ptr;   
42.  head->ptr = del->ptr;   
43.  free(del);   
44. }   
45. void main()   
46. {   
47.  init_queue();   
48.     
49.  push(1);   
50.  push(2);   
51.  push(3);   
52.  print_stack();   
53.  pop();   
54.  push(4);   
55.  push(5);   
56.  print_stack();   
57.  pop();   
58.  pop();   
59.  pop();   
60.  pop();   
61.  print_stack();   
62.  pop();   
63. }  

//끝------------------------이 줄은 소스에 포함되지 않습니다.
전에 공부했던 링크드큐(Linked queue) 와 상당히 비슷한 구조를 보인다.
 
큐와 스택의 차이점은 냉정하게 딱 잘라 말하면
 
앞부터 빼 내냐, 뒤부터 빼 내냐의 차이점이기때문에 그 부분의 소스만 약간 변했을 뿐이다.
 

 
(*그림이 잘 보이지 않으니 클릭해서 보세요*)
 
이 강의 전의 링크트리스트나 링크드큐의 강의를 보았다면
 
딱 보고도 한눈에 그림이 이해가 가리라 믿는다.
 
head는 top노드를 가리키며 top노드는 아래의 노드를, 아래의 노드는 그 아래의 노드를 차례로 가리킨다.
 
주의 할 점은, 스택은 꺼내는 순서가 위부터 아래 이므로
 
print_stack() 함수에서도 위부터 아래로 출력해야 한다는 점이다.
(head부터 tail 쪽으로)
 
---------------------------------------------
push(int number) 함수는 number를 저장하는 새로운 노드를 만들며
 
head가 새로만든 노드를, 새로만든 노드는 원래 head가 가리키던 노드를 가리키게 한다.
(원래 head가 가리키던 노드를 temp라고 임시저장 해 두었다.
즉, 새로 만든 노드는 temp를 가리키게 한다.)
 
pop() 함수는 head가 가리키고 있는 노드를 삭제한다.
(이 소스에서는 삭제를 시키지만, 원래 자료구조의 의미가 자료를 임시로 저장 해 두었다가
차례로 빼 오면서 써먹는 것 이기 때문에 출력하는 것이 정석이다.)
 
삭제 할 노드는 del이라 해 두고
head는 del이 가리키던 것 즉, del의 다음 것을 가리키게 하고
del 을 free() 한다. 즉, 메모리 할당을 해제한다.
 
init() 함수는 큐와 마찬가지로 head와 tail을 할당하고 head가 tail을 가리키게 한다.
 
print_stack() 함수는 현재 스택안의 내용을 출력 해 낸다.
---------------------------------------------
 
강의의 순서를 차례로 밟아 왔다면. 또는 연결리스트나 스택에 대해 약간이라도 지식이 있다면
 
강의를 보지 않고서도 딱! 감이 오는 것이 연결리스트로 구현한 스택 이다.
 
즉, 그만큼 써먹기 쉬운놈인것은 분명하며, 구현이 쉬운녀석이기도 하므로 잘 공부 해 두자.
 
----------------------------------------------
written by 선린 인터넷 고등학교 20420 전호근