Circular Queue

환형 큐란 큐를 응용하여 만드는 것으로 정해진 개수의 공간을 빙 돌려가며 큐를 사용하는 것이다. 즉 정해진 길이의 큐를 만들고, 그 큐를 돌려가며(입과 발이 연결된 형태) 사용할 수 있는 것이다. 리볼버 권총의 탄창을 생각하면 쉬울 것이다.

환형 큐의 연산은 일반적인 큐와 같다. 그러나 정해진 공간의 리스트라는 것이 특징이고, front, rear를 이용해 큐의 시작점, 끝점을 기록하며 큐가 가득 차면 더이상 원소를 넣을 수 없다(큐의 길이를 기록할 필요가 있다).
큐와의 차이를 살펴보면 큐는 배열을 가지고 동적으로 길이를 늘리고 줄이며 연산하지만 환형 큐는 정해진 길이의 배열을 선언해두고 그 큐 내에서 작동하므로 연산의 복잡도 면에서 이득을 볼 수 있다. 특히 큐의 경우 dequeue를 하면 배열 가장 앞의 원소를 제거하므로 그 뒤의 모든 원소를 앞으로 당겨와야한다는 단점이 있는데 환형 큐에서는 그런 단점을 보완할 수 있다.

환형 큐의 추상적 자료구조 구현

환형 큐의 연산을 정의하자면

  • size(): 현재 큐에 들어있는 데이터 원소의 수
  • isEmpty(): 현재 큐가 비어있는지
  • isFull(): 현재 큐가 가득 찼는지
  • enqueue(x): 데이터 원소 x를 큐에 추가
  • dequeue(): 큐 가장 앞의 데이터 원소 삭제하고 반환
  • peek(): 큐 가장 앞의 데이터 원소 삭제하지 않고 반환

와 같고 이것도 큐와 동일하다.

배열로 구현한 환형 큐

이번에도 지난번과 같이 배열, 연결 리스트로 환형 큐를 구현할 수 있지만 고정된 길이의 리스트를 사용해 만드는 환형 큐이기에 굳이 연결 리스트를 사용하지 않고 배열로 구현해보도록 하겠다.

Q.enqueue(A) # rear = A(0)
Q.enqueue(B) # rear = B(1)
Q.enqueue(C) # rear = C(2)
r1 = Q.dequeue() # r1 = A, front = A(0)
r2 = Q.dequeue() # r2 = B, front = B(1)
Q.enqueue(D) # rear = D(3)
Q.enqueue(E) # rear = E(4)
Q.enqueue(F) # rear = F(5)
# Q.isEmpty() == False(front가 이동)
Q.enqueue(G) # rear = G(0)
r3 = Q.dequeue() # r3 = C, front = C(2)

과 같은 로직으로 진행된다고 생각하면 된다. rear는 방금 넣은 값의 위치를 의미하고 front는 방금 뽑아낸 값의 위치를 나타낸다. 그렇게 front+1~rear의 값들이 환형 큐에 들어있는 유의미한 값이라고 할 수 있다.

배열을 이용해 환형 큐를 구현해보겠다.

class CircularQueue:
    def __init__(self, n):
	self.maxCount = n
	self.data = [None]*n
	self.count = 0
	self.front = -1
	self.rear = -1

    def size(self):
	return self.count

    def isEmpty(self):
	return self.count == 0

    def isFull(self):
	return self.count == self.maxCount

    def enqueue(self, x):
	if self.isFull():
	    raise IndexError('Queue full')
	self.rear = (self.rear+1) % self.maxCount
	self.data[self.rear] = x
	self.count += 1

	def dequeue(self):
	if self.isEmpty():
	    raise IndexError('Queue empty')
	self.front = (self.front+1) % self.maxCount
	x = self.data[self.front]
	self.count -= 1
	return x

	def peek(self):
	if self.isEmpty():
	    raise IndexError('Queue empty')
	return self.data[(self.front+1) % self.maxCount]

