큐(Queue)

큐(Queue)

큐(Queue): 리스트의 한 쪽 끝에서는 삽입만, 나머지 한 쪽에서는 삭제만 하는 유한 순서 리스트.

FIFO: First-In-First-Out 구조로 되어있다.

빨대로 버블티를 먹는다고 해보자. 먼저 빨대 속으로 들어온 버블이 입 속으로 들어간다.

빨대에 먼저 들어온 버블이 먼저 나가는 구조가 Queue다.

• Front: 제일 먼저 들어온 원소. 삭제될때 여기부터 삭제된다.

• Rear: 제일 최근에 들어온 원소. 이쪽방향으로 삽입된다.

• enQueue: 인큐. 삽입. rear에서 발생

• deQueue: 디큐. 삭제. Front에서 발생

빈 큐에서는 (큐 막 생성하고나서 아무것도 안 넣었을 때) ; front, rear의 index를 -1로 둔다.

원소 하나하나 넣어가면서 rear는 증가, front는 변화없음.

원소 하나하나 삭제하면서 front는 증가, rear는 변화없음.

큐를 구현할때는 배열, 리스트 둘 다 사용할 수 있다.

원형 큐

배열을 이용하여 큐를 구현할 때, 아래와 같은 경우는 큐를 포화 상태로 인식한다.

index[0]	index[1]	index[2]	index[3]
비어있음	비어있음	비어있음	차있음
		front	rear

빈 자리가 있는데도 큐가 다 찼다고 인식한다. 이를 해결하기 위해서는 큐에 저장된 원소들을 앞으로 옮겨야 한다.

index[0]	index[1]	index[2]	index[3]
차있음	비어있음	비어있음	비어있음
rear

front는 -1로. 바깥에.

* 큐를 짜는 방법도 여러가지가 있는데 여기서는 front는 첫번째 원소가 들은 인덱스의 바로 앞 인덱스, rear는 마지막 원소가 들은 index라고 하자. front==rear면 빈 큐.

어쨌든, 이렇게 원소들을 앞으로 옮기는 방법은 오버헤드가 커서 효율성이 떨어진다. 그래서 이 방법 대신 원형 큐(Circular Queue)를 사용한다.

원형 큐

원형 큐에서는 초기 공백 상태일때 front와 rear = 0 으로 둔다. 나중에도 공백 상태일때는 front==rear다.

그리고 공백과 포화를 구분하기 위해 자리를 꽉 채우지 않고 하나를 항상 비워둔다. 꽉 채워서 쓴다면 공백일때도 front==rear고, 포화일때도 front==rear니까 구분할 수가 없다.. 비워두는 자리는 여러 방법이 있겠지만, 여기서는 front가 가리키는 곳을 빈칸으로 두겠다. 앞의 선형큐처럼.

원형큐는 배열의 인덱스가 n-1다음에 다시 0이 된다. 그래서 어떤 인덱스를 사용할지는 mod를 이용하여 정한다.

	삽입 위치	삭제 위치
선형 큐	rear = rear +1	front = front +1
원형 큐	rear = (rear+1) mod n	front = (front +1) mod n

* mod n: n으로 나눈 나머지. 코딩할때 쓰는 나머지 연산(%) ←이거다.

ex) 7 mod 4 = 7 % 4 = 3. 11 mod 2 = 11 % 2 = 1.

원형 큐에서는 enQueue, deQueue를 하기 위해서 필요한 알고리즘(함수)가 있다.

1. isEmpty: 큐가 비었는지 확인

2. isFull: 큐가 꽉찼는지 확인

이 두 함수가 없으면, 원형큐에서 꼭 한 칸은 비워야 한다는 규칙이 안 지켜질 것이다.

덱(Deque: Double-ended queue)

덱은 큐의 양쪽 끝에서 삽입/삭제를 할 수 있는 확장된 큐다. 스택+큐의 특성을 둘 다 가지고 있다.

Rear, Front 둘 다에서 삽입 삭제가 가능하다.

• insertRear, deleteRear

• insertFront, deleteFront