[자료구조] C - 큐, Queue, array queue, linkedlist queue

큐는 가장 많이 봤을 법한 구조입니다. 선입선출식이죠

(FIFO : First In, First Out)

편의점에서 유통기한이 빠른 우유부터 내놓고 파는 것처럼 먼저 들어온 데이터를 먼저 내보내는 형식의 자료구조 입니다.

스택과 큐는 서로 반대되는 개념이라고 생각하시면 좋겠네요

간단한 구조입니다. 쉽습니다.

그럼 이것을 어떻게 구현해야할까요?

1..배열 큐( Array queue)

스택과는 달리 가리키는 포인터가 2개가 필요합니다.

큐는 앞뒤 위치를 파악할 수 있습니다.

front 와 rear를 가리키고 

데이터가 추가될 떄 마다 rear가 증가하고(위에 쌓이니까)

데이터가 추출될 때 마다 front가 증가합니다.(먼저 들어온 순서대로 빠지니까)

이 선형 배열에서는 결국에는 끝이 정해져 있기 때문에 한줄 다 쓰고 나면 재활용이 불가능하다는 단점이 가장 큽니다.

하지만 나머지 연산자를 이용하면 이 배열도 순환이 가능하게 됩니다. 순환이 가능하도록 하면 원형 큐라고 지칭합니다.

코드 확인하기!!

https://github.com/geusan/datastructure/blob/master/c_language/03_1_array_queue.c

2.원형큐(Circular Array queue)

가득 차면 못 넣게 되고 (rear = front-1)

한자리가 비어있는데 배열 사이즈를 벗어 났으면 나머지 연산자(%) 를 이용해서 순환이 가능하도록 만들 수 있습니다.

배열을 원형이라고 생각하고 순환시킨다고 해서 원형 큐라고 부릅니다.

선형 배열의 큐와 작업은 똑같은데 나머지 연산자만 추가하면 이게 가능해진다는게 좋습니다.

코드확인하기!!

https://github.com/geusan/datastructure/blob/master/c_language/03_2_array_circle_queue.c

3.링크드리스트 큐(LInkedList queue)

링크드 리스트 큐는 스택처럼 맨뒤에 노드를 추가해주고

pop을 할때는 앞에 있는 노드를 삭제시켜주면 완성됩니다.

코드 확인하기!

https://github.com/geusan/datastructure/blob/master/c_language/03_3_linkedlist_queue.c

간단한 큐입니다. 

스택과 큐는 자료구조에서 기본중의 기본이구요

큐는 우선순위 큐라는 것으로 더 확장 시킬 수 있는데 이건 좀 나중에 나오니 천천히 공부하시면 되겠습니다.