Que

CHOYEAH·2023년 10월 31일
자료구조
0
post-custom-banner

Que

큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조의 자료구조입니다.

줄을 서는 행위와 유사하다고 볼 수 있습니다.

FIFO(First-In, First-Out) 또는 LILO(Last-in, Last-Out)라고 불리며,

LIFO(Last-In, First-Out) 방식의 스택과는 꺼내는 순서가 반대입니다.

큐에는 데이터를 넣는 기능과 데이터를 꺼내는 기능이 있다고 볼 수 있습니다.

큐에 데이터를 넣는것을 Enqueue라 하고 큐에서 데이터를 꺼내는것을 Dequeue라 합니다.

참고: https://visualgo.net/en/list

장점:

  1. 순서 보장: 큐는 데이터가 들어온 순서대로 처리되므로, 순서가 중요한 상황에서 유용합니다.
  2. 처리 대기 시간 최소화: 데이터가 순차적으로 처리되기 때문에, 각 요소의 처리 대기 시간이 최소화됩니다.

단점:

  1. 랜덤 접근 불가: 큐에서는 중간에 있는 요소에 직접 접근할 수 없으므로, 특정 위치의 데이터를 찾거나 수정하는 작업이 어렵습니다.
  2. 구현 방식에 따른 공간 효율성: 큐의 데이터 저장 방식에 따라 공간 효율성이 다를 수 있습니다. 예를 들어, 배열 기반의 큐 구현에서 요소를 dequeue하면 배열의 첫 번째 요소를 제거해야 하므로, 요소들이 한 칸씩 앞으로 이동해야 합니다. 이 경우, 시간 복잡도가 O(n)이 되어 비효율적입니다. 이를 개선하기 위해 원형 큐(Circular Queue) 또는 링 버퍼(Ring Buffer)와 같은 방식을 사용하여 공간 효율성을 높일 수 있습니다.

적합한 상황:

  1. 작업 스케줄링: 운영체제에서 프로세스를 순차적으로 처리할 때 큐를 사용하여 작업을 스케줄링합니다.
  2. 인쇄 대기열: 여러 문서가 인쇄를 기다리는 상황에서, 순차적으로 인쇄하도록 큐를 사용하여 인쇄 대기열을 관리합니다.
  3. 이벤트 처리: 웹 애플리케이션에서 발생하는 이벤트들을 순차적으로 처리할 때 큐를 사용합니다.
  4. 너비 우선 탐색(BFS): 그래프 알고리즘에서 너비 우선 탐색을 구현할 때 큐를 사용합니다.

부적합한 상황:

  1. 랜덤 접근이 필요한 경우: 큐는 중간 요소에 직접 접근할 수 없으므로, 이러한 작업을 수행해야 하는 상황에는 다른 자료구조를 사용하는 것이 좋습니다.
  2. 최근 항목이 중요한 경우: 최근에 추가된 항목에 대한 처리가 우선되어야 하는 상황에서는 스택(Stack)이나 다른 자료구조를 사용하는 것이 더 적합합니다.
  3. 데이터 정렬이 필요한 경우: 큐는 데이터를 정렬하는 기능이 없으므로, 정렬된 상태로 데이터를 유지해야 하는 경우 힙(Heap) 등의 다른 자료구조를 사용하는 것이 좋습니다.

