[Algorithms] 배열을 이용한 큐(Queue)

오늘은 큐(Queue)를 구현해보자

큐는 선입선출 FIFO(First In First Out)로

들어온 순서대로 나가는 형태의 자료구조다

큐와 같은 형태를 일상에서 찾자면

은행 창구, 식당 등에서 이용하는 대기번호가 있다

대기번호를 먼저 뽑은 사람이

해당 서비스를 먼저 이용하는 것이다

고딩 점심시간 조금이라도

빨리 먹기 위해 냅다 뛰는 이유도 배식 받는 것이 큐와 같아서-_-

어찌되었든 큐를 구현해보자

크기가 5인 큐

위의 코드는 크기가 5인 큐를 구현한 것이다

이 프로그램을 돌려보면 잘 돌아간다-_-

사실 enqueue() 함수룰 5번 호출 후에

dequeue() 함수를 1번 호출하고

다시 enqueue() 함수를 호출하면 에러("index out of bound exception")가 발생해야하지만

C언어가 index검사를 엄격히 수행하지 않아 발생하지 않는다

하지만 이 프로그램은 이미 사용한 배열의 인덱스를

다시 재사용 하지 못하고 배열의 크기를 넘어서면 더 이상 동작할 수 없다

이런 문제를 해결하기 위한 방법으로 원형 큐가 있다

원형큐

일반 큐(Queue)의 차이점은 배열의 인덱스를

다시 원점으로 돌리는 것이다 

tail = (tail+1)%QUEUE_CAPACITY

head = (head+1)%QUEUE_CAPACITY

이것으로 일반 큐(QUEUE)의 문제점은 해결이 되었다

하지만 여전히 문제가 남아있다

이 프로그램은 초기 배열의 크기에 따라 큐에 들어갈 값이 제한된다

완벽히 고정된 크기 만큼만 데이터가 들어온다는 가정이 없다면 비추-_-

이를 해결하기 위해서는 연결리스트(Linked List)가 있다

연결리스트를 이용한 큐 구현은 다음 시간에 하도록 하겠다