숙제2 연결리스트를 이용하여 큐 구현하기

학습 목표

- 배열 치트키 자료구조가 아닌 연결 리스트를 이용하여 queue 자료구조를 구현하자.

- 삽입과 삭제를 시간복잡도 O(1)가 되게 해야됨.

- queue은 FIFO이기 때문에 삭제시 첫번째를 삭제해야됨.

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

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

  add(value) {
    const newNode = new Node(value);
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++;
    return this.length;
  }

  // 스택 구현시 삭제 메서드
  removeLast() {
    const value = this.tail.value;
    this.tail.prev.next = null; // 제일 마지막 이전의 next의 좌표를 null로 변경해줌
    this.tail = this.tail.prev; // 마지막을 tail의 이전 노드로 변경 해줌

    return value;
  }

  // 큐 구현시 삭제 메서드
  removeFirst() {
    const value = this.head.value;
    this.head.next.prev = null; // 제일 첫번째 다음의 이전 좌표를 null로 변경해줌
    this.head = this.head.next; // 첫번째를 head next 노드로 변경 해줌

    return value;
  }
}

// 숙제2 연결리스트로 큐 만들기
class Queue {
  linkedList = new LinkedList();

  add(value) {
    return this.linkedList.add(value);
  }

  shift() {
    return this.linkedList.removeFirst();
  }

  get top() {
    return this.linkedList.head.value;
  }

  get length() {
    return this.linkedList.length;
  }
}

const queue = new Queue();
console.log(queue.add(1)); // 1
console.log(queue.add(3)); // 2
console.log(queue.add(5)); // 3

console.log(queue.top); // 1
console.log(queue.length); // 3
console.log(queue.shift()); // 1

결과

head의 value값이 3, prev가 null이 되고 next가 value가 5인 노드를 가르킴