큐(Queue)는 데이터를 넣고빼는 자료구조 중 하나로, 먼저 삽입된 데이터가 먼저 추출되는 FIFO(First In First Out) 구조를 가지고 있다. 큐는 Front, Rear라는 두개의 포인터를 사용하여 데이터를 관리한다.
Front : 다음 추출될 데이터를 가리킨다.
Rear : 다음 데이터가 저장될 공간을 가리킨다.
데이터를 삽입하는 행위를 enque, 추출하는 행위를 deque라고 부른다. enque 및 deque 실행 시 포인터 관리에 유의해야 한다.
(구현 방법에 따라 포인터의 증감 순서는 조금씩 다를 수 있다.)
1. 변수
1) Capacity : 크기
2) Front : 큐의 맨 앞
3) Rear : 큐의 맨 뒤
4) No : 큐에 들어있는 데이터의 갯수
2. 함수
1) enque() : 큐에 데이터를 넣는 함수
2) deque() : 큐에서 데이터를 빼는 함수
3) __len__() : 큐에 넣어있는 데이터의 갯수를 반환하는 함수
4) dump() : 큐 안에 있는 데이터를 순차적으로 모두 읽는 함수
5) peek() : 맨 앞 데이터를 들여다보는 함수
6) find() : 큐에서 특정 값을 찾아 인덱스를 반환하는 함수
7) count() : 큐 안에서 특정 값의 갯수를 찾아 반환하는 함수
8) contains() : 큐 안에 특정 값의 존재 여부를 찾아 반환하는 함수
9) clear() : 큐를 초기화하는 함수
10) is_full() : 큐가 가득 찼는지 확인하는 함수
11) is_empty() : 큐가 비었는지 확인하는 함수
3. Exception
1) Empty : 큐가 빈 경우 발생하는 Exception
2) Full : 큐가 가득 찬 경우 발생하는 Exception
* 구현 내용
class FixedQueue:
class Full(Exception):
pass
class Empty(Exception):
pass
def __init__(self, c : int):
self.capacity = c
self.front = 0
self.rear = 0
self.no = 0
self.queue = [None] * self.capacity
def is_full(self) -> bool:
if self.no >= self.capacity:
return True
else:
return False
def is_empty(self) -> bool:
if self.no <= 0:
return True
else:
return False
def enque(self, data):
if self.is_full():
raise FixedQueue.Full
self.queue[self.rear] = data
self.rear += 1
self.no += 1
if self.rear == self.capacity:
self.rear = 0
def deque(self):
if self.is_empty():
raise FixedQueue.Empty
r_data = self.queue[self.front]
self.front += 1
self.no -= 1
if self.front == self.capacity:
self.front = 0
return r_data
def __len__(self):
return self.no
def dump(self):
if self.is_empty():
print('큐가 비었습니다.')
else:
for i in range(self.no):
print(self.queue[(i + self.front)%self.capacity])
def peek(self):
if self.is_empty():
raise FixedQueue.Empty
return self.queue[self.front]
def find(self, value):
for i in range(self.no):
idx = (i + self.front) % self.capacity
if self.queue[idx] == value:
return idx
return -1
def count(self, value):
c = 0
for i in range(self.no):
idx = (i + self.front) % self.capacity
if self.queue[idx] == value:
c += 1
return c
def contains(self, value):
return self.count(value)
def clear(self):
self.no = 0
self.front = 0
self.rear = 0
'Computer Science > 자료구조' 카테고리의 다른 글
| 스택(Stack) 파이썬으로 구현하기 (0) | 2020.12.20 |
|---|
