[자료구조] Queue

1. Queue 란?

 

데이터가 한쪽 끝에서 추가가 되고, 반대쪽 끝에서 데이터가 삭제되는 형태의 자료구조.

FIFO(First In First Out)으로, 가장 먼저 들어간 원소가 첫번째로 나오는 형태이다.

참고로, queue에서 앞에 있는 원소를 first(head), 마지막에 있는 원소를 rear라는 포인터로 가르킨다.

 

 

2. js에서 queue의 구현

js에서 queue에 대한 기능을 독립적으로 제공하지 않는다. 그러나 array의 shift() 메소드를 통해, 비슷하게 구현이 가능하다.

하지만 실제 queue를 통한 enqueue와 array의 shift와의 연산 속도는 차이가 있다.

그 이유는 shift의 로직과 관련이 있다.

shift 의 로직은 다음과 같다.

1. 배열의 첫번째 원소에 접근 후 삭제
2. 첫번째 원소의 공간은 빈 공간이 되므로 뒤에 있는 원소들을 당겨와야 함

→ 원소들을 당겨와야 하기 때문에 (O(n)), 연산 속도가 증가하게 된다.

그래서, data의 양이 적다면 shift()로 해결해도 되지만, data의 양이 많다면 queue로 구현해서 사용하는게 처리 속도 측면에 좋다. 일반적으로 data의 양이 1000개 이하라면 shift를 사용해도 무방하다고 한다.

 

 

3. queue 코드 구현(with js, linked list)

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

// 큐 클래스
class Queue {
  constructor() {
    this.head = null; // 제일 앞 노드
    this.rear = null; // 제일 뒤 노드
    this.length = 0; // 노드의 길이
  }

  enqueue(data) {
    // 노드 추가.
    const node = new Node(data); // data를 가진 node를 만들어준다.
    if (!this.head) {
      // 헤드가 없을 경우 head를 해당 노드로
      this.head = node;
    } else {
      this.rear.next = node; // 아닐 경우 마지막의 다음 노드로
    }
    this.rear = node; // 마지막을 해당 노드로 한다.
    this.length++;
  }

  dequeue() {
    // 노드 삭제.
    if (!this.head) {
      // 헤드가 없으면 한 개도 없는 것이므로 false를 반환.
      return false;
    }
    const data = this.head.data; // head를 head의 다음 것으로 바꿔주고 뺀 data를 return
    this.head = this.head.next;
    this.length--;

    return data;
  }
  // head를 반환하는 함수
  front() {
    // head가 있을 경우 head의 data를 반환.
    return this.head && this.head.data;
  }
  //큐의 모든 원소를 반환하는 함수
  getQueue() {
    if (!this.head) return false;
    let node = this.head;
    const array = [];
    while (node) {
      // node가 없을 때까지 array에 추가한 후 반환해준다.
      array.push(node.data);
      node = node.next;
    }
    return array;
  }
}

const queue = new Queue();

 

 

4.Queue의 Big-0

• search - O(n)
• insert - O(1) → push 한번
• delete - O(1) → pop 한번