Stack을 잘 기억해두고 들어갈 것!!

정의

FIFO(First In, First Out) 구조를 가지는 자료구조

Enqueue(삽입):
| [1] | [2] | [3] | (맨 뒤에 차례대로 들어감)

Dequeue(삭제):

먼저 들어간 1이 가장 먼저 나옴
-> 그 다음 2, 그 다음 3

| [1] | [2] | [3] |
↑출구 . . . ↑입구

쉽게 말해서 먼저 들어온 것이 먼저 나가는 구조인 것 같다.

---

종류

일반 큐

1. 일반 큐 : 맨 앞(front) 요소가 제거되며, 맨 뒤(rear)에 새로운 요소가 추가됨.

index의 값이 변경되지 않고 값의 위치를 가리키는 값만 변경되기 때문에, 고정되어있는 배열은 끝에 도달할 수 밖에 없다.

일반 큐의 한계

정해져있는 최대 갯수 이상으로 넣을 수 없음.

원형 큐

2. 원형 큐 : 배열의 처음과 끝이 연결된 구조

일반 큐의 한계점을 타파하기 위한 큐.
front/rear 인덱스가 배열 끝에 닿으면 다시 처음(0)으로 돌아감
→ 배열을 효율적으로 “순환”시켜, 공간 낭비 없이 사용

우선순위 큐

3. 우선순위 큐: FIFO가 아닌, 우선순위가 높은 요소가 먼저 제거됨.

• FIFO가 아님
• 값(또는 우선순위)이 높은/낮은 것부터 먼저 나감
• 배열/리스트+정렬, 또는 Heap(힙) 구조로 많이 구현