큐 (Queue)

큐

• 한쪽 끝(rear)에서는 삽입 연산만 이루어지며 다른 한쪽 끝(front)에서는 삭제 연산만 이루어지는 유한 순서 리스트
• 먼저 삽입된 item이 먼저 삭제가 이루어짐 (FIFO, First In First Out)

큐의 표현

1. 순차 표현

• 1차원 배열 이용

• front, rear를 -1로 초기화 하여 큐가 empty임을 표시 (front == rear일 때 큐는 공백)

• rear에서 삽입되므로 rear가 점차 증가하여 rear == n-1인 경우 큐는 full

• front에서 삭제가 일어났다면 그 만큼 공간이 비어있음. 따라서 큐에 원소가 꽉차있지 않아도 full

• 따라서 full이 되었을 때는 첫 원소 위치를 큐의 0번 인덱스부터 위치되게 하고 rear의 위치도 다시 계산

• 큐 원소 이동에 따른 지연시간 발생

 

• 원형큐 (해결책)

• 원소의 이동없이 큐 구현 가능

• empty: front, rear를 0으로 초기화 front == rear는 큐가 empty

• enqueue: 우선 full인지 확인 후 full 상태가 아니라면 rear를 1 증가 시킨 후 그 자리에 item 삽입

• full: rear를 증가시켰을 때 front와 같게 되면 full 상태

• dequeue: 우선 큐가 empty인지 확인 후 empty 상태가 아니라면 front를 1 증가 시킨 후 그 자리의 item 삭제

 

2. 연결 표현

• 연결 표현 (Linked List)을 이용하면 원소의 삽입과 삭제 시 원소들을 이동시킬 필요 없음

• empty: front, rear가 아무런 노드를 가리키지 않음

• enqueue, full: 삽입 시 순차표현과 달리 full 상태인지 확인할 필요 없음

• dequeue: 삭제 시 큐가 empty 상태인지 확인. front를 이용해 마지막 노드를 제거할 때 rear역시 null 상태로 변경

 

• 다음 노드를 가리키는 링크필드에 대한 추가적인 메모리 사용 염두해야함