[자료구조] 06. 큐

큐는 삽입과 삭제가 각각 반대쪽 끝에서 수행되는 자료구조이다.

들어온 곳으로 가장 최근에 들어온 원소가 나가는 스택과는 다르게, 큐는 먼저 들어온 사람이 먼저 나가는 선입선출의 방식이다.

은행의 대기열에서 먼저 와서 번호표를 먼저 뽑았던 사람 순서대로 일이 처리되는 것과 같다.

큐에서는 뒤(rear)에서 삽입하고 앞(front) 에서 원소를 순서대로 삭제하고 반환한다.

 

큐 역시 배열과 연결리스트로 둘 다 구현할 수 있지만, 배열의 경우 약간의 문제가 있다.

큐를 배열로 구현하는 경우, push 와 pop 의 과정에서 원소들이 배열의 오른쪽으로 치우치는 문제가 발생한다.

삭제는 왼쪽에서 진행되는데, 삽입은 오른쪽으로만 되기 때문이다.

이런 문제를 해결하기 위해서 배열로 구현할 경우, 배열을 원형으로 보아 순환시키는 구조를 갖게 한다.

배열이 가득 찼을 경우를 대비해 rear 다음의 인덱스를 모듈러 연산을 통해 앞으로 이동시킨다.

하지만 이 경우 역시, 큐에 모든 원소를 삭제할 경우 front 와 rear 간의 인덱스 위치가 애매해지는 문제가 발생한다.

이를 위해서 임의적으로 메모리 한칸을 비워두고, front 가 맨 앞 원소가 아닌 그 하나 앞의 빈 공간을 가리키게 해준다.

메모리를 하나 낭비하는 대신, 매번 front 와 rear 를 검사해줄 필요를 없애주는 것이다.

이건 그림으로 봐야 이해가 더 잘 되지만... 일단은 암튼 그렇다는걸 알아두자

 

스택은 연결리스트로 했으니, 큐는 배열로 구현해 보았다.

private E[] q;
private int front, rear;
private int size;

public Queue()
{
	front = rear = 0;			// front 는 맨앞 원소 한칸 앞의 빈 공간, rear 는 맨 마지막 원소
	size = 0;					// 시작 사이즈는 0
	q = (E[])new Object[2];
}

 

원소를 뒤에서부터 넣는 push 이다.

public void push(E item)
{
	if((rear + 1) % q.length == front) resize(q.length * 2);	// rear 다음 칸이 front 와 같다면 배열에 남은 공간이 없다는 뜻
	
	rear = (rear + 1) % q.length;	// rear 를 한칸 뒤로 옮겨주고
	q[rear] = item;					// 해당 위치에 새로운 원소 추가
	size++;
}

 

앞에서부터 원소를 제거하고, 제거한 원소를 반환해주는 pop 이다.

private void resize(int newSize)
{
	Object[] newQ = new Object[newSize];	// 새로 할당한 공간
	
	for(int i = front + 1, j = 1 ; j < size + 1 ; i++, j++)
	{
		newQ[j] = q[i % q.length];	// 기존에 원형으로 들어가있던 원소들을 인덱스 1부터 size 까지 순서대로 넣어줌
	}
	
	front = 0;			// 인덱스1에 첫원소 들어가므로, front 는 0 번째에 위치
	rear = size;		// 1 부터 size 까지 각각 들어가므로, size 위치가 마지막 원소의 위치
	q = (E[])newQ;
}

 

ArrayList 를 구현할때도 배열이기 때문에 크기를 조정해주는 resize 가 있었는데, 여기도 배열 기반 구현이기 때문에 필요하다.

private void resize(int newSize)
{
	Object[] newQ = new Object[newSize];	// 새로 할당한 공간
	
	for(int i = front + 1, j = 1 ; j < size + 1 ; i++, j++)
	{
		newQ[j] = q[i % q.length];	// 기존에 원형으로 들어가있던 원소들을 인덱스 1부터 size 까지 순서대로 넣어줌
	}
	
	front = 0;			// 인덱스1에 첫원소 들어가므로, front 는 0 번째에 위치
	rear = size;		// 1 부터 size 까지 각각 들어가므로, size 위치가 마지막 원소의 위치
	q = (E[])newQ;
}

 

수행시간

배열로 구현한 큐의 삽입과 삭제 연산은 모두 O(1) 이다.

배열 크기 조정의 resize 가 들어가며 각 요소들을 복사하기 때문에 이론적으로는 O(N) 이지만, 상각분석 해보면 실제로 O(1) 이다.

단순연결리스트로 구현한 큐도 역시 삽입과 삭제 모두 O(1) 이다.

스택과 마찬가지로 큐도 중간에 있는 원소들을 볼 필요가 없이 front 와 rear 만 관리해주면 되기 때문에 탐색은 볼 필요가 없다.