자료구조 스택과 큐 (2)- 원형 큐
"원형 큐(Circular Queue)"
“원형 큐”(Circular Queue)는 선형 큐의 문제점을 보완하기 위한 자료구조 이다.
선형 큐(Queue)의 단점으론,
첫 번째로,
큐에 데이터가 꽉차면 데이터를 더 추가할 수 없다는점.
(전체 사이즈를 늘리고 원소 재복사 가능,-시간복잡도 증가
python 리스트 사용시 이에 해당 = 동적배열할당 문제)
두 번째로,
dequeue를 계속하게 되면 앞쪽의 공간낭비
(정해진 크기의 큐 안에서 front가 뒤로 밀려 앞 공간이 남게됨,
이로 인해 모든 원소를 앞쪽으로 다시 당겨와야함 == 속도 느림)
간단하게 예시를 들어보자,
rear => 4 3 2 1 <= front
라는 선형 큐가 존재할 때,
dequeue를 진행하게되면
rear => 4 3 2 <= front
상태가 되는데, 이 상태에선 enqueue를 진행 할 수 없다.
이 단점들을 보완한 자료구조가 원형 큐 이다.
원형 큐는,
front-rear 두개의 포인터가 원소를 가리키며
선형 큐의 모양을 원으로 연결시킨 자료구조이다.
원소를 담는 구조 자체가 원이기에(마지막 위치 => 시작위치 연결)
모듈러 연산을 이용한 값 삽입과 인덱스 조정이 일어난다.
선형 큐와 같이 rear에서 enqueue / front에서 dequeue가 발생하며,
동적 배열을 쓰지 않아 메모리공간 낭비가 발생 하지 않는다.
=앞쪽에 공간이 남아있다면 원형구조를 활용해 앞쪽으로 추가가능.
또한 재배열 할 필요도 없고,모든 연산은 O(1)시간으로 빠르다.
다만,
크기가 정해져있어 연산 시 원형 큐의 크기를 미리 파악하자.
또한,이 원형 큐도 단점이 존재하는데
enqueue시 칸을 비워 놓지 않고 모든 칸을 다 이용하면서
rear,front 포인터를 이동 시킬시
큐가 꽉찬 상태와 빈 큐인 상태를 구별하지 못한다.
(rear,front 포인터가 같은 원소를 가리키는 경우가
남은 원소 1개를 가리키는 경우인지/dequeue를 하다가 만난 경우인지)
따라서,한 칸을 비워두고 enqueue를 하는 방식으로
rear 포인터가 빈 칸을 활용하는 방법으로 개선 할 수 있다.
python으로 작성한 코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class CircularQueue():
def __init__(self, size): #생성자
self.size = size #원형 큐의 원소 개수
self.queue = [None for i in range(size)] #큐 생성,list를 활용한 초기화
self.front = self.rear = -1 #front,rear의 초기화 상태 = -1
def enqueue(self, data):
# condition if queue is full
if ((self.rear + 1) % self.size == self.front): #rear 포인터와 front 포인터가 같은곳을 가리킬 때 = 꽉찬 큐
print(" Queue is Full\n")
# condition for empty queue
elif (self.front == -1): #front,rear 포인터가 -1을 가리킬 경우 == 초기화상태
self.front = 0 #값 삽입을 위한 재설정 필요(초기화 상태 아님)
self.rear = 0
self.queue[self.rear] = data #rear에 값 삽입
# next position of rear
else:
self.rear = (self.rear + 1) % self.size #원소가 있는 큐인 경우 rear 인덱스 증가 및 값 추가
self.queue[self.rear] = data
def dequeue(self):
# condition for empty queue
if (self.front == -1): #큐가 빈 상태(초기화인 상태)
print ("Queue is Empty\n")
# condition for only one element
elif (self.front == self.rear): #원소값이 1개 남은 상태 일때(rear 포인터와 front 포인터가 같은곳을 가리킴)
temp = self.queue[self.front] #맨 앞 값을 임시 저장
self.front = -1 #빈 상태로 전환
self.rear = -1
return temp #남아있던 값 반환
else: #원소가 있는 경우
temp = self.queue[self.front] #front(지울값) 임시저장
self.front = (self.front + 1) % self.size #front 포인터 이동
return temp #지운 값 반환
def display(self):
# condition for empty queue
if(self.front == -1):
print ("Queue is Empty")
# condition for full ~ one element left queue
elif (self.rear >= self.front):
print("Elements in the circular queue are:",
end = " ")
for i in range(self.front, self.rear + 1):
print(self.queue[i], end = " ")
print ()
else:
print ("Elements in Circular Queue are:",
end = " ")
for i in range(self.front, self.size):
print(self.queue[i], end = " ")
for i in range(0, self.rear + 1):
print(self.queue[i], end = " ")
print ()
if ((self.rear + 1) % self.size == self.front):
print("Queue is Full")
# Driver Code
ob = CircularQueue(5)
ob.enqueue(14)
ob.enqueue(22)
ob.enqueue(13)
ob.enqueue(-6)
ob.display()
print ("Deleted value = ", ob.dequeue())
print ("Deleted value = ", ob.dequeue())
ob.display()
ob.enqueue(9)
ob.enqueue(20)
ob.enqueue(5)
ob.display()
#final result
Elements in the circular queue are: 14 22 13 -6
Deleted value = 14
Deleted value = 22
Elements in the circular queue are: 13 -6
Elements in Circular Queue are: 13 -6 9 20 5
Queue is Full
#중요한것은,포인터가 가리키는 위치만 변하는거지 원소의 위치는 변하지 않는다.
#rear 위치가 가장 중요하다.
예시를 들어,
전체 크기가 6인 Circular Queue가 있다고 하자.
enqueue를 6번 하였고,
rear 다음 front 포인터가 있다(꽉찬 상태).
이 상태에선 enqueue가 안된다.
dequeue를 2번 행하고
front 포인터는 앞으로 증가하였을거다.
이상태에서 enqueue를 행한다면,
모듈러연산으로 인해 인덱스 (rear+1) % size 에 각각 값이 들어간다.
=메모리공간 효율적 사용
+ 원형큐는 ring buffer라고도 부른다.