원형 큐 (Circular Queue)

Class생성, init

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으로 큐의 크기만큼 만들어준다.

isEmpty

def isEmpty(self):
        return self.front == self.rear

큐가 비었는지 확인한다.
front와 rear가 같은 위치를 가르키고 있다면 큐가 비어있는 것이다.

isFull

def isFull(self):
        return self.front == (self.rear+1)%MAX_QSIZE

큐가 꽉 찼는지 판단한다.

이처럼 rear가 가르키는 인덱스의 다음 인덱스를 front가 가르키고 있다면 원형 큐는 꽉 찼다고 말한다.
큐의 크기와 나머지 연산을 사용해서 rear가 가르키고 있는 인덱스를 찾아서 판단한다.

clear

def clear(self):
        self.front = self.rear

큐를 초기화 하기 위해서는 front를 rear가 가르키고 있는 인덱스로 가게해서 원형 큐의 초기상태를 만들어준다.

enqueue

def enqueue(self, item):
        if not self.isFull():
            self.rear = (self.rear + 1) % MAX_QSIZE
            self.items[self.rear] = item

원형 큐에 데이터를 삽입하기 전에 큐가 포화상태인지 먼저 판단한다.
포화상태가 아니라면 rear를 한칸 옮기고 rear가르키고 있는 인덱스에 값을 저장한다.

dequeue

def dequeue(self):
        if not self.isEmpty():
            self.front = (self.front+1) % MAX_QSIZE
            return self.items[self.front]

원형 큐에서 데이터를 지우기 위해서는 먼저 큐가 비어있는지 판단한다.
큐가 비어있지 않다면 front를 옮겨줌으로써 큐 안에 있는 데이터를 지운다.
이후 비어지는 데이터를 반환한다.

peek

def peek(self):
        if not self.isEmpty():
            return self.items[(self.front+1)%MAX_QSIZE]

원형큐가 비어있는지 먼저 판단하고 front의 다음 인덱스 안에 있는 값을 반환한다.
큐 크기와 나머지 연산을 사용해 인덱스를 계산할 수 있다.

Queue와 Deque의 차이점

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]