[Udemy] 큐(Queue)란?

정의

큐(Queue)는 선입선출 특징을 가진 선형 자료구조이다.

매표소에 줄 서기, 편의점 진열 매대 등 일생활 대부분에서 사용되는 자료구조이다.

 

코드 및 구현

1. 배열로 구현

배열 메서드를 통해 구현할 수 있다.

const queue = [];

queue.push(1);
queue.push(2);
queue.push(3);

queue.shift(); // 1
queue.shift(); // 2
queue.shift(); // 3

// or

queue.unshift('a');
queue.unshift('b');
queue.unshift('c');

queue.pop(); // a
queue.pop(); // b
queue.pop(); // c

 

큐를 배열로 구현할 때 주의할 점은 선입선출을 지켜줘야 한다는 것이다.

push 메서드로 데이터를 넣은 후 데이터를 빼낼 때에도

가장 먼저 넣은 데이터부터 빠지도록 shift 메서드를 사용한다.

 

unshift 메서드로 시작부분에서 데이터를 넣은 후 빼낼 때에도

가장 먼저 넣은 데이터부터 빠지도록 pop 메서드를 사용한다.

 

 

2. 연결 리스트로 구현

Node 객체와 연결 리스트를 통해 구현할 수 있다.

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

class Queue {
    constructor() {
        this.first = null;
        this.last = null;
        this.size = 0;
    }

    enqueue(val) {
        let node = new Node(val);
        if (!this.first) {
           this.first = node;
           this.last = node;
        } else {
           this.last.next = node;
           this.last = node;
        }
        return ++this.size;
    }

    dequeue() {
        if (!this.first) return null;

        let temp = this.first;
        if (this.first === this.last) {
            this.last = null;
        }
        this.first = this.first.next;
        this.size--;
        return temp.value;
    }
}

 

큐에 데이터를 넣은 enqueue 메서드는 단일 연결 리스트의 push 메서드와 로직이 동일하다.

큐에 데이터를 빼는 dequeue 메서드는 스택의 pop 메서드와 로직이 동일하다.

 

 

시간 복잡도

삽입 및 제거 - O(1)

검색 및 접근 - O(n)

 

큐의 시간 복잡도 역시 스택과 마찬가지로, 삽입과 제거 시에는 상수 시간 복잡도를 가진다.

반면, 검색과 접근 시에는 O(n)의 시간 복잡도를 갖는다.

 

 

참조

Udemy - Js 알고리즘 & 자료구조 강의