자료구조와 알고리즘 - 큐

본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다.

1. Queue란?

• 선형 자료구조
• First In First Out
  • 먼저 들어온것이 먼저 나감
• Linear Queue, Cicular Queue
• Front: Queue의 맨 앞
• Rear: Queue의 맨 뒤
• DeQueue: Queue의 요소를 빼는 것
• EnQueue: Queue의 요소를 넣는 것
• 대기열이라고 할 수 있음

2. Linear Queue

• 선형 큐
• Array로 표현 가능
  • 한정된 공간인 Array에서 구현하기에는 어려움이 있음
  • 앞요소가 DeQueue가 되어도 그 만큼 배열을 더 사용할 수는 없음
  • EnQueue가 해당 배열의 length만큼만 가능
  • JavaScript에서는 위 문제는 없지만, Front, Rear의 index가 무한정 커질 수 있음
  • 공간을 더 사용하기 위해 앞당기는 작업이 필요하는데 선형 시간이 소요 됨
• Linked List로 표현 가능
  • Head는 Front
  • Taildms Rear
  • index에 대한 고민은 안 해도 됨

3. Cicular Queue

• 환형 큐
• Front와 Rear가 이어져있는 Queue
• Array로 표현 가능

Reference

프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript