큐 - 구현

sohyeon kim·2022년 8월 26일

알고리즘 자료구조

자료구조와 알고리즘

목록 보기

8/9

📌 큐에 필요한 추상자료형

enqueue: 데이터 삽입
dequeue: 데이터 제거
front: 데이터 참조
isEmpty: 비었는지 확인

✅ 기존 연결리스트에서 노드는 다음 노드를 가리키는 하나의 참조만 있었다. 이것을 큐의 구현을 위해서 이전 노드도 가리킬 수 있도록 수정해보자.

먼저 노드 수정

기존 연결리스트와 같지만 모든 노드가 이전 노드를 참조해주는 기능만 구현하면 된다.

insertAt() 함수와 deleteAt() 함수를 수정해서 데이터가 삽입, 삭제될 때 이전 노드를 참조하는 코드를 넣어주자.
기존에는 if 문으로 head에 삽입하는 경우 그렇지 않은 경우는 else문으로 처리했다.
하지만 이전 노드를 가리키는 기능이 추가됐기 때문에 마지막 위치, 즉 tail에 삽입하는 경우도 따로 처리해줘야한다. 이는 else if 문으로 마지막 인덱스에 추가하는 경우를 나눠주겠다.

1️⃣ insertAt() 함수 수정

[insertAt 함수 수정]

  // 1️⃣ 먼저 데이터가 삽입될 때 이전 노드를 가리키는 코드 추가
  // head에 새로운 노드를 삽입할 때 기존 head가 가리키던 노드의 이전 노드를 새로 삽입한 노드로 설정한다.
  insertAt(index, data) {
    if (index > this.count || index < 0) {
      throw new Error("범위를 넘어갔습니다.");
    }

    let newNode = new Node(data);

    // 데이터가 0개 일 때
    if (index == 0) {
      newNode.next = this.head;
      // head가 null일 때 에러가 나지 않도록 if문 삽입
      if (this.head != null) {
        // head가 가리키는 노드의 이전 노드를 새로운 노드로 설정
        this.head.prev = newNode;
      }
      this.head = newNode;

      // 마지막 인덱스 tail에 추가하는 경우를 나눠주자.
    } else if (index == this.count) {
      // 새로운 노드의 다음 노드를 null로 설정
      newNode.next = null;
      // 새로운 노드의 이전 노드를 tail이 가리키던 노드로 설정
      newNode.prev = this.tail;
      // tail이 가리키던 노드의 다음 노드를 새로운 노드로 설정
      this.tail.next = newNode;
      // 새로 삽입된 마지막 위치의 노드를 tail로 만들어줘야하는데 이 부분은
      // 공통적으로 처리하기 위해 if-else문 밖에 넣어주자.
    } else {
      let currentNode = this.head;

      for (let i = 0; i < index - 1; i++) {
        currentNode = currentNode.next;
      }
      // 3️⃣ head와 tail이 아닌 나머지 부분에 삽입하는 경우를 처리해보자.
      // 새로운 노드의 다음노드를 currentNode의 다음 노드로 설정해주는 코드 다음 줄에
      newNode.next = currentNode.next;
      // 새로운 노드의 이전 노드를 currentNode로 설정해준다.
      newNode.prev = currentNode;
      // 그리고 현재 노드의 다음 노드를 새로운 노드로 설정
      currentNode.next = newNode;
      // 마지막으로 새로 삽입한 노드의 다음 노드의 이전 노드를 새로 삽입한 노드로 설정
      newNode.next.prev = newNode;
    }
    // 2️⃣ 새로 삽입된 마지막 위치의 노드를 tail로 만들어줘야하는데 이 부분은
    // 공통적으로 처리하기 위해 if-else문 밖에 넣어주자.
    // 새로 삽입한 노드의 다음 노드가 null이라면 즉 새로 삽입한 노드가 마지막 노드라면

    if (newNode.next == null) {
      // tail을 새로 삽입한 마지막 노드로 설정
      this.tail = newNode;
    }

    this.count++;
  }

2️⃣ deleteAt() 함수 수정

