CS[DataStructure].push('Queue')

Queue란

FIFO (First In First Out) 형식의 자료구조

티켓팅이라고 생각하면 쉬운 자료구조, 처음에 들어간 것이 처음으로 나오게 된다.

탐색(peek): head만 보게 된다. O(1)

제거: 첫 노드(head)를 제거하고 첫 노드의 다음 노드를 head로 바꾼다. O(1)

추가: 모든 노드를 활용해 이동해서 마지막에 추가하기 때문에 O(n)이다.

class Queue {
  front = null;

  enqueue(value) {
    if (this.front===null){
      this.front = new Node(value);
    }
    else{
      let current = this.front;
      while (current.next !==null){
        current=current.next;
      }
      current.next = new Node(value);
    }
  }

  dequeue() {
    if (this.front === null){
      return null;
    }
    let result = this.front.value;
    this.front = this.front.next;
    return result
  }

  peek(){
    if (this.front === null){
      return null;
    }
    return this.front.value;
  }
}

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

const queue = new Queue();
queue.enqueue(4);
queue.enqueue(3);
queue.dequeue();
queue.peek();

Deque

위의 코드는 단방향 Queue로써 front만을 이용해서 삭제, 추가를 구현할 수 있게 되는데 이를 rear를 추가해서 양방향에서 처리하는 Deque라는 자료구조가 존재한다.

Reference

인프런 - 비전공자의 전공자 따라잡기 (제로초)
C언어로 쉽게 풀어쓴 자료구조 - 천인국,공용해,하상호