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 선린 인터넷 고등학교
댓글 0
번호 | 제목 | 글쓴이 | 날짜 | 조회 수 |
---|---|---|---|---|
공지 | 2023 Software Development Trend 정리 | 황제낙엽 | 2024.01.19 | 1 |
» | 자료구조 Part5. "연결리스트로 구현한 큐"의 모든 것 | 황제낙엽 | 2007.11.24 | 28 |
47 | 지수(과학적 표기법, "E") 서식 지정자 (2) | 황제낙엽 | 2021.07.06 | 24 |
46 | [SDC22 키노트 요약정리] 더 쉽게, 끊김 없이 매끄럽게! ‘캄 테크’ 향해 진화하는 미래의 집 | 황제낙엽 | 2022.12.24 | 23 |
45 | 자료구조-쉬어가기. (스택과 큐가 쓰이는 기본적인 예) | 황제낙엽 | 2007.11.24 | 23 |
44 | 소프트웨어 테스트 관련 | 황제낙엽 | 2020.05.04 | 22 |
43 | 자료구조 Part7. "트리" - 기본편 | 황제낙엽 | 2007.11.24 | 22 |
42 | 식품(상품) 바코드를 조회하여 제품 정보 획득하기 | 황제낙엽 | 2023.08.07 | 21 |
41 | REST API 제대로 알고 사용하기 | 황제낙엽 | 2021.06.02 | 21 |
40 | 컴퓨터와 인간의 대화[10]-byte 1 | 황제낙엽 | 2016.04.22 | 21 |
39 | WYSIWYG | 황제낙엽 | 2013.02.23 | 19 |
38 | 자료구조 강의 사이트 | 황제낙엽 | 2007.11.24 | 19 |
37 | 이미지 인증을 통한 스팸글 방지 | 황제낙엽 | 2006.01.06 | 19 |
36 | HTTP URL 상의 데이터 가져오기 (HTTP 프로토콜에 대하여) | 황제낙엽 | 2006.12.29 | 19 |
35 | 간단한 HTML 리다이렉트 페이지 | 황제낙엽 | 2006.12.28 | 19 |
34 | 페이지를 새로 고칠 수 없다는 Alert 창에 대한 이야기 | 황제낙엽 | 2005.10.21 | 19 |
33 | i18n (internationalization) | 황제낙엽 | 2020.09.19 | 18 |
32 | 자료구조 Part2. "큐"의 모든 것. | 황제낙엽 | 2007.11.24 | 18 |
31 | 웹 프로젝트 개발 환경 갖추기 | 황제낙엽 | 2006.09.21 | 17 |
30 | VSSH 프레임웍 패키지 | 황제낙엽 | 2006.10.04 | 17 |
29 | 사이트 유지보수 및 개선방법 | 황제낙엽 | 2005.11.11 | 17 |