[자료구조] 큐 Queue

Queue : FIFO (First In First Out)

개념 : "앞으로 들어가 뒤로 나온다."

Front(head)                   -       rear(tail)

 enqueue( put, insert)     -      dequeue(get)

 

front or head 에서 데이터의 삽입이 이루어 진다.

rear or tail 에서 데이터가 나오게 된다.

 

보통, 급하게 짜야할 경우, 배열을 이용하게 될텐데, 배열은

구조상

1

2

3

4

5

6

7

rear ( get )                                                                                                                 front(put)

0번 인덱스부터 쭉 데이터를 넣는 구조이다.

개념상 왼쪽부터 오른쪽으로 데이터가 저장되는 구조이므로, 데이터가 들어가는 오른쪽이 front,

데이터가 빠져나가게되는 쪽이 왼쪽이기 때문에, 왼쪽 부분이 rear 라고 생각하면 된다.

(위 그림에서는 front가 뒷쪽으로 가있는 모양새이고, rear가 앞에 있는 모양으로 보인다.)

헷갈리면 세로로 세워서 생각하자.

 

스택처럼 데이터를 밑에서부터 담아 간다.

 front(head) - put

7

6

5

4

3

2

1

 rear(tail) - get

 

데이터를 뺄 때는, 들어온 순으로 나가야 하기에, 밑에서 부터 데이터를 뺀다.

 

 배열로 구현 시에는

#define SIZE 100

int data[SIZE];

int rear = -1;(rear는 get될 대상을 가리키고 있어야 한다. 그러므로 기본 값은 -1, enqueue 될 때 마다, +1 )

int front = 0; (앞으로 들어갈 곳을 가리켜야 하니까, 0. enqueue 시에 + 1)

queue_init, queue_destroy, queue_enqueue, queue_dequeue , queue_peak(get될 대상이 되는 데이터를 return)

정도로 구현하면 되며, queue 안에 있을 데이터 자료구조형은 배열이든 리스트이든 입맛에 맞게 구현한다.