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

자료구조가 무엇인지는 본 블로그의 "자료구조알고리즘" 항목의
 
첫번째 글에 자료구조에 대한 설명이 대략 있음을 알린다.
 
 
Part5 큐 - 연결리스트로 구현한 큐
--------------------------------------
이 강의를 펴기전에, 배열로 구현한 큐, 원형큐 의 강의가 블로그에 있음을 알린다.
 
큐 - 연결리스트로 구현한 큐를 말 그래도 연결리스트로 구현한 큐
 
또는 링크드 큐. (linked queue)라고 부른다.
 
배열로 큐를 만들었을 때엔 불편한 점이 몇가지 있다.
 
당연히! 데이터 크기 문제이다.
 
즉, 배열의 크기보다 더 많은 양의 정보가 삽입 될 수 없다는 점(overflow)이 가장 큰 단점이다.
 
이러한 점을 고치기 위해 최대 크기를 잘 고려하여서 충분한 크기로 배열을 할당해야 할 필요가 있다.
 
또는 큐를 원형큐 로 구현하는 방법이 있었다.
 
또한 배열로 구현한 큐는 연속적인 메모리 공간을 차지하기 때문에, 삽입 및 삭제가 번거로웠다.
 
그래서 배열대신 연결리스트로 큐를 구현하면 이런 불편함을 해결할 수 있다.
 
먼저 소스를 보인다.
 
//시작--------------------이 줄은 소스에 포함되지 않습니다.
 
 
//끝--------------------이 줄은 소스에 포함되지 않습니다.
-- 실행결과 --
1 2 3
3
queue underflow
------------
 
자, 소스를 분석해보자.
 
1. init_queue()
init_queue는 링크드리스트에서 필수인 head와 tail 을 할당했고,
 
head는 tail을 가리키게 했다.
 
2. put(int x)
put은 연결리스트를 구현했을 때와 마찬가지로
 
메모리를 하나 할당하고, 그 안에 데이터 x를 넣으며,
 
tail의 바로 전 곳 까지 가다가 그 곳에 도착하게 되서야 할당한 메모리를 그 곳에 잇는다
(tail의 바로전 노드는 할당한 노드를 메모리를 가리키고, 할당한 메모리는 tail을 가리킨다)
 
3. get()
get함수는 head의 바로 뒤 의 노드를 삭제한다.
 
head가 tail을 가리킬때, 즉, head와 tail이외의 노드가 없을 때 언더플로우 메세지를 띄운다.
 
head의 바로 뒤 노드를 del이라 임시 지칭했으며 head는 del의 바로 뒤 노드를 가리키며,
 
del을 free(할당 헤제) 한다.
 
4. print_queue()
현재 큐의 내용을 출력한다.
 
--------------------
배열로 구현한 큐와 마찬가지로 언더플로우는 있지만,
 
연결리스트로 구현한 큐는 오버플로우(더이상 자료를 입력할 수 없는 상태)가 없다는 것이 큰 특징이다.
 
하지만, 어쩌면 이것이 때론 더 위험할 수 있다.
 
프로그램에 논리적인 에러가 있을 경우 시스템의 전 메모리를 다 까먹을 때까지 할당을 해 댈 것이므로 차라리 오버플로우가 발생하는 것이 더 나을지도 모른다.
 
사실 큐를 사용하는 실제 예도 무한대의 큐를 요구하지는 않기 때문에 때로는 오버플로우가 필요하기도 하다.
 
또다른 큰 장점으론, 삽입, 삭제가 번거롭지 않다는 점이며, 다만 속도가 조금 느려지긴 했다.
 
연결 리스트는 데이터를 삽입할 때 노드를 동적으로 할당해서 뒤에 덧붙일 수 있으므로 이론적으로 메모리 한계까지 큐의 크기를 늘릴 수 있다.
 
따라서 큐가 가득차는 오버플로우가 발생하지 않으며 처음부터 큐의 크기를 미리 정할 필요도 없다.
 
또한 노드가 메모리의 임의 위치에 생성되었다가도 언제든지 파괴될 수 있으므로 원형으로 만들지 않아도 상관없다.
 
위의 소스의 구조는 아래 그림과 같다.

이것은 필자가 생각한 가장 이상적인 연결리스트로 구현한 큐 이기 때문에,
 
자기의 생각과 이 소스의 구조가 다를 수 있는 것은 당연한 것이다.
 
------------------------
written by 호근
20420 선린 인터넷 고등학교