이 블로그에서 다루는 선형 자료구조의 마지막, Queue에 대해 글을 작성하려한다. Queue는 네트워크나 보안 장비와 연관있는 곳에서 개발 관련 업무를 진행한다면 무의식적으로라도 사용하게 되는 자료구조인데, 하드웨어 프로그래밍이건 웹 프로그래밍이건 사용하는 곳이 많아 알아두면 쓸 데가 많다. 필자의 경우도 회사에서 판매하는 보안 장비가 전송하는 Syslog를 실시간으로 받아, 해당 Syslog를 변형하여Splunk로 다시 전송하는 프로그램을 Queue와 Thread로 만들었던 경험이 있다. 물론, 그 때는 Queue라는 의식도 안하고 작성했지만 말이다...
1. Queue 개요
Queue도 Stack처럼 개념 자체가 어려운 자료구조는 아니다. 단지 Stack과 달리 양 방향이 뻥 뚤린 파이프 모양을 띄고 있다는 것과, 데이터 입출력이 한 군데에서만 발생하는 Stack과 달리, 데이터가 드나드는 곳이 명확히 구분되어 있다는 차이만 있다(물론 DEQueue라는 파생 Queue는 조금 예외다).
데이터는 한 쪽 끝으로 Queue에 유입되고 반대쪽으로 나온다는 점 때문에 보통 은행 창구 앞에 줄을 서 있는 사람들로 비유를 많이 든다.
이러한 구조로 인해 Queue로 먼저 들어온 데이터는 먼저 반대쪽 끝으로 나가게 되고, 나중에 들어온 데이터는 나중에 나가게 된다. Stack을 후입선출(LIFO)이라는 고상한 용어로 표현한 것과 달리, Queue는 선입선출(First In First Out, FIFO)이라는 용어로 표현한다.
Queue는 그 특성 상, 실시간으로 들어오는 신호를 저장했다가 처리해야하는 경우에 많이 사용한다. 위에서 필자가 진행했던 업무 역시 실시간으로 유입되는 Syslog를 처리하는데에 Queue를 사용했고, 하드웨어 쪽으로 가면 CPU에서 명령어와 데이터 처리를 위해 메모리에서 인출한 정보들을 잠시 대기하도록 만드는 데에도 Queue를 사용한다(Ready Queue라고 한다).
Stack과 데이터가 드나드는 방식이 다르다보니, 기능을 표현하는 용어도 Stack과는 다르다.
| 용어 | 구성 및 기능 |
| back | 데이터가 들어오는(Enque) Queue의 Index. Stack의 Top 또는 ptr과 유사하게 동작 |
| front | 데이터가 나가는(Deque) Queue의 Index |
| capacity | Queue의 저장 공간 크기 |
| deque | Queue에서 데이터를 추출 |
| enque | Queue에 데이터를 추가 |
| clear | Queue의 초기화 |
| dump | Queue에 저장된 모든 데이터 출력 |
| find | Queue 내 데이터 검색 |
| peek | Queue의 Deque 데이터 값만 반환. Deque를 진행하지 않음. |
2. Queue의 구현 코드
이제 위에서 정의된 구성과 기능으로 Queue를 구현해보자. 우선 뼈대부터 만들어보자.
|
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
|
class QueueTest:
def __init__(self, capacity: int = 5):
self.__capacity: int = capacity
self.__q: int = [None] * self.__capacity
self.__FRONT: int = 0
self.__back: int = 0
def __is_empty(self) -> bool:
return self.__back == 0
def __is_full(self) -> bool:
return self.__back == self.__capacity
def clear(self) -> None:
pass
def dump(self) -> None:
pass
def deque(self) -> str:
pass
def enque(self, data:str) -> None:
pass
def find(self, data:str) -> None:
pass
def peek(self) -> str:
pass
|
cs |
Stack과 마찬가지로 Enque 및 Deque 시 Queue가 꽉 차 있는지, 비어있는지 확인하는 과정이 선행되어야하므로, 뼈대에 private 매서드로 __is_empty()와 __is_full()을 추가해준다. 외부에서 Queue가 비어있는지, 가득 차 있는지 확인할 필요가 있다면 public 접근 제어자 사용을 위해 함수명 앞의 언더바를 모두 제거해주면 된다.
(1) clear() 및 dump()
clear()는 Queue의 모든 내용을 비우고 초기화, dump()는 Queue의 저장 내용을 출력하는 매서드다. 두 매서드 역시 Queue의 상태와 상관없이 사용이 가능하므로, 아래와 같이 기능을 구현해주면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class QueueTest:
def __init__(self, capacity: int = 5):
self.__capacity: int = capacity
self.__q: int = [None] * self.__capacity
self.__FRONT: int = 0
self.__back: int = 0
...(생략)
def clear(self) -> None:
self.__q = [None] * self.__capacity
self.__back = 0
return None
def dump(self) -> None:
print(self.__q)
return None
|
cs |
클래스 내 private 멤버변수인 __back은 enque 시 값이 증가하고, deque 시 감소하기 때문에, Queue가 초기화되는 경우 0번 Index를 가리키도록 코드를 추가해주어야 한다.
(2) enque(): Queue에 데이터 추가
데이터의 추가를 담당하는 enque()도 크게 구현하기 어렵지는 않다. 데이터가 Queue에 들어오면 self.__back이 가리키는 Index에 데이터를 추가하고, 다음 enque가 발생할 Index 위치를 가리키도록 self.__back 값을 1 증가시키면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class QueueTest:
def __init__(self, capacity: int = 5):
self.__capacity: int = capacity
self.__q: int = [None] * self.__capacity
self.__FRONT: int = 0
self.__back: int = 0
...(생략)
def enque(self, data:str) -> None:
if not self.__is_full():
self.__q[self.__back] = data
self.__back += 1
return None
print("[WARNING] Queue is Full.")
return None
|
cs |
Enque 시, Queue가 가득 차 있다면 당연히 데이터를 추가할 수 없기 때문에, enque를 수행하기 직전에 Queue가 가득 차 있는지 검증하는 과정을 거친다. 만약 Queue에 저장 공간이 있다면 데이터를 저장하고, 아닌 경우에는 Queue가 가득 차 있다는 문구를 화면에 출력하도록 한 뒤 매서드를 종료한다.
(3) peek() : Queue에서 Back 위치의 데이터 반환
Queue의 peek()은 Stack의 peek()과 기능과 원리 자체는 동일하다. 다만 Queue의 경우 참조하는 Index가 0번, self.__FRONT 값으로 고정되어 있다는 특징이 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 |
class QueueTest:
def __init__(self, capacity: int):
self.__capacity: int = capacity
self.__q: int = [None] * self.__capacity
self.__FRONT: int = 0
self.__back: int = 0
...(생략)
def peek(self) -> str:
if not self.__is_empty(): return self.__q[self.__FRONT]
print("[WARNING] Queue is Empty")
return None
|
cs |
peek()은 Queue가 비어있는 경우, 반환할 값이 없기 때문에 이와 관련된 검증을 __is_empty() 매서드로 진행해준다.
peek()은 단순히 데이터를 출력하는 방향으로 제작할 수도 있으나, 필자는 dequeue와의 연계를 위해 값을 돌려받는 것으로 함수를 작성했다.
(4) deque() : Queue에서 Back 위치의 데이터 추출 및 반환
Queue에서 dequeue는 구현 시 고려해야 할 점이 많다. 우선, Front 위치의 데이터가 추출되면서, Queue 내부의 모든 원소가 한 자리씩 이동하게 되므로, Loop를 사용하여 이를 구현해야한다. 이 결과로 기존 Back 위치의 좌측 데이터도 None 값으로 변경되며, Queue 내 원소 이동으로 인해 Back 값 역시 1 감소하도록 만들어주어야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class QueueTest:
def __init__(self, capacity: int):
self.__capacity: int = capacity
self.__q: int = [None] * self.__capacity
self.__FRONT: int = 0
self.__back: int = 0
...(생략)
def deque(self) -> str:
tmp = self.peek()
if tmp is not None:
self.__back -= 1
for idx in range(self.__FRONT, self.__back):
self.__q[idx] = self.__q[idx + 1]
self.__q[self.__back] = None
return None
|
cs |
deque() 매서드 구현을 위해 연계한 peek() 매서드에서 미리 Queue가 비어있는 상태인지 검증을 진행하기 때문에, Queue가 비어있더라도 deque() 매서드에서는 어떠한 경고 문구도 출력하지 않는다. 이는 Stack에서 구현했던 pop() 매서드와 동일한 원리다.
(5) find(): Queue 저장 자료 검색
마지막으로 find() 매서드다. find() 매서드는 값이 Queue에 존재할 때, 값의 존재 여부만 돌려줄지, 아니면 저장 위치까지 돌려줄지는 각자의 필요에 따라 작성하면 된다. 필자는 귀찮으니까 단지 값의 저장 여부만 돌려받도록 제작해보려한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class QueueTest:
def __init__(self, capacity: int):
self.__capacity: int = capacity
self.__q: int = [None] * self.__capacity
self.__FRONT: int = 0
self.__back: int = 0
...(생략)
def find(self, data:str) -> bool:
if not self.__is_empty():
for idx in range(self.__FRONT, self.__back + 1):
if self.__q[idx] == data:
return True
return False
print("[WARNING] Queue is Empty")
return None
|
cs |
개요에서 정의한 Queue의 구조와 기능을 구현한 코드가 완성되었다. 결과는 아래와 같다.
3. 원형 큐(Circular Queue)
위에서 필자가 구현한 Queue는 Deque가 진행되는 경우, Queue 내의 원소를 하나씩 자리 이동을 진행해주어야하기 때문에 Loop 문이 필수적으로 들어가야한다. 이 때문에 Deque() 매서드에 대한 시간 복잡도가 O(N)으로 도출된다. 지금이야 Queue의 크기가 크지 않기 때문에 O(N)이더라도 수행 시간이 많이 걸리거나 하는 문제가 없지만, 실제 필자가 수행했던 업무와 같이, Syslog가 실시간으로 대량 유입되는 환경이라면 데이터가 빠질 때 마다 O(N)을 진행하는 것은 부담이 될 수 밖에 없다.
이 문제는 필자가 태어나기 전에도 고민했던 누군가가 있었을 듯 한데, Queue의 구조를 조금 비틀어 만든 원형 큐(Circular Queue), 또는 원형 버퍼(Circular Buffer)라는 것이 등장한다.
원형 큐는 마치 뱀이 꼬리를 무는 모양처럼 - Benzene이 생각난다 - 생겼는데, 이러한 구조로 인해 데이터의 Deque 시 원소를 이동시키는 것이 아니라 내부의 Pointer만 위치를 수정하면 되기에 데이터를 제외하더라도 시간 복잡도가 O(N)이 되지 않는다.
위에 첨부한 이미지를 보면 알겠지만, 원형 큐는 구현 시 Front의 Index도 지속적으로 변하는 것을 고려해야한다. 특히 Front의 Index는 Back이 가리키는 Index를 절대 추월할 수 없기 때문에, 값을 증가시키더라도 Front가 Back을 추월하는지의 여부도 확인할 수 있도록 코드를 작성해야한다.
우선, clear나 dump, find와 같은 불필요한 매서드를 싸그리 제외하고 원형 큐의 특징이 드러나는 매서드만 골라서 작성해보자.
|
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
|
class CircularQueueTest:
def __init__(self, capacity: int = 5):
self.__capacity: int = capacity
self.__q = [None] * self.__capacity
self.__front: int = 0
self.__back: int = 0
self.__looped: bool = False
def __is_empty(self):
return self.__front == self.__back and not self.__looped
def __is_full(self):
return self.__front == self.__back and self.__looped
def enque(self, data:str):
if not self.__is_full():
self.__q[self.__back] = data
self.__back += 1
if self.__back == self.__capacity:
self.__back = 0
self.__looped = True
return None
print("[WARNING] Queue is Full")
return None
def deque(self):
tmp = self.peek()
if tmp is not None:
self.__q[self.__front] = None
self.__front += 1
if self.__front == self.__capacity:
self.__front = 0
self.__looped = False
return tmp
return None
def peek(self) -> str:
if not self.__is_empty():
return self.__q[self.__front]
print("[WARNING] Queue is Empty")
return None
|
cs |
(1) __is_empty(), __is_full() 매서드
Queue가 비어있을 때와 가득 차 있을 때의 front와 end 값은 항상 동일하다. 그러나, back이 Queue 내부를 한 바퀴 돌아 front와 동일한 위치에 있는지, 아니면 Queue 내부의 순회 없이 front와 동일한 위치에 있는지에 따라 그 결과가 갈린다.
(2) enque(), deque()
따라서 enque와 deque 시, 이들 값이 Queue의 크기를 초과하게 되는 경우, Queue를 한 바퀴 훑어 Queue의 첫 부분으로 돌아갔음을 확인할 수 있는 변수가 필요하다. 필자가 작성한 코드에서는 self.__looped가 그 역할을 하는데, 초기 인스턴스 생성 단계에서는 이 값이 False로 지정되어 있으며, self.__back이 Queue를 순회하면 True를, self.__front가 Queue를 순회하면 False로 변경되도록 만들었다.이렇게 코드를 작성하면 Front와 Back Index가 동일 위치에 존재하더라도 Queue가 가득 차서 동일한 위치인지, 아니면 비어 있어서 동일한 위치인건지 확인이 가능해진다.
물론, self.__back과 self.__front 모두 Queue를 순회하면 다시 0번 index로 돌아올 수 있도록 함수 후반부에 조건문도 추가해주어야 한다.
구현한 코드의 결과는 아래와 같이 나타난다.
Fin.
'Python > Python Data Structure and Algorithm' 카테고리의 다른 글
| [자료구조 with Python] 15. 선형 자료 구조 - Stack (0) | 2024.03.19 |
|---|---|
| [자료구조 with Python] 14. 정렬 알고리즘(7), 쉘 정렬(Shell Sort) (0) | 2024.03.18 |
| [자료구조 with Python] 13. 정렬 알고리즘(6), 퀵 정렬(Quick Sort) (0) | 2024.03.15 |
| [자료구조 with Python] 12 - 정렬 알고리즘(5), 병합 정렬(Merge Sort) (0) | 2024.03.13 |
| [자료구조 with Python] 11 - 정렬 알고리즘(4), 선택 정렬(Selection Sort) (0) | 2024.03.12 |
댓글