[Typescript] 자료구조 : 큐 (Queue)

 

큐의 모습

 

 

 

 

큐의 특징

• 탐색 시, O(n) 만큼 소요됩니다.
• 추가, 삭제 시, O(1) 만큼 소요됩니다.
• 맨 앞의 노드를 head, 맨 뒤의 노드를 tail로 기억합니다.
• 식당에서 순서를 기다리는 대기열과 비슷합니다.

 

 

 

 

데이터 노드 구현하기

class Node {
    value: number;
    prev: Node | null = null;
    next: Node | null = null;

    constructor(value: number) {
      this.value = value;
    }
  }

prev, next 프로퍼티가 있습니다.

value 프로퍼티로 데이터를 받고 있고, 숫자 데이터만 받기로 정했습니다.

 

 

* 큐를 이중 연결 리스트를 이용해서 구현했습니다.

 

 

 

[ 이중 연결 리스트 개념 ] 

[Typescript] 자료구조 : 이중 연결 리스트 (doubly-LinkedList)

 

 

 

 

큐 구현하기

class Queue {
    private head: Node | null = null;
    private tail: Node | null = null;
    private size = 0;

    isEmpty() {
      return this.size === 0;
    }

    enqueue(node: Node) {
      if (this.isEmpty()) {
        this.head = node;
        this.tail = node;
        this.size = 1;
        return;
      }

      const tailPrevNode = this.tail;

      tailPrevNode.prev = node;
      node.next = tailPrevNode;

      this.tail = node;
      this.size++;
    }

    dequeue(): Node | null {
      if (this.isEmpty()) {
        console.log("Queue is Empty!");
        return null;
      }

      const node = this.head;
      this.head = node.prev;

      node.prev = null;

      if (this.size > 1) {
        this.head.next = null;
      }

      this.size--;
      return node;
    }
  }

 

 

 

 

구현한 코드를 테스트 해보기

const queue = new Queue();

queue.enqueue(new Node(1));
queue.enqueue(new Node(2));
queue.enqueue(new Node(3));

console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());

 

 

console 출력값

Node { next: null, prev: null, value: 1 }
Node { next: null, prev: null, value: 2 }
Node { next: null, prev: null, value: 3 }
Queue is Empty!
null