[2] Queue(큐)란 무엇인가?

 Queue(큐)는 선형리스트 이다.

쉽게 비유하자면 물건을 사기위해 줄을 선다고 생각하면 쉽다.

---

 먼저 줄을 선사람은 앞으로 가게 되고, 먼저 나가게된다.

뒤늦게 줄을 선 사람은 맨 뒤로 위치하며, 앞사람이 모두 볼일이 끝난 후에야 자신도 볼일을 볼 수 있다.

 

 즉, 출구와 입구가 따로 존재한다는 것이다.

그대로 영어로 표현을 하자면

 

"First In First Out"

선 입 선 출

 

---

 실제 생활에서 큐가 사용되는 것은,

1. 줄서기

2. 티켓예매

3. 키보드작동

4. 컴퓨터 시스템

.

.

.

등이 있다.

---

실제로 큐를 구현하는데 사용되는 Main Operations(함수)은

1. Enqueue : 데이터 입력

2. Dequeue : 데이터 추출

3. Createqueue : 큐생성

4. Destroyqueue : 큐제거

가있다.

---

 자 이제 실제로 Queue(큐)는 어떻게 만들어지고, 그 자료들은 어떤식으로 저장되는지 알아보자.

우선 무든 자료는 "NODE"라는 묶음으로 저장이된다.

그림과 같이 NODE는 Data + Link 로 구성이된다.

"Link" 는 일열로 줄을 서있는 사람들이 서로 앞뒤로 손을 잡으며 "내다음 사람은 이사람이에요!"라고 알려주는 것과 같은 역할이다.

 

Queue는 이 모든 NODE들을 총괄한다고 생각하면된다.

Count : 지금 줄을 몇명이 서고있는지

Front : 지금 앞사람은 누구인지

Rear : 맨 마지막으로 들어온 사람이 누구인지

---

 실제 Queue의 구성도를 그린 그림이다.

아래의 4개의 노드들은 저장된 데이터들이다.

각각 문자열형태로 저장이 되어있고, NODE의 구성 처럼 데이터만 있는것이 아니라, 자신의 다음 노드의 손을 잡는 Link와 함께 있다.

 

 그리고 Front와 Rear 이 가르키는 것은 각각 첫번째 노드, 마지막 노드이다. 

마지막 노드인 Eat의 Link는 X표기가 되어있는데, 이것은 NULL을 의미한다.

자신의 뒤에 다음 노드가 없기 때문에, 손을 가르킬 수가 없는 것이다.

---

다음 글에선 실제 C언어로 어떻게 코딩을 하여 이 그림과 같은 자료구조를 형성할 수 있는지 알아보자.