[자료구조] 원형 큐 (Circular Queue) 구현

알고리즘 문제를 풀어보다 leetcode의 원형 큐 구현 문제( Design Circular Queue )를 만났다.

과거 큐를 공부하면서 원형 큐에 대한 구현을 해봐야겠다는 생각을 항상 미루고 있었는데 이번 기회에 이를 학습하였다.

회전 큐를 만드는 과정이 다음과 같다고 생각하였다

 

이를 왜 사용할까 생각해 보았을때, 기존 큐의 경우 삽입, 출력 과정에서 배열의 크기가 변경되며 O(n)의 시간복잡도를 요구한다. 하지만 회전 큐에 경우 정해놓은 메모리 사이즈에서 index로 접근해 값을 변경하기 때문에 메모리의 크기는 변경되지 않아 메모리를 효율적으로 사용하는 경우에 필요로 하다고 생각한다.

 

 

자세한 개념은 해당 블로그를 참조하였다.

[Data Structure] ① 원형 큐(Circular Queue) 알아보기

 

초기값 

---

class MyCircularQueue:

    def __init__(self, k: int):
        self.front = 0
        self.rear = 0
        self.que = [None] * k  
        self.max_len = k

투포인터를 이용해서 처음값과 이동할 값, 배열을 만들어준다.

 

 

큐 상태 확인

---

    def isEmpty(self) -> bool:
        return self.front == self.rear and self.que[self.front] == None
        

    def isFull(self) -> bool:
        return self.front == self.rear and self.que[self.front] != None

isEmpty -> 큐가 비어있는지 확인한다. rear포인터와 front 포인터가 일치하고,  que[front]에 값이 없다면 비어있는 상태 

isFull -> 큐가 차있는지 확인한다. rear포인터와 front 포인터가 일치하고, que[front] 에 값이 존재한다면 가득 차있는 상태

 

 

값 삽입 (enQueue)

---

    def enQueue(self, value: int) -> bool:
        if not self.isFull():
            self.que[self.rear] = value
            self.rear = (self.rear + 1) % self.max_len
            return True
        else:
            return False

 

큐에 값을 삽입하는 과정으로 큐가 isFull 상태가 아니면

rear포인터에 값을 변경하고 rear포인터의 위치를 +1 이동시킨다.

 

 

값 삭제 (deQueue)

---

    def deQueue(self) -> bool:
        if not self.isEmpty():
            self.que[self.front] = None
            self.front = (self.front +1) % self.max_len
            return True
        else:
            return False

 

큐의 첫번째 값을 제거하는 과정으로 큐가 isEmpty 상태가 아니면

front포인터의 값을 None으로 변경 후 front 포인터를 +1 이동한다.

 

첫번째 값 확인 (Front) , 마지막 값 확인 (Rear)

---

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

  def Rear(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.que[self.rear - 1]

 

 

전체 코드

---

class MyCircularQueue:

    def __init__(self, k: int):
        self.front = 0
        self.rear = 0
        self.que = [None] * k  
        self.max_len = k 
        

    def enQueue(self, value: int) -> bool:
        if not self.isFull():
            self.que[self.rear] = value
            self.rear = (self.rear + 1) % self.max_len
            return True
        else:
            return False

    def deQueue(self) -> bool:
        if not self.isEmpty():
            self.que[self.front] = None
            self.front = (self.front +1) % self.max_len
            return True
        else:
            return False

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

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.que[self.rear - 1]

    def isEmpty(self) -> bool:
        return self.front == self.rear and self.que[self.front] == None
        

    def isFull(self) -> bool:
        return self.front == self.rear and self.que[self.front] != None

 

감사합니다.

---

 

 

---

참고

파이썬 알고리즘 인터뷰 - 예스24

Design Circular Queue - LeetCode

[Data Structure] ① 원형 큐(Circular Queue) 알아보기