큐 개요

정의

• 'First In First Out' 이라는 개념을 가진 선형 자료구조다.
• 'Linear Queue', 'Circular Queue' 가 존재한다.

용어

• 'Front' : 큐의 맨 앞부분
• 'Rear' : 큐의 맨 뒷부분
• 'DeQueue' : 큐의 요소 제거
• 'EnQueue' : 큐의 요소 추가

대표예시

• 놀이공원 대기줄

Linear Queue (선형 큐)

배열로 표현하기 (👎)

• 스택과 다르게 배열로 표현하는 것이 조금 어렵습니다.
  • 배열의 길이를 정적으로 관리하는 언어이면 'EnQueue' 가 여러개 되었을때 배열의 길이가 꽉차게됩니다.
  • 자바스크립트에서는 배열의 길이가 자유롭게 증감되기 때문에 배열의 길이 문제는 발생하지 않지만 'DeQueue' 동작할때 각 요소의 인덱스를 하나씩 앞으로 당겨줘야 하기때문에 O(n) 선형시간이 소요됩니다.

연결 리스트로 표현하기 (👍)

• 연결 리스트의 'Head' 가 'Front' 가 되고, 'Tail' 이 'Rear' 가 됩니다.
• 배열과 다르게 인덱스 고민은 할 필요가 없습니다.

JS 에서 선형 큐 구현

깃허브 : https://github.com/HyeonWooGa/algorhithm-code-snippet

Circular Queue (원형 큐)

정의

• 'Front' 와 'Rear' 가 이어져있는 Queue 입니다.
• 한정적인 공간을 효율적으로 이용할때 사용하는 자료구조 입니다.
• Circular Queue 는 Linked List 로 구현했을 때 이점이 없습니다.

JS 에서 원형 큐 구현

깃허브 : https://github.com/HyeonWooGa/algorhithm-code-snippet