MAX_QSIZE = 10
class CircularQueue :
def __init__(self):
self.front = 0
self.rear = 0
self.items = [None] * MAX_QSIZE
MAX_QSIZE를 사용하여 원형 큐의 크기를 지정해준다.
이후에 원형 큐 클레스를 작성하고 __init__
메소드를 사용해서 원형큐에 필요한 front와 rear을 선언해준다. item은 파이썬의 list를 사요하여 None으로 큐의 크기만큼 만들어준다.
def isEmpty(self):
return self.front == self.rear
큐가 비었는지 확인한다.
front와 rear가 같은 위치를 가르키고 있다면 큐가 비어있는 것이다.
def isFull(self):
return self.front == (self.rear+1)%MAX_QSIZE
큐가 꽉 찼는지 판단한다.
이처럼 rear가 가르키는 인덱스의 다음 인덱스를 front가 가르키고 있다면 원형 큐는 꽉 찼다고 말한다.
큐의 크기와 나머지 연산을 사용해서 rear가 가르키고 있는 인덱스를 찾아서 판단한다.
def clear(self):
self.front = self.rear
큐를 초기화 하기 위해서는 front를 rear가 가르키고 있는 인덱스로 가게해서 원형 큐의 초기상태를 만들어준다.
def enqueue(self, item):
if not self.isFull():
self.rear = (self.rear + 1) % MAX_QSIZE
self.items[self.rear] = item
원형 큐에 데이터를 삽입하기 전에 큐가 포화상태인지 먼저 판단한다.
포화상태가 아니라면 rear를 한칸 옮기고 rear가르키고 있는 인덱스에 값을 저장한다.
def dequeue(self):
if not self.isEmpty():
self.front = (self.front+1) % MAX_QSIZE
return self.items[self.front]
원형 큐에서 데이터를 지우기 위해서는 먼저 큐가 비어있는지 판단한다.
큐가 비어있지 않다면 front를 옮겨줌으로써 큐 안에 있는 데이터를 지운다.
이후 비어지는 데이터를 반환한다.
def peek(self):
if not self.isEmpty():
return self.items[(self.front+1)%MAX_QSIZE]
원형큐가 비어있는지 먼저 판단하고 front의 다음 인덱스 안에 있는 값을 반환한다.
큐 크기와 나머지 연산을 사용해 인덱스를 계산할 수 있다.
Queue는 데이터를 넣는 방향과 빼는 방향이 따로 정해져있다.
Deque는 양쪽에서 데이터를 삽입하고 추출할 수 있다.
때문에 CircularDeque를 구현할 때에도 CircularQueue를 상속받아서 front와 Rear에서 각각 데이터를 삽입하고 꺼내는 메소드만 추가해주면 된다.
MAX_QSIZE = 10
class CircularQueue :
def __init__(self):
self.front = 0
self.rear = 0
self.items = [None] * MAX_QSIZE
def isEmpty(self):
return self.front == self.rear
def isFull(self):
return self.front == (self.rear+1)%MAX_QSIZE
def clear(self):
self.front = self.rear
def __len__(self):
return (self.rear - self.front + MAX_QSIZE) % MAX_QSIZE
def enqueue(self, item):
if not self.isFull():
self.rear = (self.rear + 1) % MAX_QSIZE
self.items[self.rear] = item
def dequeue(self):
if not self.isEmpty():
self.front = (self.front+1) % MAX_QSIZE
return self.items[self.front]
def peek(self):
if not self.isEmpty():
return self.items[(self.front+1)%MAX_QSIZE]
def print(self):
out = []
if self.front < self.rear:
out = self.items[self.front+1:self.rear+1]
else:
out = self.items[self.front+1:MAX_QSIZE] + self.items[0:self.rear+1]
print("[f=%s, r=%d] ==> "%(self.front, self.rear), out)
class CircularDeque(CircularQueue):
def __init__(self):
super().__init__()
def addRear (self, item):
self.enqueue(item)
def deleteFront (self):
return self.dequeue()
def getFront(self):
return self.peek()
def addFront(self, item):
if not self.isFull():
self.items[self.front] = item
self.front = (self.front - 1 + MAX_QSIZE) % MAX_QSIZE
def deleteRear(self):
if not self.isEmpty():
item = self.items[self.rear]
self.rear = (self.rear - 1 + MAX_QSIZE) % MAX_QSIZE
return item
def getRear(self):
return self.items[self.rear]