자료구조 알고리즘 - 큐 이해와 효율적인 구현 방법

큐 개요

• 선입선출(FIFO) 구조를 가지고 있는 자료구조입니다.
• 먼저 집어넣은 데이터가 가장 먼저 나오는 자료구조입니다.
• 데이터를 임시로 저장했다가 나중에 꺼내서 사용할 때 유용합니다.

큐의 FIFO 원리

• 줄을 첫 번째 선 사람이 가장 먼저 서비스를 받습니다.
• 큐에서 제거될 첫 번째 항목은 앞쪽이기 때문에 head라고 합니다. 가장 최근에 추가된 위치는 가장 뒤쪽이기 때문에 rear라고 합니다.

큐 동작 원리

• enqueue(el) : 데이터를 큐의 뒤쪽에 추가합니다.
• dequeue() : 큐의 앞쪽에서 데이터를 제거 후 반환합니다.
• front() : 큐의 앞쪽에서 데이터를 제거하지 않고 반환합니다.
• isEmpty() : 큐가 비어있는지 확인합니다.
• size() : 큐의 크기를 반환합니다.

큐 배열 코드 예시

class Queue {
 constructor() {
  this.items = []
 }
 size() {
  return this.items.length
 }
 isEmpty() {
  return this.size() === 0
 }
 enqueue(el) {
  this.items.push(el)
 }
 dequeue() {
  if(this.isEmpty()) throw new Error('empty queue')
  return this.items.shift()
 }
 front() {
  if(this.isEmpty()) throw new Error('empty queue')
  return this.items[0]
 }
}

큐 링크드 리스트 코드 예시

class Node {
 constructor(el) {
  this.item = el
  this.next = null
 }
}

class Queue {
 constructor() {
  this.queue = null
  this.length = 0
 }
 
 size() {
  return this.length
 }
 
 isEmpty() {
  return this.size() === 0
 }
 
 enqueue(el) {
  const node = new Node(el)
  if(this.isEmpty()) this.queue = node
  else {
   let current = this.queue
   while(current.next) {
    current = current.next
   }
   current.next = node
  }
  length++
 }
 
 front() {
  if(this.isEmpty()) throw new Error('empty queue')
  return this.queue.item
 }
 
 dequeue() {
  const item = this.front()
  this.queue = this.queue.next
  length--
  return item
 }
}

하나의 구조에서만 하니 enqueue일때 while을 돌게됩니다.

그래서 2개의 구조를 만들어서 front와 rear로 구성하겠습니다.

class Node {
 constructor(el) {
  this.item = el
  this.next = null
 }
}

class Queue {
 constructor() {
  this.front = null
  this.rear = null
  this.length = 0
 }
 
 size() {
  return this.length
 }
 
 isEmpty() {
  return this.size() === 0
 }
 
 enqueue(el) {
  const node = new Node(el)
  if(this.isEmpty()) this.front = this.rear = node
  else {
   this.rear.next = node
   this.rear = node
  }
  length++
 }
 
 peek() {
  if(this.isEmpty()) throw new Error('empty queue')
  return this.front.item
 }
 
 dequeue() {
  const item = this.peek()
  this.front = this.front.next
  length--
  return item
 }
}

front 와 rear를 둬서 rear에 insert되는 node를 계속 둬서 같은 node를 바라보는 front next에도 영향이 가게끔 했습니다.

선형 큐 개요

• 고정된 크기를 가지는 자료구조로 최대 크기를 초과하면 더이상 데이터를 삽입할 수 없습니다.

선형 큐 작동원리

• enqueue(el) : rear 포인트를 증가 시킨 후 데이터를 추가합니다.
• dequeue() : front 포인트를 증가 시킨 후 데이터를 제거 후 반환합니다.
• peek() : 첫번째 데이터를 제거하지 않고 반환합니다.
• isEmpty() : front와 rear이 같으면 비어있습니다.
• isfull() : rear이 size - 1와 같으면 가득차있습니다.
• getSize() : 현재 큐가 생성된 사이즈를 반환합니다.
• getCount() : 현재 큐에 저장된 데이터 숫자를 반환합니다.

선형 큐 코드 예시

class Queue {
 constructor(size) {
  this.queue = new Array(size)
  this.front = -1
  this.rear = -1
  this.count = 0
 }
 
 getSize() {
  return this.queue.length
 }
 
 getCount() {
  return this.count
 }
 
 isFull() {
  return this.rear === (this.getSize() - 1)
 }
 
 isEmpty() {
  return this.rear === this.front
 }
 
 enqueue(el) {
  if(this.isFull()) throw new Error('full queue')
  this.queue[++this.rear] = el
  this.count++
 }
 
 peek() {
  if(this.isEmpty()) throw new Error('empty queue')
  return this.queue[this.front + 1]
 }
 
 dequeue() {
  const item = this.peek()
  this.front++
  this.count--
  return item
 }
}

원형 큐 개요

• 고정된 크기를 가졌지만 큐의 앞과 뒤가 연결되어 있는 원형 구조를 가집니다.
• 큐가 가득 찬 상태에서 요소를 추가할 때, 새로운 요소를 큐의 첫 번째 위치로 이동시켜 공간을 확보할 수 있습니다.
• 나머지를 이용하여 위치를 이동시켜줍니다.

원형 큐 코드 예시

class Queue {
 constructor(size) {
  this.queue = new Array(size)
  this.front = -1
  this.rear = -1
  this.count = 0
 }
 
 getSize() {
  return this.queue.length
 }
 
 getCount() {
  return this.count
 }
 
 isFull() {
  return this.getCount() === this.getSize()
 }
 
 isEmpty() {
  return this.getCount() === 0
 }
 
 #getIndex(n) {
  return (n + 1) % this.getSize()
 }
 
 enqueue(el) {
  if(this.isFull()) throw new Error('full queue')
  this.rear = this.#getIndex(this.rear)
  this.queue[this.rear] = el
  this.count++
 }
 
 peek() {
  if(this.isEmpty()) throw new Error('empty queue')
  return this.queue[this.#getIndex(this.front)]
 }
 
 dequeue() {
  const item = this.peek()
  this.front = this.#getIndex(this.front)
  this.count--
  return item
 }
}

큐 시간 복잡도

• 데이터 삽입, 삭제 O(1)를 가집니다.

큐 장점

• 데이터 접근, 삽입, 삭제가 빠릅니다.

큐 단점

• 중간에 있는 데이터를 가져오기가 어렵습니다.

큐 활용

• 작업 스케줄링
• 버퍼 구현
• 너비 우선 탐색