큐

• 큐는 한쪽 방향으로 데이터가 삽입되고 다른 반대 방향으로 데이터가 삭제되는 선형 자료구조입니다.
• 큐는 가장 먼저 삽입된 데이터가 가장 먼저 삭제되므로 선입 선출(FIFO : First-In First-Out)구조라고도 불린다.
• 대표적으로 예매와 관련된 어플리케이션, 데이터를 입력된 순서대로 처리해야 할 때,
  BFS(너비 우선 탐색) 알고리즘을 구현할 때에서 많이 활용되는 자료구조이다.

시간복잡도

• 연결 리스트로 큐를 구현한 경우
  

• 삽입(insertion) : 큐의 맨 뒤 데이터를 추가만 하면 된다.

• 삭제(deletion) : 큐의 맨 앞 데이터를 삭제만 하면 된다.

• 탐색(search) : 맨 앞 요소부터 맨 마지막까지 순차 검색이 이루어진다.
  
  

구현 - javaScript

• 배열을 활용한 큐 구현

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];

    this.front++;

    return value;
  }

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

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

const queue = new Queue();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);

console.log(queue.dequeue()); // 1

queue.enqueue(8);

console.log(queue.size()); // 3
console.log(queue.peek()); // 2
console.log(queue.dequeue()); // 2
console.log(queue.dequeue()); // 4

• 연결 리스트를 활용한 큐 구현

'use strict';

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

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

  // 데이터 삽입
  enqueue(value) {
    const newNode = new Node(value);

    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++;

    return;
  }

  // 데이터 삭제
  dequeue() {
    const deleteNode = this.head;

    if (this.isEmpty()) {
      console.log('삭제할 데이터가 존재하지 않습니다. \n');

      return;
    }

    if (this.size() === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = deleteNode.next;
    }

    this.length--;

    return deleteNode;
  }

  // 맨 앞 데이터 조회
  front() {
    console.log(`Front : ${this.head.data}`);

    return;
  }

  // 맨 뒤 데이터 조회
  rear() {
    console.log(`rear : ${this.tail.data}`);

    return;
  }

  // 큐 크기 조회
  size() {
    return this.length;
  }

  // 큐의 데이터 존재 여부 조회
  isEmpty() {
    return this.length === 0 ? true : false;
  }

  // 큐 데이터 프린트
  print() {
    let curNode = this.head;
    let str = '';

    while (curNode) {
      str += curNode.data + ' ';
      curNode = curNode.next;
    }

    if (str.length === 0) {
      console.log('데이터가 존재하지 않습니다.\n');
    } else {
      console.log(`Queue Size : ${this.length} \n${str} \n`);
    }
  }
}

const queue = new Queue();

queue.enqueue(1);
queue.print();

queue.enqueue(2);
queue.print();

queue.enqueue(3);
queue.print();

queue.dequeue();
queue.print();

queue.front();
queue.rear();

• 결과