[자료구조]Queue에 관하여(feat. Linked List)

Goal

• Queue 에 대해 완벽하게 설명할 수 있다.
• Linked List 를 완벽하게 설명할 수 있다.
• Queue와 Stack을 Linked List로 구현할 수 있다.

Queue란 무엇인가?

• FIFO(First-In First-Out)의 구조를 갖는 자료구조

queue는 'n. (대기하는)줄' 'v. 줄을 서서 기다리다' 라는 사전적 의미를 갖고있습니다. 그에 알맞게 자료구조에서 Queue 또한 줄과 같습니다.

이렇게 사람들이 줄을 서있습니다. 그렇다면 누가 먼저 줄을 서기 시작했을까요?

우리는 알고 있습니다. 바로 가장 우측에 있는 파란색 여성분이겠죠!
그 다음은 노란색 여성분이겠죠. (이제 색으로 표현하겠습니다.)
업무 또한 파란색 - 노란색 - 체크 - 남색 순으로 처리할 것입니다.

이 것이 바로 Queue 입니다.

먼저 줄을 서면(First-In) 먼저 처리한다(First-Out).

Queue의 Field와 Method

• Enqueue : 맨 뒤에 추가 => push()
• Dequeue : 맨 앞에 삭제 => shift()
• Peek : 맨 앞에 (front) 에 위치한 데이터를 읽음
• front : 맨 앞의 위치(index)
• rear : 맨 뒤의 위치(index)

배열로 Queue 구현하기

대략적으로 아래와 같이 구현할 수 있습니다 !

class Queue {
  constructor() {
    this.array = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(value) {
    this.array.push(value);
    this.rear++;
  }

  dequeue() {
    this.front++;
    return this.array.shift();
  }

  peek() {
    return this.array[0];
  }
}

하지만 이렇게 구현하면 성능상 좋지 못합니다..!⛔
Array에서 앞에 있거나 중간에 있는 요소를 제거하면 시간복잡도가 O(n)이 나오기 때문이죠!

여기에서 Linked List가 등장합니다.

Linked List 관련 글 업데이트 예정

---

Linked List로 구현하기

class Queue {
  #rear;
  #size;
  #head;
  #front;

  constructor(maxSize) {
    this.maxSize = maxSize;
    this.#head = { value: undefined, next: undefined };
    this.#size = 0;
    this.#front = 0;
    this.#rear = 0;
    this.tail;
  }
  
	
  // Queue가 비었는지 확인하는 메서드
  isEmpty() {
    return this.#size === 0;
  }
	
  // Queue가 꽉 찼는지 확인하는 메서드
  isFull() {
    return this.#size === this.maxSize;
  }
  
  // Queue의 현재 node의 갯수를 확인하는 메서드
  get size() {
    return this.#size;
  }
  	
  // 맨 뒤의 위치한 node의 위치를 확인하는 메서드
  get rear() {
    if (this.#size === 0) throw new Error("텅 빔");
    return this.#rear;
  }

  // 맨 앞에 위치한 node의 위치를 확인하는 메서드
  get front() {
    if (this.#size === 0) throw new Error("텅 빔");
    return this.#front;
  }

  // 맨 뒤에 node를 추가하는 메서드
  enqueue(value) {
    if (this.isFull()) throw new Error("꽉 참");
    const node = { value, next: undefined };
    if (this.isEmpty()) {
      this.#head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = this.tail.next;
    }
    this.#rear++;
    this.#size++;
  }
  
  // 맨 앞에 node를 삭제하는 메서드
  dequeue() {
    if (this.isEmpty()) throw new Error("텅 빔");
    const node = this.#head;
    this.#head = this.#head.next;
    this.#front++;
    this.#size--;
    return node;
  }

  // 맨 앞에 node를 읽는 메서드
  peek() {
    if (this.isEmpty()) throw new Error("텅 빔");
    return this.#head.value;
  }
}

Queue 알고리즘 문제 풀기

업데이트 예정