[자료구조] 큐(Queue)란?

Queue

큐는 '선입선출' , FIFO(First In First Out)의 개념을 가진 선행 자료구조이다. 스택은 입구와 출구가 동일하여 나중에 들어온 순서대로 나가는 구조지만, 큐는 입구와 출구가 달라 먼저 들어온 데이터가 먼저 나가는 구조이다.

놀이공원에서 놀이기구를 타기 위해서는 줄을 서야 하고 줄을 슨 순서대로 놀이기구에 탑승하게 된다. 이와 같은 예가 큐(Queue)이다.

큐(Queue)의 주요 동작들

• enQueue : 큐에 데이터를 넣는다.
• edQueue : 큐에서 데이터를 빼낸다. (먼저 들어온 데이터 순)
• isEmpty : 큐가 비어있는지 확인한다.
• isFull : 큐가 꽉 차 있는지 확인한다.
• peek : 가장 앞(front)에 있는 데이터를 반환한다.
• front : 큐의 맨 앞 데이터 위치(index)
• rear : 큐의 맨 뒤 데이터 위치(index)

큐(Queue)의 종류

• Linear Queue (선형 큐)
• Circular Queue (원형 큐)
• Priority Queue (우선순위 큐)

Linear Queue (선형 큐)

• 가장 기본적인 큐의 형태이다.
• 선형 큐는 배열, 연결리스트로 표현할 수 있다.
• 큐에서 deQueue() 함수를 사용하면 맨 앞에 있는 값이 반환되며 제거된다. 이때 front 값이 front += 1 되어 한칸씩 밀려나게 되어 큐의 가용범위가 줄어들고, 큐의 재사용 또한 불가능하게 된다는 문제점이 있다.

선형 큐 Array로 구현

class Queue {
    constructor() {
        this.queue = [];
        this.front = 0;
        this.rear = 0;
    }

    enqueue(value) {
        this.queue[this.rear++] = value;
    }

    dequeue() {
        const value = this.queue[this.front];
        delete this.queue[this.front++]
        return value;
    }

    peek() {
        return this.queue[this.front];
    }

    size() {
        return this.rear - this.front;
    }
}

선형 큐 LinkedList로 구현

class Node {
    constructor(value) {
        this.next = null;
        this.value = value;
    }
}

class Queue {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    enqueue(value) {
        const newNode = new Node(value);
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.size++;
    }

    dequeue() {
        const value = this.head.value;
        this.head = this.head.next;
        this.size--;
        return value;
    }

    peek() {
        return this.head.value;
    }
}

선형 큐의 문제점

큐에서 deQueue() 함수를 사용하면 맨 앞에 있는 값이 반환되며 제거된다. 이때 front 값이 front += 1 되어 한 칸씩 밀려나게 되어 큐의 가용 범위가 줄어들고, 데이터가 꽉 차게 된다면 더 이상 공간을 활용할 수 없게 된다. 이 방식을 해결하기 위해서는 deQueue 되었을 때 front 값은 고정시키고 뒤에 있는 데이터들의 index를 한 칸씩 당기는 방법밖에 없다. 이 문제점을 보완하기 위해 나온 것이 원형 큐이다.

Circular Queue (원형 큐)

• 선형 큐의 문제점을 보완할 수 있는 큐로 원형 큐가 있다. 기존의 큐는 직선 형태로 구현되었지만, 원형 큐는 이름 그대로 원형으로 연결되어 있는 구조를 갖는다.
• 원형 큐는 1차원 배열 형태로 큐를 원형으로 구성하여 배열의 처음과 끝을 연결하여 만든다.
• 삽입/삭제 연산에서, 변경되는 front와 rear 값이 가리키는 위치가 마지막 index에서 다시 처음 index로 돌아오게 되는 경우를 위해 나머지 연산자((front + 1) % maxSize)를 사용한다.

class CircularQueue {
    constructor(maxSize) {
        this.maxSize = maxSize;
        this.queue = [];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    enqueue(value) {
        if (this.isFull()) {
            console.log('Queue if Full');
            return;
        }
        this.queue[this.rear] = value;
        this.rear = (this.rear + 1) % this.maxSize
        this.size += 1;
    }

    dequeue() {
        const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front = (this.front + 1) % this.maxSize;
        this.size -= 1;
        return value;
    }

    isFull() {
        return this.size === this.maxSize;
    }

    peek() {
        return this.queue[this.front];
    }
}

Priority Queue (우선순위 큐)

• 우선순위 큐는 일반적인 큐(FIFO)와 다르게 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조를 말한다.
• 우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다.