주의사항:

  1. 오버플로우와 언더플로우: 큐의 크기가 제한되어 있다면, 큐가 가득 찼을 때 원소를 추가하려고 시도하면 오버플로우가 발생합니다. 반대로, 큐가 비어있는데 원소를 제거하려고 시도하면 언더플로우가 발생합니다. 이러한 상황을 피하려면 큐의 크기를 확인하고, 오버플로우 또는 언더플로우가 발생하지 않도록 적절한 조치를 취해야 합니다.
  2. 동기화 문제: 여러 스레드 또는 프로세스가 동시에 큐에 액세스해야 하는 경우 동기화 문제가 발생할 수 있습니다. 이를 방지하기 위해 동기화 메커니즘을 사용하여 동시 액세스를 처리할 수 있습니다. 자바스크립트에서는 워커를 사용하여 멀티스레드 환경을 구성할 수 있습니다.
    • 동기화 메커니즘 경쟁 조건(Race Condition)과 같은 문제를 방지하기 위해 사용하는 기술입니다. 동기화 메커니즘은 상호 배제(mutual exclusion)를 통해 공유 자원에 대한 동시 액세스를 제한하고, 순서를 정해서 처리합니다. 이를 통해 데이터 일관성과 안정성을 보장할 수 있습니다. 다양한 동기화 메커니즘들이 있습니다:

      1. 뮤텍스(Mutex): 뮤텍스는 상호 배제를 위한 동기화 기본 객체로서, 한 번에 하나의 스레드만 공유 자원에 액세스할 수 있도록 합니다. 뮤텍스를 소유한 스레드만 해당 자원을 사용할 수 있으며, 다른 스레드는 뮤텍스가 해제될 때까지 대기해야 합니다.

      2. 세마포어(Semaphore): 세마포어는 공유 자원에 대한 동시 액세스 수를 제한하는 카운터 기반 동기화 메커니즘이며, 여러 스레드가 동시에 공유 자원에 액세스할 수 있습니다. 세마포어는 일반적으로 뮤텍스와 함께 사용되어 더 복잡한 동기화를 제공합니다.

      3. 모니터(Monitor): 모니터는 공유 자원에 대한 상호 배제를 제공하는 고급 동기화 메커니즘으로, 특정 객체의 메소드에 대한 동시 액세스를 제한합니다. 모니터 내에서 실행 중인 스레드는 다른 스레드가 해당 메소드를 호출할 수 없도록 합니다.

      4. 락(Lock): 락은 공유 자원에 대한 동시 액세스를 제한하기 위해 사용되는 동기화 메커니즘입니다. 락을 획득한 스레드만 공유 자원에 액세스할 수 있으며, 락이 해제되기 전까지 다른 스레드는 대기해야 합니다.

      5. 컨디션 변수(Condition Variable): 컨디션 변수는 스레드가 공유 자원의 특정 상태를 기다리도록 하는 동기화 메커니즘입니다. 스레드는 컨디션 변수를 사용하여 다른 스레드가 공유 자원의 상태를 변경할 때까지 기다리게 됩니다.

        위의 동기의 동기화 메커니즘 외에도 다양한 동기화 기법이 있으며, 언어와 라이브러리에 따라 구현 방식이 다를 수 있습니다. 이러한 동기화 메커니즘을 사용하면 공유 자원에 대한 동시 액세스를 제어하고, 데이터의 일관성과 시스템의 안정성을 유지할 수 있습니다.

    • 자바스크립트 워커 멀티스레드

      1. Async/Await: 비동기 작업을 처리하는 동안 동기화를 위해 async/await 패턴을 사용할 수 있습니다. 이를 통해 비동기 작업이 완료될 때까지 다른 작업을 일시 중단하고, 순서대로 처리할 수 있습니다.

        
async function fetchData() {
  try {
    const response = await fetch('https://api.example.com/data');
    const data = await response.json();
    console.log(data);
  } catch (error) {
    console.error('Error:', error);
  }
}

fetchData();

      2. Promise: 자바스크립트에서 Promise는 비동기 작업의 결과를 나타내는 객체로 사용됩니다. Promise를 사용하면 비동기 작업이 완료된 후 실행할 작업을 체인으로 연결할 수 있습니다.

        
fetch('https://api.example.com/data')
  .then(response => response.json())
  .then(data => console.log(data))
  .catch(error => console.error('Error:', error));

      3. 웹 워커(Web Worker): 웹 워커는 별도의 스레드에서 스크립트를 실행할 수 있게 해주는 기술입니다. 웹 워커를 사용하면 메인 스레드와 별도로 동작하는 작업을 수행할 수 있으며, 메인 스레드와 웹 워커 사이에 메시지를 주고받을 수 있습니다.

        ```jsx

// main.js
const worker = new Worker('worker.js');

worker.addEventListener('message', event => {
  console.log('Message from worker:', event.data);
});

worker.postMessage('Hello, Worker!');

// worker.js
self.addEventListener('message', event => {
  console.log('Message from main:', event.data);
  postMessage('Hello, Main!');
});

```

        동기화 메커니즘을 사용할 때는 성능과 사용성 사이의 균형을 고려해야 합니다. 동기화를 과도하게 사용하면 성능 저하의 원인이 될 수 있으므로, 필요한 경우에만 적절한 동기화 기법을 적용하는 것이 중요합니다.

  3. 메모리 관리: 큐가 사용하는 메모리가 누적되어 시스템에 부담을 주지 않도록 주기적으로 메모리를 정리해야 합니다. 큐에서 원소를 제거한 후에는 메모리에서도 해당 원소를 해제해야 합니다.
  4. 정확한 순서 보장: 큐는 FIFO(First In, First Out) 원칙에 따라 동작합니다. 큐를 사용하는 알고리즘에서 순서가 중요한 경우, 원소를 추가하거나 제거할 때 순서를 보장해야 합니다.
  5. 성능 최적화: 큐의 성능을 최적화하려면 원소를 추가하고 제거하는데 걸리는 시간을 최소화해야 합니다. 배열이나 연결 리스트를 사용하여 큐를 구현할 수 있는데, 각 방식에 따라 성능이 다를 수 있습니다. 배열을 사용한 큐는 원소를 추가하거나 제거할 때 배열의 인덱스를 조정해야 하므로 비용이 더 들 수 있습니다. 반면, 연결 리스트를 사용한 큐는 원소를 추가하거나 제거할 때 포인터만 변경하면 되므로 비용이 적게 듭니다. 상황에 따라 적합한 구현 방식을 선택해야 합니다.

