Queue with JS

• 단일 연결 리스트 
• 이중 연결 리스트
• 스택 & 큐 (배열로 하는 방법은 숙지했음! linked list로 구현해 보기)
• 이진 검색 트리
• 트리 순회
• 이진 힙
• 해시 테이블 (사용해 봤지만 복습)
• 그래프, 그래프 순회
• 다익스트라 알고리즘
• 동적 프로그래밍

---

2024.01.25 - [코딩테스트/코테를 위한 알고리즘 & 자료구조 정리] - Stack with JS

Stack with JS

스택이 끝났다면....

큐는 스택과 다르게 먼저 들어온 것이 먼저 나가는 "선입선출"로 ,FIFO(First In First Out)의 구조를 가지고 있음.

배열과 메소드를 사용하면 간단하지만 오늘도 똑같이 linked list로 직접 구현을 해서 메모리를 줄여보자.

enqueue, dequeue

---

Queue class Setting

Node 클래스는 연결리스트이기 때문에 스택과 비슷하다.

queue는 연결리스트를 사용할 때 기본적으로 담아두는 value값과 다음을 가리키는 next로 구성되어 있고 

queue 클래스는 first, last, size로 구성되어 있다.

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
}

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

---

enqueue, dequeue는 add, shift와 거의 같다. (변수명만 달라질뿐.. 원리는 같다)

Enqueue

  enqueue(val) {
    var newNode = new Node(val);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    return ++this.size;
  }

Dequeue

  dequeue() {
    if (!this.first) return null;
    var temp = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return temp.val;
  }

 

기본 구조

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
}
class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
  enqueue(val) {
    var newNode = new Node(val);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    return ++this.size;
  }
  dequeue() {
    if (!this.first) return null;
    var temp = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return temp.val;
  }
}

시간 복잡도

big O of Queue

• insertion - O(1)
• Removal - O(1)
• Searching - O(N)
• Access - O(N)