이중 연결 리스트를 이용한 큐의 구현

소개글

컴파일/실행환경 및 사용방법
MS 비주얼C/C++ 6.0

목차

1장. 정 의
1.1. 이중 연결 리스트
1.2. 큐
1.3. 이중 연결 리스트와 큐

2장. 톨게이트 차량 통과 구현
2.1. 차량 통과 ADT
2.2. 코딩 및 해석

3장. 결과 및 고찰
3.1. 결론
3.2. 고찰

4장. 참고문헌

본문내용

제 1 장. 정 의
이중 연결 리스트는 단순 연결 리스트의 단점을 보완한다. 단순 연결 리스트 에서 어떤 노드에서 후속 노드를 찾기는 쉽지만, 선행노드는 찾기가 힘들다. 즉 처음부터(헤드 포인터) 다시 탐색해야 한다. 특정 노드에서 양방향으로 자유롭게 움직일 필요가 있다면 단순 연결 리스트 구조는 부적합하다. 그러하여 이중연결 리스트를 사용함으로써 이러한 문제점을 보완한다.
(중 략)

1.3. 이중 연결 리스트와 큐

단지 연결 리스트들이 이중으로 연결 되었을 뿐이고, 이를 큐 형식으로 구현 한 것이다.
(p = 이전 링크, A,B,C = 데이터, n = 다음링크)
삽입은 일단 동적 메모리를 할당을 받은 후, 데이터가 비어 있을 경우, 어떤 노드가 있을 경우로 2가지의 경우로 나누어진다.
1) 노드가 없을 경우
front와 rear에 삽입할 노드를 가리킨다. 그리고 노드의 데이터를 저장하고, 다음과 이전을 가리키는 노드는 없으므로 둘 다 NULL으로 설정해준다.
2) 어떠한 노드가 있을 경우
rear의 다음 링크를 삽입할 노드를 가리키고, 삽입한 노드를 rear로 설정한다. 그리고 노드의 데이터를 저장하고, 다음을 가리키는 링크의 값은 NULL으로 설정해준다.

참고 자료

1. Data Structures in C (C언어로 쉽게 풀어쓴 자료구조), 생능출판사, 천인국저, 2006년
137쪽 - 이중 연결 리스트
212쪽 - 큐
221쪽 - 연결 리스트로 구현된 큐 (참고)

2. http://blog.naver.com/hpmovie?Redirect=Log&logNo=120058305204
소스 코딩 참조