[javascript] 원형큐 만들기

선형큐는 enque로 인하여 rear가 max_size 까지 갔다면 공간이 배열에 빈공간이 있더라도 front와 rear를 초기해주지 않는 이상 enqueue를 할 수 없다. 그런 단점을 극복한 것이 원형큐이다. 원형큐는 선형큐와 달리 원형의 모양을 하고 있으며 이 queue의 공간에 아이템이 꽉 차지 않는 이상 언제든 enque와 deque를 할 수 있다. 

 

 

원형큐 설명

 

원형 큐가 공백인 상황

 

원형 큐는 enque와 deque의 형태가 조금 다른데 그 이유는 max_size 까지 가면 front와 rear가 0 부터 다시 처음부터 시작해야 하기 때문이다. 또한 front는 항상 item이 있는 곳 앞에 존재한다. 

 

원형큐의 멤버변수 

 

 constructor(size){
        this.maxQueueSize = size;
        this.array = [];
        this.front = 0;
        this.rear = 0;
    }

 

원형큐의 공백과 포화상태 확인

 

  isEmpyt(){
        return this.front == this.rear;
    }

    isFull(){
        return (this.rear +1) % this.maxQueueSize == this.front;
    }

 

포화상태

공백상태

코드에서 보면 해당 로직이 맞는지 값을 불리언으로 return 하는데 이유는 if문으로 저 긴 문구를 적으려 하니 코드가 이상해지고 enque가 item을 넣는 일 이외에 공백상태나 포화상태까지 확인하는 구조가 되어버렸기 때문이다. 

 

enqueue와 dequeue

  enQueue(item){
        if(this.isFull()){
            console.log(new Error("큐가 포화상태입니다."))
        }else{
            this.rear = (this.rear + 1) % this.maxQueueSize;
            this.array[this.rear] =  item;
        }
    }

    deQueue(){
        if(this.isEmpyt()){
            console.log(new Error("큐가 비었습니다."));
        }else{
            this.front = (this.front + 1) % this.maxQueueSize;
            return this.array[this.front];
        }
    }

 

 

enque시 (rear + 1 ) % maxQueueSize 의 값을 rear에 할당하고 해당 자리에 item을 넣는다. 

 

deque시 (front +1) % maxQueueSize의 값을 front에 할당하고 해당 자리에 있는 item을 리턴한다. 

 

 

전체

class CircleQueue{
    constructor(size){
        this.maxQueueSize = size;
        this.array = [];
        this.front = 0;
        this.rear = 0;
    }

    isEmpyt(){
        return this.front == this.rear;
    }

    isFull(){
        return (this.rear +1) % this.maxQueueSize == this.front;
    }
    enQueue(item){
        if(this.isFull()){
            console.log(new Error("큐가 포화상태입니다."))
        }else{
            this.rear = (this.rear + 1) % this.maxQueueSize;
            this.array[this.rear] =  item;
        }
    }

    deQueue(){
        if(this.isEmpyt()){
            console.log(new Error("큐가 비었습니다."));
        }else{
            this.front = (this.front + 1) % this.maxQueueSize;
            return this.array[this.front];
        }
    }

    print(){
        if(this.isEmpyt()){
            console.log(new Error("큐가 비었습니다."));
        }
        let string = "";
        let i = this.front;
        do{
            i = (i+1) % this.maxQueueSize;
            string += this.array[i] + "|";
            if(i == this.rear){
                console.log(string);
                break;
            }
        }while(i != this.front);
    }
}

let queue = new CircleQueue(5);

queue.enQueue(1);
queue.enQueue(2);
queue.enQueue(3);
queue.enQueue(4);
queue.deQueue();
queue.enQueue(5);

queue.print();