[자료구조] 3. Queue - 큐 구현 (선형, 원형)

큐의 구현

큐는 두가지 방법을 통해서 구현할 수 있다

1. 배열을 활용하여 선형 형태로 큐를 구현하는 것.
2. 배열을 활용하여 원형 형태로 큐를 구현하는 것

 

선형 큐

다음처럼 선형 큐는 일반 선형 배열 형태로 구현한다.

 

• Front 와 Rear를 통해 큐의 맨 앞과 뒤를 표시한다.
• 초기상태의 표시를 위해 front와 rear는 -1로 시작한다.
• Front위치에는 아무것도 저장하지 않는다

 

공백 상태 : Front = Rear

포화 상태 : Rear = Max_index

 

선형 큐의 문제는 dequeue를 통해 요소를 큐에서 제거함에도 불구하고 배열 크기만큼의 데이터만 저장할 수 있다는 점에 있다.

즉, 아무리 dequeue연산을 통해서 요소를 제거해도 이미 이전에 5개의 요소를 저장한 바가 있다면 더 이상 해당 큐를 사용할 수 없다.

 

원형 큐

위에서 언금한 선형 큐의 문제점은 원형 큐를 통해서 해결할 수 있다. 

원형 큐라는 것은 복잡한 것이 아니라, 선형 큐에 mod연산을 도입하여 계속해서 큐를 사용할 수 있도록 하는 것이다.

 

선형 큐의 문제점은 front와 rear의 값이 계속 커져서, 결국 더 이상 front와 rear의 값을 크게 만들 수 없기 때문에 발생한다.

front값이 크다는 것은, front 앞의 인덱스들은 모두 빈자리라는 것이다. 우리는 mod연산으로 이 앞의 자리들 또한 계속 사용할 수 있다.

 

• rear=5일때 뒤에 새로운 data를 추가하려고 한다.
• front = 3이다. 즉, 인덱스 0,1,2는 비어있고 새로운 데이터를 받을 수 있다
• rear+1 = 6은 불가능. 그러나 (rear+1) mod 6 = 0으로, 인덱스 0을 다음 자리로 사용할 수 있게 한다.

 

공백 상태 : Front = Rear

포화 상태 : Front = (Rear+1)%M 

 

주의할 점

주의할 점은, 선형큐와 원형 큐의 경우 공백상태와 포화상태의 구별 방법이 서로 달라 혼동될 수 있다는 것이다.

	선형 큐	원형 큐
초기 상태	Front = Rear = -1	Front = Rear = 0
공백 상태	Front == Rear	Front == Rear
포화 상태	Rear == Max_Idx	(Rear+1) % M == Front