큐 구현

Python

파이썬 queue 라이브러리 활용해서 큐 자료 구조 사용하기

queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공
- 프로그램을 작성할 때 프로그램에 따라 적합한 자료 구조를 사용
- Queue(): 가장 일반적인 큐 자료 구조
- LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조 (스택 구조라고 보면 됨)
- PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

Queue()로 큐 만들기 (가장 일반적인 큐, FIFO(First-In, First-Out))

    import queue
    
    data_queue = queue.Queue()
    data_queue.put("funcoding")
    data_queue.put(1)
    data_queue.qsize()
    # 2
    
    data_queue.get()
    # 'funcoding'
    
    data_queue.qsize()
    # 1
    
    data_queue.get()
    # 1

LifoQueue()로 큐 만들기 (LIFO(Last-In, First-Out))

    import queue
    data_queue = queue.LifoQueue()
    data_queue.put("funcoding")
    data_queue.put(1)
    data_queue.qsize()
    # 2
    data_queue.get()
    # 1

PriorityQueue()로 큐 만들기

    import queue
    
    data_queue = queue.PriorityQueue()
    data_queue.put((10, "korea"))
    data_queue.put((5, 1))
    data_queue.put((15, "china"))
    data_queue.qsize()
    # 3
    data_queue.get()
    # (5, 1)
    
    data_queue.get()
    # (10, 'korea')
    
    data_queue.get()
    # (15, 'china')

리스트 변수로 큐를 다루는 enqueue, dequeue 기능 구현해보기

    queue_list = list()
    
    def enqueue(data):
        queue_list.append(data)
        
    def dequeue():
        data = queue_list[0]
        del queue_list[0]
        return data
    
    for index in range(10):
        enqueue(index)
    
    len(queue_list)
    # 10
    
    dequeue()
    # 0
    
    dequeue()
    # 1
    
    dequeue()
    # 2

JS

배열을 사용하여 구현한 큐

class Queue {
  items = [];

  // 큐에 요소를 추가하는 메서드
  enqueue(element) {
    this.items.push(element);
  }

  // 큐에서 가장 앞에 있는 요소를 제거하고 반환하는 메서드
  dequeue() {
    const firstItem = this.items[0];
    for (let i = 0; i < this.items.length - 1; i++) {
      this.items[i] = this.items[i + 1];
    }
    // this.items.splice(this.items.length - 1, 1);
    // 위 코드는 가독성이 좋으나 내부적으로 요소를 지운 후 나머지 요소를 다시 결합하는 작업이 수행되기 때문에
    // -=를 사용하는것이 성능적으로 더 우수하다 -=연산을 수행하면 배열의 길이를 조절하면서 요소가 사라진다.
    // 대신 주석을 명확하게 남겨놓는것이 좋을것이다.
    this.items.length -= 1;
    return firstItem;
  }

  // 큐의 가장 앞에 있는 요소를 반환하는 메서드 (큐에 변화를 주지 않음)
  front() {
    return this.items[0];
  }

  // 큐가 비어 있는지 확인하는 메서드
  isEmpty() {
    return this.items.length === 0;
  }

  // 큐의 모든 요소를 문자열 형태로 출력하는 메서드
  printQueue() {
    return this.items.join(" ");
  }

  // 큐의 크기를 반환하는 메서드
  size() {
    return this.items.length;
  }
}

