[Leetcode] - 622

• Queue의 기본 동작

  • enqueue(), dequeue(), is_full(), is_empty()

• Linear Queue (선형 큐, Array를 사용한 큐 구현)

  • front, rear pointer로 arr의 시작, 끝 원소를 가리킴
  • dequeue() 반복 수행시 arr의 앞 공간이 비게 되어 메모리 낭비
  • dequeue() 수행시 element를 앞으로 전부 당기는 동작이 필요

• Circular Queue (원형 큐, Array를 사용한 큐 구현)

  • front pointer: arr의 시작 원소, rear pointer: arr의 마지막 원소 + 1
  • is_full, is_empty 상태를 구분하기 위해 size + 1 의 arr를 생성함
  • front == rear : empty 상태, front == rear + 1: full 상태
  • arr idx 계산 시 mod 연산 사용

class MyCircularQueue:

    def __init__(self, k: int):
        self.sz = k+1
        self.arr = [0 for _ in range(k+1)]
        self.front = 0
        self.rear = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        
        self.arr[self.rear] = value
        self.rear = (self.rear + 1) % self.sz
        return True
    
    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        
        self.arr[self.front] = 0
        self.front = (self.front + 1) % self.sz
        return True
    
    def Front(self) -> int:
        if self.isEmpty():
            return -1
        
        front_idx = self.front % self.sz
        return self.arr[front_idx]        

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        
        rear_idx = (self.rear-1) % self.sz
        return self.arr[rear_idx]
        

    def isEmpty(self) -> bool:
        if self.front == self.rear:
            return True
        return False

    def isFull(self) -> bool:
        if (self.rear + 1) % self.sz == self.front:
            return True
        return False


# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()