과 같이 구현할 수 있는데 우선 초기화 메소드에서 None값을 가지는 입력된 길이만큼의 배열을 만들어주고, front, rear를 -1로 초기화해준다. -1로 정하는 이유는 front, rear를 한칸씩 움직이면서 정보가 저장된 활성화된 부분을 표시해주는데 처음으로 정보가 담기는 곳이 0번 인덱스이므로 -1로 초기화해준다.
size()부터 isFull()까지는 모두 간단하게 이해가 될 것이라고 생각하고 아래 세 함수만 설명하도록 하겠다.

enqueue(x)

우선 enqueue에서는 큐가 가득 찼을 때 더이상 값을 입력받으면 안되기 때문에 조건문으로 한번 처리해준다. 그 후 self.rear = (self.rear+1)%self.maxCount와 같이 rear의 값을 변경해주는데, 이는 현재 rear의 다음 위치에 값을 저장하되 배열의 정해진 크기를 넘어가면 배열의 가장 앞으로 와서(0번 인덱스) 다시 정보를 저장하기 시작하므로 rear에 1을 더해준 값에 큐의 전체 길이를 % 연산을 해서 rear 값을 갱신한다.
예를 들어 전체 큐의 길이가 4이고, 현재 인덱스가 3이라면 다음 인덱스는 0이 되어야하는데 이때 (3+1)%4==0이므로 잘 처리되게 된다. 또한 이미 큐가 몇바퀴 돈 상태이면 배열의 그 위치에는(rear) 사용하지 않는 쓰레기 값이 들어있을 것이기 때문에 값을 넣고자 하는(enqueue) 값으로 변경해주면 된다(처음 값을 넣기 시작하는 경우라고 하더라도 data에 append하지 않는 이유는 크기가 정해진-미리 할당한 배열에 값을 넣어주는 것이기 때문이다). 마지막으로 self.count를 통해 큐에 들어있는 값의 수를 조정해주면 된다.

dequeue()

dequeue의 경우에도 front를 움직이면서 큐에 속하는 값들 중 가장 앞의 값을 제거해주는데, 현재 front는 직전에 dequeue한 사용하지 않는 값의 인덱스이므로 enqueue에서의 rear와 동일하게 self.front = (self.front+1)%self.maxCount를 통해 front를 한칸 옮겨준다. 그럼 현재 front인덱스에 있는 값이 지금 dequeue한 그 값이 되고, self.data[self.front]를 통해 방금 dequeue한 값을 반환할 수 있게 된다. 또한 front+1~rear의 데이터만이 큐에 들어있는 것으로 생각하므로 front에 있는 값(방금 dequeue된 값)은 큐에서 제거된 것처럼 동작하게 된다. 마지막으로 self.count를 통해 큐에 들어있는 값의 수를 조정해주면 된다.

peek()

peek은 dequeue와 동일하지만 front를 수정하지 않는 동작을 한다. self.data[self.front]로 front 인덱스의 값을 출력하지 않는 이유는 front 값은 마지막 dequeue 연산에서 제거된 값이기 때문에 그 다음의 값이 큐의 처음 값이기 때문이다.

정리

이렇게 간단하게 배열을 이용해서 환형 큐를 구현해보았다. 직접 환형 큐 구현 문제를 풀어보면서 다시 한번 복습할 수 있다.
또한 전 포스트에서 간단한 예제 문제를 가지고 와서 같이 풀어볼 생각을 했었는데, 환형 큐로 구성된 간단한 알고리즘 문제를 찾을 수가 없었다....

(전부 다 너무 어려워... 이러다 다 죽어...)

그러므로 우선은 배열을 통한 구현까지만 포스팅하도록 하겠다. 후에 블로깅하기 좋은 알고리즘 문제를 찾는다면 다시 포스팅을 하도록 하겠다.

profile
Surfer surfing on the dynamic flow of the world

0개의 댓글