// 예제 코드
const myQueue = new Queue();
myQueue.enqueue(1);
myQueue.enqueue(2);
myQueue.enqueue(3);
console.log(myQueue.printQueue()); // 출력: 1 2 3
console.log(myQueue.dequeue()); // 출력: 1
console.log(myQueue.printQueue()); // 출력: 2 3
console.log(myQueue.front()); // 출력: 2
console.log(myQueue.isEmpty()); // 출력: false
console.log(myQueue.size()); // 출력: 2
console.log(myQueue.dequeue()); // 출력: 2
console.log(myQueue.printQueue()); // 출력:3

링버퍼를 활용한 원형큐

원형 큐(Circular Queue)는 배열을 기반으로 한 큐의 한 가지 효율적인 구현 방법입니다. 원형 큐에서는 링 버퍼 기법을 사용하여 배열의 끝에 도달한 후 다시 배열의 시작 부분으로 돌아가며, 이를 통해 공간을 최대한 활용합니다. 다음은 원형 큐를 자바스크립트로 구현한 예제입니다.

링 버퍼(Ring Buffer)는 고정된 크기의 배열을 사용하여 원형 구조를 형성하는 방식입니다. 링 버퍼에서는 읽기와 쓰기 위치를 관리하는 두 개의 인덱스를 사용하여 데이터를 저장하고 처리합니다. 링 버퍼는 원형 큐를 구현하는데 사용될 수 있지만, 그 외에도 다양한 용도로 사용될 수 있는 일반적인 데이터 저장 기법입니다. 예를 들어, 오디오나 비디오 스트리밍, 네트워킹, 실시간 처리 등 다양한 분야에서 링 버퍼가 사용됩니다.

결론적으로, 원형 큐는 특정 자료구조를 의미하며, 링 버퍼는 원형 큐를 포함한 다양한 용도로 사용되는 고정 크기의 원형 데이터 저장 방식을 의미합니다.

class CircularQueue {
  constructor(capacity) {
    this.capacity = capacity;
    this.queue = new Array(capacity);
    this.front = 0;
    this.rear = 0;
    this.size = 0;
  }

  // 큐에 요소를 추가하는 메서드
  enqueue(element) {
    if (this.isFull()) {
      throw new Error("Queue is full");
    }
    this.queue[this.rear] = element;
		
		// 원형 큐에서 rear 인덱스는 새로운 요소가 추가될 위치를 가리킵니다.
		// 인덱스가 배열의 끝에 도달한 경우, 다시 배열의 시작 부분(인덱스 0)으로 돌아갑니다.
    this.rear = (this.rear + 1) % this.capacity;
    this.size++;
  }

  // 큐에서 가장 앞에 있는 요소를 제거하고 반환하는 메서드
  dequeue() {
    if (this.isEmpty()) {
      throw new Error("Queue is empty");
    }
    const dequeuedElement = this.queue[this.front];
    this.queue[this.front] = null;
    /*
			원형 큐(또는 링 버퍼)의 핵심 부분 중 하나는 인덱스를 순환시키는 것입니다. (this.rear + 1) % this.capacity와 같은 연산은 인덱스를 순환시키는 데 사용되며, 배열의 끝에 도달한 경우 인덱스를 다시 배열의 시작 부분(인덱스 0)으로 돌아가게 합니다.
			이 연산을 사용함으로써 원형 큐에서 공간을 효율적으로 사용하고, 새로운 요소를 추가하거나 기존 요소를 제거할 때 배열의 크기를 조절할 필요가 없습니다. 이는 원형 큐를 구현하는데 중요한 요소입니다.
			enqueue 메서드에서 이 연산을 사용하여 rear 인덱스를 순환시키고, dequeue 메서드에서는 (this.front + 1) % this.capacity를 사용하여 front 인덱스를 순환시킵니다. 이렇게 함으로써 원형 큐가 올바르게 동작하게 됩니다.
		*/
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return dequeuedElement;
  }

  // 큐의 가장 앞에 있는 요소를 반환하는 메서드 (큐에 변화를 주지 않음)
  front() {
    if (this.isEmpty()) {
      throw new Error("Queue is empty");
    }
    return this.queue[this.front];
  }

  // 큐가 비어 있는지 확인하는 메서드
  isEmpty() {
    return this.size === 0;
  }

  // 큐가 가득 찼는지 확인하는 메서드
  isFull() {
    return this.size === this.capacity;
  }

