[자료구조] 큐(Queue)

zzzzsb·2022년 7월 15일

자료구조&알고리즘

목록 보기

2/11

큐(Queue)

큐의 개념

스택과 마찬가지로 선형(linear) 자료구조
큐는 스택과 다르게 한쪽 방향에서 삽입이, 반대편에서 삭제가 이루어지는 선입선출(FIFO, First In First Out) 구조를 가진다.
즉, 먼저 들어온 데이터가 먼저 나가는 구조이다.
데이터가 삭제될 위치를 Front/Head, 마지막 데이터가 삽입된 위치를 Rear/Tail 이라 부른다.
양 방향에서 삽입과 삭제 모두 이루어지는 큐를 덱(Deque)이라고 한다.

큐의 기본 연산

Enqueue: 큐 맨 뒤에 요소를 추가
Dequeue: 큐 맨 앞의 요소를 삭제
Peek: front에 위치한 데이터를 확인
front: 큐의 맨 앞 위치
rear: 큐의 맨 뒤 위치

큐 구현 with JavaScript

다른 언어의 경우 내장 라이브러리에서 큐를 제공하고 있다.(C++/Java 등)
하지만 자바스크립트는 큐를 제공하고 있지 않기에, 직접 구현이 필요하다.

배열로 큐 구현

자바스크립트에서는 배열을 이용해 큐의 기능을 흉내낼 수 있다.
자바스크립트의 배열 내장 메서드 중 shift() 메서드는, 배열의 가장 앞에있는 원소부터 하나씩 제거하는 기능을 수행한다. 즉, 큐의 연산 중 Dequeue과 동일하다.

class Queue {
  constructor() {
    this._arr = [];
  }
  enqueue(item) {
    this._arr.push(item);
  }
  dequeue() {
    return this._arr.shift();
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.dequeue(); // 1

하지만, shift() 메서드로 맨 앞의 요소를 하나씩 제거할때, 시간복잡도는 O(N)이 소요된다.
shift() 메서드는 배열의 첫번째 원소를 배열에서 제거하고, 나머지 배열의 원소들을 앞으로 한 칸씩 당겨주기 때문이다.

마지막 위치 재조정 과정에서 연산이 추가적으로 소요되기 때문에, 자바스크립트에서 배열로 큐의 기능을 흉내내는 방식은 다른 언어에서의 큐 자료구조보다 더 많은 시간복잡도를 요구한다.

위와 같이 배열을 이용해 첫번째 요소에 접근하는 경우 O(N)
연결리스트를 사용해 첫번째 원소에 접근하는 경우 O(1)

보통 BFS 같은 문제에서 큐를 활용해 문제를 풀어야 하는 경우 위와 같이 배열을 이용한 방식으로도 통과가 가능한 경우가 많다. 하지만 시간복잡도를 세세하게 관리해야 하거나, 데이터의 양이 매우 크다면 위와 같은 방식 대신 큐를 직접 구현하여 더 빠른 시간복잡도로 문제에 접근해야 할 것이다.

객체(해시)로 큐 구현

자바스크립트에서 객체(Object)는 key-value의 구조로 사용할 수 있으며, key값을 통해 O(1) 시간으로 요소에 접근할 수 있다.

큐에서 핵심이 되는 포인터는 2개가 있다.

front: 큐에서 가장 첫번째 요소
rear: 큐에서 가장 마지막 요소

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  
  size() {
    if (this.storage[this.rear] === undefined) {
      return 0;
    } else {
      return this.rear - this.rear + 1;
    }
  }
  
  add(value) {
    if (this.size() === 0) {
      this.storage['0'] = value;
    } else {
      this.rear += 1;
      this.storage[this.rear] = value;
    }
  }
  
  popleft() {
    let temp;
    if (this.front === this.rear) {
      temp = this.storage[this.front];
      delete this.storage[this.front];
      this.front = 0;
      this.rear = 0;
    } else {
      temp = this.storage[this.front];
      delete this.storage[this.front];
      this.front += 1;
    }
    return temp;
  }
}