JS 알고리즘 공부 5회차 with. BaaaaaaaarkingDog

#큐

"한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조"

 

큐의 성질 및 시간복잡도

1. 원소의 추가/제거 O(1)
2. 제일 앞(rear)/뒤(front) 원소 확인 O(1)
3. 제일 앞/뒤가 아닌 나머지 원소들의 확인 및 변경이 원칙적으로 불가능
   • 추가적으로 원소를 확인하거나 변경하는 기능을 추가할 수는 있음

const QUEUE_SIZE = 10;
const queue = [];
let head = 0;
let tail = 0;

function push(data) {
  if(tail + 1 === QUEUE_SIZE) {
    console.log("It's full");
    return;
  }
 
  queue[tail++] = data;
}

function pop() {
  if(tail === head) {
    console.log("It's empty");
    return null;
  }
  
  return queue[head++];
}

function front() {
  return queue[head];
}

function back() {
  return queue[tail-1];
}

#원형 큐

"배열로 만든 큐에서 빈 공간을 재활용하기 위한 자료구조"

 

원형 큐의 성질

1. 일반 큐와 같은 성질
2. head나 tail이 마지막을 가리키고 있을 때 0번지로 돌아간다

 

출처 & 참고

큐, BaaaaaaaarkingDog, 2024.10.23