Gaon12: 시작

2024-10-14T02:24:41Z

시작

새 문서

== 개요 ==
큐(Queue)는 컴퓨터 과학에서 널리 사용되는 추상 자료형으로, 데이터를 순서대로 저장하고 관리하는 자료 구조이다. 큐의 가장 큰 특징은 '선입선출'(FIFO: First In First Out) 원칙을 따른다는 점이다. 이는 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조를 의미한다.

== FIFO vs LIFO ==
데이터 구조를 이해하는 데 있어 FIFO와 LIFO의 개념은 매우 중요합니다.

=== FIFO (First In First Out) ===
* FIFO는 '''"먼저 들어온 것이 먼저 나간다"'''는 원칙이다.
* 큐(Queue)가 대표적인 FIFO 구조다.
* 실생활의 예: 계산대에 줄 서 있는 사람들, 프린터의 인쇄 대기열

=== LIFO (Last In First Out) ===
자세한 내용은 [[스택(프로그래밍)]] 문서를 참고하세요!

* LIFO는 '''"나중에 들어온 것이 먼저 나간다"'''는 원칙이다.
* 스택(Stack)이 대표적인 LIFO 구조다.
* 실생활의 예: 접시 쌓기, 웹 브라우저의 뒤로 가기 버튼

== 큐(Queue)의 특징 ==
# FIFO 원칙: 가장 먼저 들어온 데이터가 가장 먼저 나간다.
# 주요 작업:
## Enqueue: 큐의 뒤쪽(rear)에 새로운 요소를 추가한다.
## Dequeue: 큐의 앞쪽(front)에서 요소를 제거한다.
# 주요 위치:
## Front: 큐의 첫 번째 요소 위치
## Rear: 큐의 마지막 요소 위치

== 큐의 기본 연산 ==
# enqueue(item): 큐의 뒤쪽(rear)에 새로운 요소를 추가한다.
# dequeue(): 큐의 앞쪽(front)에서 요소를 제거하고 반환한다.
# front(): 큐의 첫 번째 요소를 반환하지만 제거하지는 않는다.
# isEmpty(): 큐가 비어있는지 확인한다.
# isFull(): 큐가 가득 찼는지 확인한다. (배열로 구현된 경우)

== 큐의 구현 방식 ==
큐는 주로 두 가지 방식으로 구현된다:

=== 1. 배열 기반 구현 ===
배열을 사용하여 큐를 구현하는 방식이다.

==== 장점 ====
* 구현이 간단하다.
* 랜덤 접근이 가능하다.

==== 단점 ====
* 크기가 고정되어 있어 큐가 가득 찼을 때 새로운 요소를 추가할 수 없다.
* 큐에서 요소를 제거할 때마다 모든 요소를 앞으로 이동시켜야 할 수 있다.

==== C언어 예제 ====
<syntaxhighlight lang="c">
#include <stdio.h>
#define MAX_SIZE 100

typedef struct {
int items[MAX_SIZE];
int front;
int rear;
} Queue;

void initializeQueue(Queue *q) {
q->front = -1;
q->rear = -1;
}

int isEmpty(Queue *q) {
return (q->front == -1 && q->rear == -1);
}

int isFull(Queue *q) {
return (q->rear == MAX_SIZE - 1);
}

void enqueue(Queue *q, int value) {
if (isFull(q)) {
printf("Queue is full!\n");
return;
}
if (isEmpty(q)) {
q->front = 0;
}
q->rear++;
q->items[q->rear] = value;
}

int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return -1;
}
int item = q->items[q->front];
if (q->front == q->rear) {
initializeQueue(q);
} else {
q->front++;
}
return item;
}

int main() {
Queue q;
initializeQueue(&q);

enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);

printf("%d\n", dequeue(&q));
printf("%d\n", dequeue(&q));

return 0;
}
</syntaxhighlight>

=== 2. 연결 리스트 기반 구현 ===
연결 리스트를 사용하여 큐를 구현하는 방식이다.

==== 장점 ====
* 크기가 동적으로 조절된다.
* 요소의 추가와 제거가 효율적이다.

==== 단점 ====
* 추가적인 메모리가 필요하다. (포인터를 저장해야 하므로)
* 랜덤 접근이 불가능하다.

==== C언어 예제 ====
<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
int data;
struct Node* next;
} Node;

typedef struct {
Node* front;
Node* rear;
} Queue;

void initializeQueue(Queue* q) {
q->front = q->rear = NULL;
}

int isEmpty(Queue* q) {
return (q->front == NULL);
}

void enqueue(Queue* q, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;

if (isEmpty(q)) {
q->front = q->rear = newNode;
} else {
q->rear->next = newNode;
q->rear = newNode;
}
}

int dequeue(Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return -1;
}

Node* temp = q->front;
int item = temp->data;

q->front = q->front->next;
free(temp);

if (q->front == NULL) {
q->rear = NULL;
}

return item;
}

int main() {
Queue q;
initializeQueue(&q);

enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);

printf("%d\n", dequeue(&q));
printf("%d\n", dequeue(&q));

return 0;
}
</syntaxhighlight>

== 큐의 응용 분야 ==
큐는 다양한 분야에서 활용된다:

# 운영 체제의 작업 스케줄링
# 네트워크의 데이터 패킷 전송
# 프린터의 인쇄 작업 대기열
# 웹 서버의 요청 처리
# 너비 우선 탐색(BFS) 알고리즘
# 캐시(Cache) 구현

== 큐의 변형 ==
# 원형 큐(Circular Queue): 배열의 처음과 끝이 연결된 형태의 큐.
# 우선순위 큐(Priority Queue): 각 요소에 우선순위가 부여되어 있어, 우선순위가 높은 요소가 먼저 나가는 큐.
# 데크(Deque, Double-ended Queue): 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐.

== 결론 ==
큐는 FIFO 원칙을 따르는 간단하면서도 강력한 자료 구조이다. 이 구조는 많은 실제 상황을 모델링하는 데 이상적이며, 컴퓨터 과학의 여러 분야에서 중요한 역할을 한다. 큐의 개념을 이해하고 적절히 활용할 수 있다면, 다양한 프로그래밍 문제를 효과적으로 해결할 수 있을 것이다.<s>악 코딩테스트</s>


[[분류:자료구조]] [[분류:알고리즘]] [[분류:컴퓨터 과학]]

큐(프로그래밍) - 편집 역사

Gaon12: 시작