C언어 큐 (Queue) - FIFO 자료구조
선수학습(1개)
요약
C언어 큐(Queue)의 개념과 FIFO 원리를 알아봅니다. 선형 큐의 구조, enqueue/dequeue 연산, 그리고 선형 큐의 한계점을 이해하면 원형 큐를 쉽게 이해할 수 있습니다.
큐 핵심 정리
| 개념 | 설명 | 예시 |
|---|---|---|
| 큐(Queue) | 먼저 들어온 데이터가 먼저 나가는 자료구조 | 대기열, 줄 서기 |
| FIFO | First In First Out (선입선출) | 먼저 온 사람이 먼저 서비스 |
| enqueue | 큐에 데이터 삽입 (rear에 추가) | enq(&q, 10); |
| dequeue | 큐에서 데이터 삭제 (front에서 제거) | deq(&q); |
| front | 다음에 꺼낼 위치를 가리키는 정수 | 초기값 0 |
| rear | 다음에 넣을 위치를 가리키는 정수 | 초기값 0 |
큐란?
큐(Queue) 는 먼저 들어온 데이터가 먼저 나가는 자료구조입니다. 이를 FIFO(First In First Out) 라고 합니다.
실생활에서 줄 서기와 같습니다. 먼저 줄을 선 사람이 먼저 서비스를 받습니다.
큐는 두 개의 위치를 기억합니다. front(앞쪽, 데이터를 꺼내는 곳)와 rear(뒤쪽, 데이터를 넣는 곳)입니다. 두 위치 모두 배열의 인덱스를 저장하는 정수값입니다.
큐 vs 스택 비교
| 구분 | 큐 (Queue) | 스택 (Stack) |
|---|---|---|
| 원리 | FIFO (선입선출) | LIFO (후입선출) |
| 삽입 위치 | rear (뒤) | top (위) |
| 삭제 위치 | front (앞) | top (위) |
| 예시 | 대기열, 프린터 작업 | 접시 쌓기, 뒤로가기 |
선형 큐의 구조
선형 큐는 배열을 사용하여 큐를 구현한 것입니다.
아래 코드에서 사용되는 C 문법을 간단히 정리하면:
- #define SIZE 5: 코드에서
SIZE를 모두5로 치환하는 매크로 상수 - typedef struct: 구조체에 별칭을 붙여
struct키워드 없이 사용
Queue q = {{0}, 0, 0};에서 첫 번째 {0}은 배열 data의 모든 요소를 0으로 초기화하고, 나머지 두 0은 front와 rear를 각각 0으로 설정합니다. 구조체 초기화와 같은 방식입니다.
| 위치 표시 | 역할 | 초기값 |
|---|---|---|
front | 삭제할 위치 (맨 앞 요소) | 0 |
rear | 다음 삽입할 위치 (맨 뒤 다음 칸) | 0 |
enqueue (삽입)
enqueue는 큐의 rear 위치에 데이터를 삽입하고, rear를 1 증가시킵니다.
Queue* q는 큐 구조체의 포인터입니다. q->data는 포인터로 구조체 멤버에 접근하는 문법으로, (*q).data와 같은 의미입니다.
삽입 예시
| 동작 | data[0] | data[1] | data[2] | front | rear |
|---|---|---|---|---|---|
| 초기 | 0 | 0 | 0 | 0 | 0 |
| enqueue(10) | 10 | 0 | 0 | 0 | 1 |
| enqueue(20) | 10 | 20 | 0 | 0 | 2 |
| enqueue(30) | 10 | 20 | 30 | 0 | 3 |
dequeue (삭제)
dequeue는 큐의 front 위치에서 데이터를 꺼내고, front를 1 증가시킵니다.
삭제 예시
| 동작 | 반환값 | data[0] | data[1] | data[2] | front | rear |
|---|---|---|---|---|---|---|
| 이전 | - | 10 | 20 | 30 | 0 | 3 |
| dequeue() | 10 | 10 | 20 | 30 | 1 | 3 |
| dequeue() | 20 | 10 | 20 | 30 | 2 | 3 |
선형 큐의 한계
선형 큐는 앞쪽 공간을 재사용할 수 없다는 문제가 있습니다.
연습 문제
다음 단계
선형 큐의 공간 낭비 문제를 해결한 원형 큐(Circular Queue)를 학습하세요. 나머지 연산(%)을 사용해서 배열의 끝과 처음을 연결합니다.