Python 알고리즘 인터뷰 - 문제25. 원형 큐 디자인

leetcode 422. Design Circular Queue - https://leetcode.com/problems/design-circular-queue/description/

 

원형 큐를 디자인하라.

 

예제

다음과 같이 동작해야한다.

myCircularQueue = MyCircularQueue(3);
myCircularQueue.enQueue(1); # return True
myCircularQueue.enQueue(2); # return True
myCircularQueue.enQueue(3); # return True
myCircularQueue.enQueue(4); # return False
myCircularQueue.Rear();     # return 3
myCircularQueue.isFull();   # return True
myCircularQueue.deQueue();  # return True
myCircularQueue.enQueue(4); # return True
myCircularQueue.Rear();     # return 4

 

원형큐는 큐와 거의 동일하나 마지막 위치가 시작 위치와 연결된다. 동작 원리는 다음과 같다.

먼저 MyCircularQueue(4)로 초기화했을 때에 다음과 같이 초기화 된다. 

코드로는 다음과 같다.

class MyCircularQueue:
	def __init__(self, max_len):
    	self.q = [None] * max_len
    	self.front = 0
        self.rear = 0
        self.max_len = max_len

 

 

먼저 Enqueue를 했을 때는 다음과 같이 rear포인터에 위치한 곳에 값을 넣은 후 rear 포인터를 한칸 이동시킨다.

rear이 마지막 인덱스에 위치해 있을 경우 다음 위치는 0으로 이동해야한다. 따라서 (real(=3) + 1) % max_len(=4)을 진행하여 인덱스가 넘어가지 않도록 한다.

rear 포인터가 가리키는 값이 None아 아닌 경우는 큐가 꽉찬 경우이므로 예외처리를 한다.

enque 함수의 구현된 코드는 다음과 같다.

def enQueue(self, x):
	if self.q[self.rear] is not None:
    	return False
        
    self.q[self.rear] = x
    self.real = (self.real + 1) % max_len
    return True

 

deque 함수는 큐의 저장된 데이터를 삭제(None으로 변경)한다. 다음과 같이 값을 None으로 바꾸면서 한칸씩 전진한다.

rear과 마찬가지로 front = (front + 1) % max_len을 통해 마지막 인덱스에 위할 경우 처음 인덱스로 이동시킨다.

front의 값이 None인 경우 queue에 데이터가 없는 경우이므로 예외처리를 한다.

deque 함수의 구현된 코드는 다음과 같다.

def deQueue(self, x):
	if self.q[self.from] is None:
    	return False
        
    self.q[self.front] = None
    self.front = (self.front + 1) % max_len
    return True

 

이를 바탕으로 전체 코드를 구현한다. 코드는 다음과 같다.

class MyCircularQueue(object):
    def __init__(self, k):
        self.q = [None] * k
        self.front = 0
        self.real = 0
        self.max_len = k

    def enQueue(self, value):
        if self.q[self.real] is not None:
            return False

        self.q[self.real] = value
        self.real = (self.real + 1) % self.max_len
        return True

    def deQueue(self):
        if self.q[self.front] is None:
            return False

        self.q[self.front] = None
        self.front = (self.front + 1) % self.max_len
        return True

    def Front(self):
        return -1 if self.isEmpty() else self.q[self.front]

    def Rear(self):
        return -1 if self.isEmpty() else self.q[self.real - 1]

    def isEmpty(self):
        return self.real == self.front and self.q[self.front] is None

    def isFull(self):
        return self.real == self.front and self.q[self.front] is not None