  // 큐의 크기를 반환하는 메서드
  size() {
    return this.size;
  }
}

// 예제 코드
const myCircularQueue = new CircularQueue(3);
myCircularQueue.enqueue(1);
console.log(myCircularQueue);
myCircularQueue.enqueue(2);
console.log(myCircularQueue);
myCircularQueue.enqueue(3);
console.log(myCircularQueue);

try {
  myCircularQueue.enqueue(4);
} catch (error) {
  console.log(error.message); // 출력: Queue is full
}

console.log(myCircularQueue.dequeue()); // 출력: 1
console.log(myCircularQueue);
myCircularQueue.enqueue(4);
console.log(myCircularQueue);
console.log(myCircularQueue.dequeue()); // 출력: 2
console.log(myCircularQueue);
console.log(myCircularQueue.getFront()); // 출력: 3
console.log(myCircularQueue);

큐의 용량을 인수로 받아 초기화하고, 배열을 기반으로 front와 rear 인덱스를 관리합니다. front와 rear 인덱스는 각각 큐의 시작과 끝을 가리키며, 큐가 가득 찼는지 여부를 확인하는 데 사용됩니다. 원형 큐를 사용하면 enqueue와 dequeue 작업이 상수 시간(O(1))이 걸리므로, 성능상의 이점이 있습니다.

배열을 사용한 일반 큐와 링 버퍼 기법을 사용한 원형 큐의 성능 차이에 대하여.

  1. 배열을 사용한 일반 큐

일반 큐는 선입선출(FIFO) 원칙에 따라 데이터를 처리합니다. 배열을 사용하여 큐를 구현할 경우, 요소를 추가할 때는 배열의 끝에 삽입하고, 요소를 제거할 때는 배열의 시작 부분에서 삭제합니다.

요소를 추가하는 것은 상수 시간(O(1))이 걸리지만, 요소를 제거하는 것은 선형 시간(O(n))이 걸립니다. 왜냐하면 배열의 시작 부분에서 요소를 제거하면 나머지 요소들을 왼쪽으로 이동시켜 공간을 채워야하기 때문입니다. 이로 인해 일반 배열 기반 큐에서 요소를 제거할 때마다 배열의 크기에 비례하는 시간이 소요됩니다.

  1. 링 버퍼 기법을 사용한 원형 큐

원형 큐는 링 버퍼 기법을 사용하여 배열을 기반으로 구현할 수 있습니다. 원형 큐에서는 front와 rear 인덱스를 사용하여 요소를 추가하고 제거하는 작업을 관리합니다. 배열의 끝에 도달한 후에는 인덱스가 다시 시작 부분으로 돌아가면서 공간을 최대한 효율적으로 활용합니다.

원형 큐에서 요소를 추가하거나 제거하는 작업은 상수 시간(O(1))이 걸립니다. 인덱스만 업데이트하면 되기 때문에, 배열의 크기와 관계없이 일정한 시간이 소요됩니다. 따라서 원형 큐는 일반 배열 기반 큐에 비해 성능상의 이점이 있습니다.

요약하면, 일반 배열 기반 큐에서 요소를 제거하는 작업은 선형 시간이 걸리지만, 원형 큐에서는 상수 시간이 걸립니다. 이로 인해 원형 큐가 일반 배열 기반 큐에 비해 성능상의 이점을 가집니다.

선형 시간(linear time)이란 알고리즘이나 작업의 실행 시간이 입력 데이터의 크기에 비례하여 선형적으로 증가하는 것을 의미합니다. 선형 시간 복잡도는 일반적으로 O(n)으로 표기되며, 여기서 n은 입력 데이터의 크기를 나타냅니다.

예를 들어, 배열에 있는 모든 요소를 순회하며 합계를 구하는 작업은 선형 시간이 걸립니다. 배열의 크기가 10개의 요소일 때 10번의 연산이 필요하고, 배열의 크기가 100개의 요소일 때는 100번의 연산이 필요하기 때문입니다. 이 경우, 실행 시간이 입력 데이터의 크기에 비례하여 증가하므로 선형 시간이 걸리는 작업이라고 할 수 있습니다.

선형 시간과 대비되는 개념으로는 상수 시간(constant time)이 있습니다. 상수 시간은 입력 데이터의 크기와 관계없이 일정한 시간이 걸리는 작업을 의미합니다. 상수 시간 복잡도는 O(1)로 표기되며, 입력 데이터의 크기에 영향을 받지 않습니다.

