[자료구조] 큐

스택과 큐

스택과 큐는 데이터를 저장하는 동적인 자료구조이다. 스택은 LIFO(last in first out) 구조이고 큐는 FIFO(first in first out) 구조이다.

큐

데이터가 FIFO의 흐름을 갖고 있다. 줄 서는 것을 생각하면 된다. 먼저 온 사람이 먼저 들어간다.데이터의 삽입은 뒤(rear), 데이터의 삭제는 (front)에서 이루어진다. 종종 head, tail이라 한다. 항목이 큐에 삽입될 때는 Enqueue, 상목이 큐에서 제거될 때는 Dequene. 빈 큐에 Dequeue하려는 것은 Underflow, 가득 찬 큐에 Enqueue하려는 것은 Overflow이다.

큐의 앞부분을 front, 혹은 head라고 하고 뒷부분을 rear 혹은 tail이라 한다.

위 큐는 [15,7,6]을 갖고있는 큐에 대해서 [9, 11, 3]을 enqueue 했고 [15,7]을 dequeue한 상태이다.

큐는 공간낭비를 방지하기 위해 대개 Circular (원형) 배열을 사용한다.

Q[1, ..., n]의 큐는 n-1개의 요소를 저장할 수 있다. (하나를 쓰지 않는 이유는 Circular를 활용하기 위함이다.)

• tail은 마지막 요소의 다음, 즉 새로 들어올 자리를 표시한다.
• head는 큐의 머리, 첫 부분을 가리킨다.
• 큐 안의 항목들은 Q.head, Q.head+1, ..., Q.tail - 1 까지 있고 n 다음은 1이다. (Circular)
• 초기 시작은 Q.head = Q.tail = 1 이다.
• 만약 Q.head == Q.tail 이면 Q는 empty Queue이다.
• 만약 Q.head == Q.tail + 1 이면 Q는 이미 full 이다. 이 상태에서 Enqueue하게될 경우 overflow가 발생한다.

주요연산

EnQueue(Q, x):
	Q[Q.tail] = x
	if Q.tail == Q.length:
		Q.tail = 1
	else:
		Q.tail = Q.tail + 1

DeQueue(Q):
	x = Q[Q.head]
	if Q.head == Q.length:
		Q.head = 1
	else:
		Q.head = Q.head + 1

	return x