대기줄
오늘 우리는 큐에 대해 배웠습니다.
Linear Queue, Circular Queue 및 Double Ended Queue와 같은 대기열을 구현하는 방법에는 여러 가지가 있습니다.
오늘은 Circular Queue 구현에 중점을 둘 것입니다.
대기열은 후입선출 구조인 스택과 다릅니다.
먼저 들어간, 먼저 나온 구조를 가진 데이터 구조입니다.
선입선출 구조란?
'추천 관련글,First In First Out 또는 줄여서 FIFO라고도 하며 데이터 구조에 들어가는 데이터가 먼저 나온다는 의미입니다.
우리가 식당을 기다릴 때 대기열은 첫 번째 사람이 들어가는 구조와 같습니다!
가장 기본적인 큐 데이터 구조는 목록을 사용하여 구현됩니다.
항목은 목록의 앞쪽부터 하나씩 쌓이게 되며, 대기열에서 항목을 삭제하면 맨 앞의 항목부터 먼저 빠져나가게 되는데, 의 연산으로 인해 오버헤드가 증가하게 됩니다.
이를 방지하기 위해 큐 데이터 구조는 큐의 맨 앞 위치를 나타냅니다.
앞쪽맨 뒤 위치를 나타냅니다.
뒤쪽에 호출된 변수는 계산을 수행하는 데 사용됩니다.
큐의 기본 동작은 다음과 같습니다.
- 삽입 : 큐의 끝에 항목을 추가하는 작업입니다.
뒤에서 가리키는 지점에 요소를 삽입합니다.
삽입 후에는 등을 뒤로 움직여야 합니다. - 끄다 : Queue의 첫 번째 요소를 삭제하는 작업입니다.
항목이 실제로 삭제되는 것이 아니라 앞쪽을 한 칸 뒤로 이동하여 대기열의 앞쪽 위치를 변경하도록 구현했습니다.
- 몰래 엿보다 : 대기열의 첫 번째 항목을 인쇄합니다.
front 로 지정된 위치에 요소를 출력합니다.
순환 대기열을 구현하기 전에 선형 대기열이 작동하는 방식을 살펴보겠습니다.
선형 대기열
먼저 선형 큐의 초기 상태는 위의 그림과 같습니다.
대기열에 항목이 없고 현재 앞면과 뒷면이 같은 위치에 있음을 알 수 있습니다.
여기에 항목 3을 삽입하겠습니다.
새 요소를 삽입하면 그림과 같이 뒤가 있던 곳에 요소가 삽입되고 뒤가 한 칸 뒤로 이동합니다.
이미지와 같이 몇 가지 요소를 더 추가했습니다.
이제 요소를 삭제하겠습니다.
맨 앞의 요소 3이 삭제되고 앞의 요소가 한 필드 뒤로 이동합니다.
큐에서 항목을 삭제하면 실제로 목록에서 항목이 삭제되는 것이 아니라 큐의 앞 값을 1씩 증가시켜 큐의 앞을 다음 항목으로 대체합니다.
그림에서 보듯이 선형 큐 형태로 구현할 경우 매우 큰 단점이 있다.
바로 소거 동작을 수행하여 전면을 뒤로 이동시키면 전면의 전면 부분에 더미 데이터가 그대로 저장되어 저장 효율이 떨어진다.
나중에 설명할 Circular Queue는 이러한 점을 보완하고 구현합니다.
순환 대기열
선형 대기열과 같은 순환 대기열에는 목록의 기본 구현이 있습니다.
다만, 앞값과 뒤값에 대해 추가적인 모듈 연산을 수행하여 앞값이 이미 통과한 지수의 값을 재사용할 수 있도록 한다.
모듈식 작동이란 무엇입니까?
모듈러 산술은 나머지 산술과 관련이 있습니다.
a mod b는 a % b와 같습니다.
순환 대기열은 다음 이미지에 표시됩니다.
처음에는 선형 단서처럼 앞면과 뒷면이 동일한 값을 갖는 것을 볼 수 있습니다.
이제 Circular Queue 구현에 대해 진지하게 살펴보겠습니다.
class CircleQueue:
rear = 0
front = 0
capacity = 8
queue = list()
def __init__(self):
self.rear = 0
self.front = 0
self.queue = (0 for _ in range(self.capacity))
def is_empty(self):
return self.rear == self.front
def is_full(self):
return (self.rear + 1) % self.capacity == self.front
def peek(self):
if self.is_empty():
print("Empty")
return
return self.queue(self.front)첫째, CircleQueue 클래스는 앞뒤, 대기열의 크기인 용량, 항목 목록인 대기열을 가지고 있습니다.
용량은 기본적으로 8개로 설정되어 있으며 큐가 꽉 차서 확장이 불가능할 경우 확장을 계속합니다.
위의 is_empty 및 is_full 함수는 각각 대기열이 비어 있는지 또는 가득 차 있는지를 반환하는 함수입니다.
앞과 뒤가 가리키는 위치가 같으면 힌트가 비어 있고 뒤가 시계 방향으로 한 칸 이동하여 앞과 같아지면 힌트가 가득 찼습니다.
이제 몇 가지 요소를 삽입해 보겠습니다.
총 6개의 요소를 삽입한 후의 결과는 다음과 같습니다.
뒤에는 여전히 다음 요소가 삽입될 위치가 표시됩니다.
# class CircleQueue
def delete(self):
if self.is_empty():
print("Empty")
return
elem = self.queue(self.front)
self.front = (self.front + 1) % self.capacity
return elem이제 적어도 세 개의 날짜를 삭제합시다.
삭제 후 사진은 아래와 같습니다.
선형 큐처럼 삭제되는 실제 요소가 아니라 앞부분의 위치만 변경되는 것을 확인할 수 있습니다.
지금은 이전 Linear Queue와 가장 큰 차이점이 된 부분입니다.
요소를 4번 더 삽입하는 과정을 살펴보겠습니다.
4개의 항목을 모두 삽입하기 전에 2개의 항목을 삽입하면 Rear는 대기열의 마지막 인덱스로 이동합니다.
이 시점에서 선미는 한 방 더 이동해야 하며 여기서는 모듈식 작업이 사용됩니다.
먼저 코드를 살펴보겠습니다.
# class CircleQueue
def insert(self, x):
self.queue(self.rear) = x
if self.is_full():
self._expand()
self.rear = (self.rear + 1) % self.capacity뒤쪽 위치에 x가 먼저 삽입되고 용량으로 나눈 나머지가 시계 방향 역방향 이동 동작에 사용되는 것을 볼 수 있습니다.
따라서 back+1의 값이 목록의 인덱스 범위를 벗어나더라도 모듈러 연산을 통해 목록의 맨 위로 이동할 수 있습니다.
앞부분이 선형대기열에서 이미 통과한 부분을 재사용할 수 없다는 단점을 보완할 수 있습니다!
이 모듈식 작업으로 인해 현재 대기열에 있는 항목 수를 계산하는 것은 선형 대기열보다 약간 더 복잡합니다.
Linear Queue에서 대기열에 있는 항목 수를 확인하려면 뒤에서 앞을 빼면 됩니다.
반면에 Circular Queue를 사용하면 뒤쪽이 앞쪽보다 작을 수 있으므로 Linear Queue와 같은 방식으로 요소 수를 찾기가 어렵습니다.
# class CircleQueue
def size(self):
if self.rear < self.front:
return self.rear - self.front + self.capacity
else:
return self.rear - self.f이를 위해 요소수를 계산할 때 앞바퀴보다 뒷바퀴가 작을 때 용량을 추가하는 작업을 진행했다.
꼬리가 앞바퀴보다 작아진 것은 꼬리가 지수의 범위를 넘어섰기 때문에 실제로는 꼬리+용량의 지수와 관련이 있다고 해도 무방하다.
따라서 크기를 계산할 때 후면이 전면보다 작은 경우 정전 용량이 추가됩니다.
9와 10을 계속 삽입하면 그림은 다음과 같습니다.
여기에도 11번 요소를 삽입하면 앞뒤가 동일해진다.
이 경우 확장은 _expand 함수를 사용하여 수행됩니다.
# class CircleQueue
def _expand(self):
self.capacity *= 2
tmp = (0 for _ in range(self.capacity))
ptr = self.front
i = 0
while ptr !
= self.rear:
tmp(i) = self.queue(ptr)
i += 1
ptr = (ptr + 1) % (self.capacity // 2)
tmp(i) = self.queue(ptr)
self.front = 0
self.rear = i
self.queue = tmp코드만 봐서는 헷갈릴 수 있으니, 아래 이미지를 함께 살펴보시죠!
처음에 ptr 변수를 앞에서 같게 설정하고 뒤에 같을 때까지 +1씩 증가시켜 요소를 검색합니다.
동시에 새 queue의 인덱스 i도 ptr과 같이 증가하고 현재 ptr이 가리키는 요소를 i가 가리키는 위치에 복사합니다.
ptr이 리스트의 인덱스 영역 끝으로 가더라도 모듈러 연산을 통해 다시 앞쪽으로 보낼 수 있다.
모든 요소가 복사되면 아래 이미지와 같은 결과를 얻을 수 있습니다.
이제 마지막으로 큐의 앞면과 뒷면을 새 목록에 일치시켜야 합니다.
front를 리스트의 시작점인 0으로 설정하는 것은 쉽지만, back의 경우 마지막 값 i로 초기화해야 합니다.
이 경우 back은 다음 요소가 삽입될 위치가 아니라 마지막 요소의 위치를 가리키며, 삽입 후 확장 작업을 수행하므로 확장 후 다시 1씩 증가하는 추가 작업이 있습니다.
따라서 Expand 함수에서 후행 값은 마지막 요소의 위치로 설정됩니다.
확장 완료 후 insert 함수의 trailing 값은 다음과 같이 조정됩니다.
이와 같이 큐의 경우 목록이 가득 차면 두 배 크기로 확장됩니다.
물론 확장하는 방법은 다양하지만 이 포스팅에서는 다루지 않습니다.
.!
CircleQueue의 전체 구현 코드는 다음과 같습니다.
class CircleQueue:
rear = 0
front = 0
capacity = 8
queue = list()
def __init__(self):
self.rear = 0
self.front = 0
self.queue = (0 for _ in range(self.capacity))
def is_empty(self):
return self.rear == self.front
def is_full(self):
return (self.rear + 1) % self.capacity == self.front
def insert(self, x):
self.queue(self.rear) = x
if self.is_full():
self._expand()
self.rear = (self.rear + 1) % self.capacity
def delete(self):
if self.is_empty():
print("Empty")
return
elem = self.queue(self.front)
self.front = (self.front + 1) % self.capacity
return elem
def size(self):
if self.rear < self.front:
return self.rear - self.front + self.capacity
else:
return self.rear - self.front
def _expand(self):
self.capacity *= 2
tmp = (0 for _ in range(self.capacity))
ptr = self.front
i = 0
while ptr !
= self.rear:
tmp(i) = self.queue(ptr)
i += 1
ptr = (ptr + 1) % (self.capacity // 2)
tmp(i) = self.queue(ptr)
self.front = 0
self.rear = i
self.queue = tmp
def peek(self):
if self.is_empty():
print("Empty")
return
return self.queue(self.front)