[LeetCode]원형 큐 디자인

Design Circular Queue - LeetCode

개념 : 배열기반의 큐로 구현해보기

• 배열 기반의 큐 인 경우
  • 기존의 큐는 공간이 꽉 차게 되면 더 이상 요소를 추가할 수 없었다. 심지어 앞쪽 요소들이 모두 빠져 충분한 공간이 생기더라도, 그쪽으로는 추가할 방법이 없었다. ( 지금 이렇게 말하는 건, 배열!!! 이기 때문에 )
  • 하지만 원형큐의 경우 앞쪽에 공간이 남아 있다면, 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용 가능한 구조가 된다.
  • 동작하는 원리는 “투 포인터처럼 생각” 하면 된다.
  • 큐에서는 front, rear 이 존재하니 , 이에 대한 투 포인터를 두고 움직이면 된다.
• 정해진 크기의 배열을 생성
• rear, front 라는 두가지 포인터를 두는데,
  • rear : 다음에 원소를 넣을 위치를 가리킨다.
  • front : 다음에 꺼낼 원소의 위치를 가치킨다.
  • rear, front 초기값은 0으로 한다.
• 하나의 배열을 원형인 것 처럼 사용하기 위해서는, modulo를 사용해야 한다
• 큐가 비어있을 때, 꽉 차 있을 때 는 어떻게 아는가??
  • 꽉 차 있으면 → rear에 값이 존재함
  • 비어있으면 → front에 값이 존재하지 않음.
• Enqueue
  • rear 에다가 추가를 하는데
  1. rear가 비어있지 않으면 → false ( 즉, 꽉 차 있다. )
  2. rear에 추가
  3. (rear++)% size
• Dequeue
  • front의 값을 제거하는데
  1. front가 비어있다면 → false ( 즉, 비어있다. )
  2. front의 값을 초기화
  3. (front++)%size

class MyCircularQueue {
    
    int[] arr;
    int front;
    int rear;
    int n;
    private final int INIT_NUMB = -1; 
    
    public MyCircularQueue(int k) {
        arr = new int[k]; 
        // -1로 초기화 
        Arrays.fill(arr,INIT_NUMB);
        n = k;
        front = 0;
        rear = 0; 
    }
    
    // rear를 움직인다. 
    public boolean enQueue(int value) {
        // 먼저, full인지 확인
        if(isFull()) return false;
        // rear 에 값을 넣는다. 
        arr[rear] = value;
        // rear 값을 업데이트 한다 
        rear = (rear+1)%n;
        return true;
    }
    
    public boolean deQueue() {
        // 먼저, empty인지 확인
        if(isEmpty()) return false;
        // front에 -1을 넣는다.
        arr[front] = INIT_NUMB;
        // front의 값을 업데이트 한다. 
        front = (front+1)%n;
        return true;
    }
    
    public int Front() {
        // empty인지 확인
        if(isEmpty()) return -1;
        return arr[front];
    }
    
    public int Rear() {
        // empty인지 확인
        if(isEmpty()) return -1;
        if(rear == 0) return arr[n-1];
        else return arr[rear-1];
    }
    
    public boolean isEmpty() {
        if(arr[front] == INIT_NUMB) return true;
        else return false;
    }
    
    public boolean isFull() {
        if(arr[rear]!=INIT_NUMB) return true;
        else return false;
    }
}

JAVA를 사용할 때 고민 되었던 부분

Primitive type인 int의 배열로 구현하는 것을 생각했었다.

이 때의 문제점은 → Dequeue연산을 할 때, 값을 제거해 주는 부분이었다.

어쩔 수 없이, 문제조건에서, value의 범위가 아닌 값으로 덮어씌움으로서 제거한다는 표현을 했었다.

• size는 어떻게 구할까??
  • 문제에서는 size 까지 계산하는 것은 나오지 않았다.
  • 위의 방식으로 구현할 경우

if front < rear : rear - front
else : max - front + rear 

python

class MyCircularQueue:
    
    def __init__(self, k: int):
        self.q = [None]*k
        self.maxlen = k
        self.f = 0
        self.r = 0

    # rear 이동
    def enQueue(self, value: int) -> bool:
        # rear 자리가 비어있다면 
        if self.q[self.r] is None:
            self.q[self.r] = value
            self.r = (self.r + 1) % self.maxlen 
            return True
        else:
            return False
    # front 이동
    def deQueue(self) -> bool:
        # front 가 비어있으면 False
        if self.q[self.f] is None:
            return False
        else:
            self.q[self.f] = None
            self.f = (self.f + 1) % self.maxlen
            return True

    def Front(self) -> int:
        return -1 if self.q[self.f] is None else self.q[self.f]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        if self.r == 0:
            return self.q[self.maxlen-1]
        else:
            return self.q[self.r-1]
    
        
    # front가 비어있다면 -> Empty 
    def isEmpty(self) -> bool:
        if self.q[self.f] is None:
            return True
        else:
            return False
    # Rear가 꽉 차있다면 -> Full
    def isFull(self) -> bool:
        if self.q[self.r] is None:
            return False
        else:
            return True

Deque

• Double Ended queue 로, queue와 비슷한 자료구조인데, “삽입과 제거” 가 양 쪽(front, rear) 모두에서 가능한 것 .
  • JAVA의 경우, LinkedList 를 통해 많은 것을 구현 가능..