Queue

큐(Queue)란?

• Queue란 Stack과 마찬가지로 작업이 수행되는 특정 순서를 따르는 선형 구조이다.
• 선입선출(FIFO: First In First Out) 구조를 따른다.
• 스택과 큐의 차이점은 제거 방식에 있다. Stack에서는 가장 최근에 추가된 항목을 제거하지만, Queue에서는 가장 처음에 추가된 항목부터 제거한다.
• Queue에서는 주로 아래 네 가지 기본 작업이 수행된다.
  • Enqueue: 큐에 항목을 추가한다. (큐가 가득 차면 Overflow condition)
  • Dequeue: 먼저 항목이 추가된 순서대로 큐에서 항목을 제거한다. 큐가 비어 있으면 Underflow condition)
  • Front: 큐의 첫번째 항목을 가져온다.
  • Rear: 큐의 마지막 항목을 가져온다.
• 식당에서 주문 받는 예를 생각해보자. 먼저 주문한 사람이 먼저 음식을 받는다. 이러한 주문 대기열을 Queue라고 생각하자.

Queue의 기본 구조

Queue 생성

 

• JS에서 큐는 Array를 사용하거나 Linked List를 사용해서 구현할 수 있다.
• Array로 생성하면 더욱 간단하다.

Queue를 Array로 생성하기

// Queue class
class Queue {
    // Array를 사용하여 Queue를 구현
    constructor() {
        this.queue = [];
    }

    // queue에 항목 추가
    enqueue(element) {
        this.queue.push(element);
    }

    // queue에서 항목 제거
    dequeue() {
        // 큐가 비어있으면 'underflow'
        if(this.isEmpty()) {
            return "Underflow";
        }
        return this.queue.shift();
    }

    // queue에 첫번째 항목
    front() {
        if(this.isEmpty()) {
            return "No elements in Queue";
        }
        return this.queue[0];
    }

    // queue에 마지막 항목
    rear() {
        return this.queue[this.queue.length - 1];
    }
    // queue가 비었는지 확인
    // 비었다면 true
    isEmpty() {
        return this.queue.length === 0;
    }

    // queue를 출력하는 함수
    printQueue()
    {
        let string = "";
        for(let i = 0; i < this.queue.length; i++)
            string += `${this.queue[i]} `;
        return string;
    }
}

// 새로운 큐 생성
const queue = new Queue();

// 현재 큐는 빈 상태
// returns Underflow
console.log(queue.dequeue()); // Underflow
console.log(queue.isEmpty()); // true

// Adding elements to the queue
// queue contains [10, 20, 30, 40, 50]
queue.enqueue(10); // 현재 큐의 상태: [10]
queue.enqueue(20); // 현재 큐의 상태: [10, 20]
queue.enqueue(30); // 현재 큐의 상태: [10, 20, 30]
queue.enqueue(40); // 현재 큐의 상태: [10, 20, 30, 40]
queue.enqueue(50); // 현재 큐의 상태: [10, 20, 30, 40, 50]
queue.enqueue(60); // 현재 큐의 상태: [10, 20, 30, 40, 50, 60]
console.log(queue.printQueue()); // 10 20 30 40 50 60
console.log(queue.isEmpty()); // false


console.log(queue.front()); // 10
console.log(queue.rear());  // 60

// 큐에서 10을 삭제
console.log(queue.dequeue()); // 현재 큐의 상태: [20, 30, 40, 50, 60]

console.log(queue.front()); // 20
console.log(queue.rear());  // 60

// 큐에서 20을 삭제
console.log(queue.dequeue()); // 현재 큐의 상태: [30, 40, 50, 60]

console.log(queue.printQueue()); // 30 40 50 60

 

사용된 전체 코드

https://github.com/rkdden/Data-Structure/blob/main/queue.js

GitHub - rkdden/Data-Structure

출처

https://www.geeksforgeeks.org/queue-set-1introduction-and-array-implementation/?ref=lbp 

Queue | Set 1 (Introduction and Array Implementation) - GeeksforGeeks