[Data Structure] Circular Queue

4 minute read

python3로 Circular Queue 구현하기

__ init __()

먼저 데이터 구조의 초깃값을 정한다. Queue의 크기를 k로 두고, 값을 담을 수 있게 길이가 k인 리스트 queue_list 를 만든다.

Queue에는 두개의 포인터가 필요하다. 한개는 Front를 가리켜야 하고, 다른 하나는 Back을 가리켜야 한다.

1def __init__(self, k: int):
2    self.size = 0    # 처음 리스트의 길이
3    self.max_size = k    # 리스트의 길이
4    self.queue_list = [0] * k   # Queue를 담을 리스트
5    self.front = self.rear = -1    # pointer

enQueue()

enQueue() 는 Circular Queue에 값을 삽입하는 함수이다.

enQueue() 는 boolean을 반환한다. 값을 삽입하는 것이 성공하면 True 를 반환하고, 실패하면 False 를 반환한다.

  1. 리스트의 초기 크기와 최대 크기가 같으면 값을 삽입할 수 없으므로 False를 반환한다.
  2. 리스트의 뒷 부분(back)이 초기에 설정해둔 -1이면 rear 와 front 에 0을 넣는다. 왜냐하면 두 포인터 모두 리스트의 0번째 인덱스를 가리키고 있기 때문이다.
  3. rear 값이 -1이 아니라면, rear 에 1을 증가 시키 것을 max_size 로 나머지 연산한 값이 rear 가 된다.
  4. 그리고 queue_list 에서 rear 번째에 값이 들어간다.
  5. 새 값이 들어가면서 길이가 증가하였으므로 size 를 1만큼 증가시킨다. 그리고 True 를 반환한다.
 1def enQueue(self, value: int):
 2    if self.size == self.max_size:    # 1
 3        return False
 4    else:
 5        if self.rear == -1:    # 2
 6            self.rear = self.front = 0
 7        else:    # 3
 8            self.rear = (self.rear + 1) % self.max_size
 9        self.queue_list[self.rear] = value    # 4
10        self.size += 1
11        return True

deQueue()

deQueue() 는 Circular Queue에 값을 삭제하는 함수이다.

deQueue() 는 boolean을 반환한다. 값을 제거하는게 성공하면 True 를 반환하고, 실패하면 False 를 반환한다.

1def deQueue(self):
2        if self.size == 0: return False
3        if self.front == self.rear:
4            self.front = self.rear = -1
5        else:
6            self.front = (self.front + 1) % self.max_size
7        self.size -= 1
8        return True

Front()

Front() 는 현재 start pointer가 가리키고 있는 값을 반환한다.

1def Front(self):
2        return self.queue_list[self.front] if self.size != 0 else -1

Rear()

Rear() 는 현재 end pointer가 가리키고 있는 값을 반환한다.

1def Rear(self) -> int:
2        return self.queue_list[self.rear] if self.size != 0 else -1

isEmpty()

isEmpty() 는 현재 값이 비어 있는지 아닌지 확인한다.

1def isEmpty(self) -> bool:
2        return self.size == 0

isFull()

isFull() 은 리스트에 값이 가득 차 있는지 아닌지 확인한다.

1def isFull(self):
2        return self.size == self.max_size

전체 코드

 1
 2class MyCircularQueue:
 3    def __init__(self, k: int):
 4        self.size = 0
 5        self.max_size = k
 6        self.queue_list = [0] * k
 7        self.front = self.rear = -1
 8
 9    def enQueue(self, value: int) -> bool:
10        if self.size == self.max_size:
11            return False
12        else:
13            if self.rear == -1:
14                self.rear = self.front = 0
15            else:
16                self.rear = (self.rear + 1) % self.max_size
17            self.queue_list[self.rear] = value
18            self.size += 1
19            return True
20
21    def deQueue(self) -> bool:
22        if self.size == 0: return False
23        if self.front == self.rear:
24            self.front = self.rear = -1
25        else:
26            self.front = (self.front + 1) % self.max_size
27        self.size -= 1
28        return True
29
30    def Front(self) -> int:
31        return self.queue_list[self.front] if self.size != 0 else -1
32
33    def Rear(self) -> int:
34        return self.queue_list[self.rear] if self.size != 0 else -1
35
36    def isEmpty(self) -> bool:
37        return self.size == 0
38
39    def isFull(self) -> bool:
40        return self.size == self.max_size