원형 큐 구현에 있어서 rear와 front이 두 인덱스는 각각 다른 목적으로 사용되며, 원형 큐의 동작을 관리하는 데 필수적입니다.

  1. rear 인덱스: rear 인덱스는 새로운 요소가 추가될 위치를 가리킵니다. 원소가 큐에 추가될 때마다 rear 인덱스는 증가하며, 배열의 끝에 도달한 후에는 다시 배열의 시작 부분으로 돌아갑니다. 이렇게 함으로써 원형 큐에서 공간을 최대한 효율적으로 활용할 수 있습니다.
  2. front 인덱스: front 인덱스는 큐에서 가장 앞에 있는 요소, 즉 다음에 제거될 요소를 가리킵니다. 원소가 큐에서 제거될 때마다 front 인덱스는 증가하며, 배열의 끝에 도달한 후에는 다시 배열의 시작 부분으로 돌아갑니다.

rear와 front 인덱스를 사용하여 원형 큐에서 요소를 추가하고 제거하는 작업을 상수 시간(O(1))에 수행할 수 있습니다. 두 인덱스가 없으면, 원형 큐의 동작을 올바르게 처리하거나 관리하기 어려워집니다. 따라서 원형 큐 구현에 있어서 rear와 front 인덱스는 모두 필수적입니다.

(index + 1) % capacity와 같은 공식은 주로 순환 구조에서 인덱스를 관리하는 데 사용되며, 여러 상황에서 활용됩니다. 여기에 몇 가지 예를 들어 보겠습니다.

  1. 원형 버퍼(Circular Buffer): 이 공식은 원형 큐와 관련된 원형 버퍼에서도 사용됩니다. 원형 버퍼는 고정된 크기의 배열에서 데이터를 순환적으로 저장하는 데이터 구조입니다. 원형 버퍼에서 이 공식은 새로운 데이터를 저장할 위치를 결정하고 기존 데이터를 덮어쓰는 데 사용됩니다.
  2. 로테이션(회전) 알고리즘: 배열이나 문자열 등의 데이터를 순환적으로 회전시키는 알고리즘에서 이 공식이 사용됩니다. 예를 들어, 데이터를 오른쪽으로 한 칸씩 이동시키는 데 이 공식을 사용하여 새로운 인덱스를 계산할 수 있습니다.
  3. 시계열 데이터 관리: 시계열 데이터를 저장하고 처리하는 애플리케이션에서는 일정 시간 간격으로 샘플링된 데이터를 저장합니다. 이때, 고정된 크기의 순환 버퍼를 사용하여 샘플을 저장하고, 이 공식을 사용하여 새로운 샘플이 저장될 위치를 계산합니다.
  4. 프로세스 스케줄링: 컴퓨터 시스템에서 프로세스 스케줄링 알고리즘 중 하나인 Round Robin 스케줄링에서 이 공식이 사용됩니다. Round Robin 스케줄링은 각 프로세스에 공평하게 CPU 시간을 할당하며, 이 공식을 사용하여 다음 실행할 프로세스를 순환적으로 선택합니다.

이러한 상황에서 (index + 1) % capacity 공식은 인덱스를 순환적으로 증가시키고, 배열의 경계를 넘지 않도록 하는데 사용됩니다. 이 공식을 사용하면 고정된 크기의 배열이나 리스트에서 데이터를 효율적으로 관리할 수 있습니다.

연결 리스트를 이용한 큐 구현

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

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

  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }
    this.tail.next = newNode;
    this.tail = newNode;
  }

  removeFirst() {
    if (!this.head) {
      return null;
    }
    const removedHead = this.head;
    this.head = this.head.next;
    if (!this.head) {
      this.tail = null;
    }
    return removedHead.value;
  }

  isEmpty() {
    return !this.head;
  }
}

class Queue {
  constructor() {
    this.linkedList = new LinkedList();
  }

  enqueue(value) {
    this.linkedList.append(value);
  }

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

  isEmpty() {
    return this.linkedList.isEmpty();
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.linkedList.head.value;
  }
}

// 사용 예시
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.peek()); // 출력: 1
console.log(queue.dequeue()); // 출력: 1
console.log(queue.peek()); // 출력: 2
profile
CHOYEAH
Move fast & break things
이전 포스트

Stack

다음 포스트

Linked List

post-custom-banner

0개의 댓글