[javascript] 선형 큐 만들기 queue

어제 만들어본 stack은 가장 늦게 넣은 것이 가장 빨리 나오는 LIFO(후입선출) 의 형태를 취하고 있다. 오늘  만들어볼 queue는 FIFO(선입선출)의 형태를 하고 있으며 원시적인 선형큐를 만들어 볼 것이다.

 

Queue 란 ?

 

큐는 데이터를 선입선출을 하는 자료구조이다.

 

queue는 우리 주변에서도 많이 보이는데 카운터에서 줄을 서고 있는 손님들이나 print의 출력에서도 queue의 형태를 볼 수 있다.

 

 

선형큐 

선형 큐란 ?

선형큐는 재사용이 되지 않는 형태의 큐이다. 배열에 공간이 남았더라도 rear가 max_size 까지 도달 했다면 배열 전체를 초기화 하지 않으면 item을 넣지 못한다.    

 

queue의 멤버변수

max_size // queue에 저장 가능한 공간을 뜻 한다. 

 

front // queue의 앞부분을 뜻한다. 아이템이 들어있는 공간 앞을 가리킨다. 

 

rear // queue에 아이템이 들어있는 마지막 공간을 뜻 한다. 

 

 constructor(size){
        this.maxSize = size;
        this.front = -1;
        this.rear = -1;
        this.array = [];
    }

 

queue의 기능 

 

enque // queue의 rear에 아이템을 추가한다. 

 

deque //  queue의 맨 앞에 해당하는 아이템을 제거하고 리턴한다. 

 

print // queue에 있는 아이템들을 가져와서 출력한다. 

 

    enque(item){
        if(this.rear != this.maxSize -1 ){
            this.array[++this.rear] = item;
        }else{
            console.log(new Error("queue is full"));
        }
    }

    deque(){
        if(this.front == this.rear){
            console.log(new Error("queue is empty"))
        }else{
            ++this.front;
            return this.array[this.front];
        }
    }
    
    print(){
        let string = "";
        for(let i = 0; i < this.maxSize ; i++){
            if(this.front >= i || i > this.rear){
                string += " | "
            }else{
                string += `${this.array[i]} | `;
            }
        }
        console.log(string);
    }

 

전체

 

class queueType{
    constructor(size){
        this.maxSize = size;
        this.front = -1;
        this.rear = -1;
        this.array = [];
    }
    enque(item){
        if(this.rear != this.maxSize -1 ){
            this.array[++this.rear] = item;
        }else{
            console.log(new Error("queue is full"));
        }
    }

    deque(){
        if(this.front == this.rear){
            console.log(new Error("queue is empty"))
        }else{
            ++this.front;
            return this.array[this.front];
        }
    }
    
    print(){
        let string = "";
        for(let i = 0; i < this.maxSize ; i++){
            if(this.front >= i || i > this.rear){
                string += " | "
            }else{
                string += `${this.array[i]} | `;
            }
        }
        console.log(string);
    }
}

let queue = new queueType(5);

queue.enque("10");
queue.enque("23");
queue.enque("32");
queue.print();
queue.deque();
queue.deque();
queue.deque();
queue.print();

 

 

결과 

 

 

좀 더 방어적으로 

 

function queueType(size){
    const maxSize = size;
    let front = -1;
    let rear = -1;
    let array = [];

    return{
        enque(item){
            if(rear != maxSize -1 ){
                array[++rear] = item;
            }else{
                console.log(new Error("queue is full"));
            }
        },
    
        deque(){
            if(front == rear){
                console.log(new Error("queue is empty"))
            }else{
                ++front;
                return array[front];
            }
        },
        
        print(){
            let string = "";
            for(let i = 0; i < maxSize ; i++){
                if(front >= i || i > rear){
                    string += " | "
                }else{
                    string += `${array[i]} | `;
                }
            }
            console.log(string);
        }
    }
}