Queue

Queue 💡

Queue는 선형 자료구조로 Stack과는 달리 들어온 순서대로 나오는 구조이다.

1번이 제일 먼저 들어간다고 하면 Stack은 그림과 같이 1번이 가장 먼저 들어갔지만 나올때는 가장

늦게 들어간 4, 3, 2번이 모두 나와야 나올 수 있다. Queue는 가장 먼저 들어간 1번이 가장 먼저

나오게 된다. Stack은 보통 막힌 골목길에 들어선 여러대의 차에 비유할 수 있고, Queue는 놀이공원에서

놀이기구를 타기 위해 기구 앞에 줄을 서 있는 사람들에 비유 할 수 있겠다.(물론 우선탑승권? 제외)

배열 활용

//배열 활용한 Queue 구현
class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  
    enqueue(val) {
      this.queue[this.rear++] = val;  // this.rear에 저장 후 값 1 증가
    }
 
    dequeue() {
      const val = this.queue[this.front];
      delete this.queue[this.front];
      this.front++;
      return val;
    }

    peek() { // 첫번째 값 조회 
      return this.queue[this.front];
    }
  }

연결 리스트 활용(Linked List)

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

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

  enqueue(newValue) {
    const newNode = new Node(newValue);
    if(this.head === null) { // null값 이라면
      this.head = newNode;
      this.tail = newNode;
    } else { // 있다면 꼬리의 다음에 newNode를 연결
      this.tail.next = newNode;
      this.tail = newNode;
    }
   this.size++;
  }

  dequeue() {
    const value = this.head.value;
    this.head = this.head.next;
    this.size--;
    return value;
  }

  peek() {
    return this.head.value;
  }
}

연결 리스트 형태도 가끔 코딩테스트에 나온다고 하니 알아는 두자. !