[자료구조] Queue

Queue란?

Queue는 선형구조를 가진 자료구조로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말합니다.

 

나중에 집어 넣은 데이터가 먼저 나오는 stack과는 반대되는 개념입니다.

 

보통 프린터의 출력 처리나, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야할 필요가 있는 상황에 사용됩니다.

 

Queue의 구현

Queue의 구현해야할 기능은 다음과 같습니다.

• create : Queue를 생성하는 함수입니다. front로 가장 앞의 인덱스를 가르키고 rear로 가장 끝의 인덱스를 가르킵니다.
• enQueue : 큐에 Element(요소)를 추가합니다.
• deQueue : 큐에서 맨앞의 요소를 빼냅니다.
• peek : 큐에서 맨앞의 요소를 가져옵니다. (큐에서 제거하지는 않음)
• isFull : 큐가 가득찼는지 확인합니다
• isEmpty : 큐가 비어있는지 확인합니다.
• delete : 큐를 삭제합니다.

위의 기능을 포함먼저 배열로 구현한 선형큐입니다.

https://github.com/zxcv9203/dataStructure/blob/master/chap04/arrayqueue.c

GitHub - zxcv9203/dataStructure

제가 구현한 선형큐의 경우 front와 rear가 값을 넣을때마다 정방향으로만 증가하기 때문에 삽입과 삭제를 반복하다보면 큐에 비어있는 공간이 존재하지만 다 찼다고 판단하는 문제점이 있습니다.

 

그래서 선형큐의 문제점을 해결하기 위해 원형큐가 등장하였고 원형큐는 마지막 인덱스에 도달하면 처음 인덱스로 돌아가도록 구현되어 있습니다.

 

다음은 배열로 구현한 원형큐입니다.

https://github.com/zxcv9203/dataStructure/tree/master/chap04

GitHub - zxcv9203/dataStructure