큐 (Queue)

큐 (Queue)

---

FIFO (First In First Out) 원칙을 따르는 선형 데이터 구조

먼저 들어간 요소가 먼저 나온다

 

대기열의 기본 작업

---

• enqueue(): 큐의 끝, 즉 뒤쪽에 요소를 삽입합니다.
• dequeue(): 이 연산은 큐의 앞쪽에 있는 요소를 제거하고 반환합니다.
• front(): 이 연산은 요소를 제거하지 않고 프런트엔드의 요소를 반환합니다.
• rear(): 이 연산은 요소를 제거하지 않고 뒤쪽에 있는 요소를 반환합니다.
• isEmpty(): 이 연산은 큐가 비어 있는지 여부를 나타냅니다.
• isFull(): 이 연산은 큐가 가득 찼는지 여부를 나타냅니다.
• size(): 이 연산은 큐의 크기, 즉 큐에 포함된 총 요소 수를 반환합니다.

 

큐의 유형

---

• 선형 큐 (Linear Queue)
  • 큐의 가장 기본적인 버전
  • 삽입인 Enqueue 과정은 뒤에서 이루어지고 제거인 Dequeue 과정은 앞에서 이루어진다
  • 삽입과 삭제를 반복하다 보면 앞에 있는 인덱스가 비어 있음에도 꽉 찼다고 인식하는 경우가 발생 -> 이러한 경우를 보안하기 위해 원형 큐가 나옴
• 원형 큐 (Circular Queue)
  • 선형 큐의 문제점을 보완하기 위해 나옴
  • 마지막 요소가 첫번째 요소에 연걸
  • 메모리를 더 나은 방식으로 활용
  • 배열의 마지막 인덱스에서 다음 인덱스로 넘어갈 때 (index+1) % 배열의 사이즈를 이용하여Out Of Bounds Exception이 일어나지 않고 인덱스 0으로 순환되는 구조를 가진다.
• 우선순위 큐 (Priority Queue)
  • 일부 우선순위에 따라 큐에 요소를 정렬
• 데큐 (Dequeue)
  • Double Ended Queue
  • 양쪽 끝에서 삽입하거나 제거할 수 있다