| sitelink1 | |
|---|---|
| sitelink2 | |
| sitelink3 | |
| sitelink4 | |
| sitelink5 | |
| extra_vars6 |
http://blog.naver.com/simtwolove/30022216350
자료구조가 무엇인지는 본 블로그의 "자료구조알고리즘" 항목의
첫번째 글에 자료구조에 대한 설명이 대략 있음을 알린다.
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 선린 인터넷 고등학교
첫번째 글에 자료구조에 대한 설명이 대략 있음을 알린다.
Part5 큐 - 연결리스트로 구현한 큐
--------------------------------------
이 강의를 펴기전에, 배열로 구현한 큐, 원형큐 의 강의가 블로그에 있음을 알린다.
큐 - 연결리스트로 구현한 큐를 말 그래도 연결리스트로 구현한 큐
또는 링크드 큐. (linked queue)라고 부른다.
배열로 큐를 만들었을 때엔 불편한 점이 몇가지 있다.
당연히! 데이터 크기 문제이다.
즉, 배열의 크기보다 더 많은 양의 정보가 삽입 될 수 없다는 점(overflow)이 가장 큰 단점이다.
이러한 점을 고치기 위해 최대 크기를 잘 고려하여서 충분한 크기로 배열을 할당해야 할 필요가 있다.
또는 큐를 원형큐 로 구현하는 방법이 있었다.
또한 배열로 구현한 큐는 연속적인 메모리 공간을 차지하기 때문에, 삽입 및 삭제가 번거로웠다.
그래서 배열대신 연결리스트로 큐를 구현하면 이런 불편함을 해결할 수 있다.
먼저 소스를 보인다.
//시작--------------------이 줄은 소스에 포함되지 않습니다.
·미리보기 | 소스복사·
- #include<stdio.h>
- #include<malloc.h>
- struct aa
- {
- int data;
- struct aa *ptr;
- };
- struct aa *head, *tail;
- void put(int x)
- {
- struct aa *New, *temp;
- temp = head;
- New = (struct aa *)malloc(sizeof(struct aa));
- New->data = x;
- while( temp->ptr != tail ) temp = temp->ptr;
- New->ptr = tail;
- temp->ptr = New;
- }
- void init_queue()
- {
- head = (struct aa *)malloc(sizeof(struct aa));
- tail = (struct aa *)malloc(sizeof(struct aa));
- head->ptr = tail;
- }
- void print_queue()
- {
- struct aa *Now;
- for (Now=head->ptr;Now!=tail;Now=Now->ptr)
- {
- printf("%dt",Now->data);
- }
- printf("n");
- }
- void get()
- {
- struct aa *del;
- if(head->ptr == tail)
- {
- printf("queue underflown");
- return;
- }
- del = head->ptr;
- head->ptr = del->ptr;
- free(del);
- }
- void main()
- {
- init_queue();
- put(1);
- put(2);
- put(3);
- print_queue();
- get();
- get();
- print_queue();
- get();
- get();
- }
//끝--------------------이 줄은 소스에 포함되지 않습니다.
-- 실행결과 --
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 선린 인터넷 고등학교