기존에 만든 연결리스트를 수정해서 head뿐만 아니라 리스트의 끝을 tail이 가리키게 했고 각 노드가 이전 노드와 다음 노드를 가리키게 했다.

[deleteAt 함수 수정]

deleteAt(index) {
    if (index >= this.count || index < 0) {
      throw new Error("제거할 수 없습니다.");
    }

    let currentNode = this.head;

    // 1️⃣ 가장 먼저 head에 있는 노드를 제거하는 경우, head에 있는 노드를 제거하기 때문에 삭제할 노드로 head가 가리키는 노드로 설정
    if (index == 0) {
      let deletedNode = this.head;
      // 📌 if 문으로 데이터가 하나 남은 경우와 그렇지 않은 경우 else를 구분해주기
      if (this.head.next == null) {
        // 데이터가 하나 남은 경우로 head의 다음 노드가 null인 경우
        // 이때는 간단하게 head와 tail 모두 null로 설정해주면 리스트가 완벽하게 비워짐.
        this.head = null;
        this.tail = null;
        // 📌 그렇지 않은 경우
        // 데이터가 하나보다 더 많은 경우는 else문으로 처리한다.
      } else {
        // head에 있는 노드가 제거되기 때문에 head의 다음 노드를 새로운 head로 만들어주고
        this.head = this.head.next;
        // 새로 head가 된 노드의 이전 노드를 null로 설정해 연결을 끊어줌.
        this.head.prev = null;
      }
      // count를 하나 줄여주고 리턴
      this.count--;
      return deletedNode;

      // 2️⃣ else if 문을 넣어서 마지막 노드를 제거하는 경우 구분
    } else if (index == this.count - 1) {
      // tail이 가리키는 노드를 삭제할 노드로 설정
      let deletedNode = this.tail;
      // tail 이전 노드의 다음 노드를 null로 설정
      this.tail.prev.next = null;
      // tail 이전 노드를 tail로 설정
      this.tail = this.tail.prev;
      // count를 줄여주고 삭제한 노드를 return
      this.count--;
      return deletedNode;
      // 이제 head와 tail을 제거하는 경우가 아닌 경우 즉, 나머지 부분을 제거하는 경우를 else로 처리
    } else {
      for (let i = 0; i < index - 1; i++) {
        currentNode = currentNode.next;
      }
      // 현재 노드의 다음 노드를 삭제할 노드로 지정
      let deletedNode = currentNode.next;
      // 현재 노드의 다음 노드를 현재 노드의 다음 노드의 다음 노드로 설정하는 것과 똑같다.
      currentNode.next = currentNode.next.next;
      // 이전 노드 설정하기
      // 헌재 노드의 다음 노드의 이전 노드를 현재 노드로 설정
      currentNode.next.prev = currentNode;
      // count를 줄여주고 삭제된 노드 return
      this.count--;
      return deletedNode;
    }
  }

3️⃣ 큐 구현

[Queue.mjs]

import { DoublyLinkedList } from "./DoublyLinkedList.mjs";

class Queue {
  constructor() {
    // 빈 이중 연결리스트를 만들어 초기화
    this.list = new DoublyLinkedList();
  }

  // 📌 데이터 삽입
  // list 의 앞부분에 데이터를 넣기만 하면 됨
  enqueue(data) {
    // insertAt 함수로 인덱스 0에 data 넣어준다.
    this.list.insertAt(0, data);
  }

  // 📌 데이터 제거
  // list 뒷부분에서 데이터 제거
  // 이중연결리스트의 deleteLast 함수를 호출해서 그 노드를 반환하면 끝
  dequeue() {
    // 삭제할 수 없는 경우 예외 처리
    // try - catch
    try {
      return this.list.deleteLast();
    } catch (e) {
      // 예외 발생시
      return null;
    }
  }

  // 📌 front함수 구현
  // 데이터를 제거하지 않고 참조만
  front() {
    // tail값 리턴만
    return this.list.tail;
  }

  // 📌 isEmpty 함수
  isEmpty() {
    // 스택과 동일하게 구현
    return this.list.count == 0;
  }
}

export { Queue };