[자료구조] 큐

 

1. 자료구조
   1. 연결 리스트
   2. 이진 트리
   3. 스택
   4. 큐
   5. 해시
2. 정렬
   1. 버블 정렬
   2. 선택 정렬
   3. 삽입 정렬
   4. 퀵 정렬
   5. 힙 정렬
3. 알고리즘
   1. 재귀 함수
   2. 너비 우선탐색(BFS)
   3. 깊이 우선탐색(DFS)
   4. 다익스트라

---

 

큐(Que)

Que의 구조

 

큐는 기본적으로 선입선출(First In First Out)을 따른다.

큐라는 배열에 Enque()를 통해 데이터를 입력하고

Deque()를 통해 먼저 들어온 값부터 출력하는 구조이다.

 

---

 

Enque

Enque()

 

1. rear가 가리키는 위치에 데이터를 입력한다.
2. rear를 1증가시킨다.
3. 만일 rear가 큐의 max보다 크면 0으로 초기화한다.

 

 

Deque

Deque()

 

1. front가 가리키는 위치의 데이터를 출력한다.
2. front를 1증가시킨다.
3. 만일 front가 큐의 max보다 크면 0으로 초기화한다.

 

---

 

소스코드

#define __main

#ifdef __main

#include <stdio.h>

typedef struct __Que{
	int* que; // 큐

	int max; // 큐의 최대입력 개수
	int num; // 현재 큐에있는 데이터 개수
	int front; // Deque할 위치
	int rear; // Enque할 위치
} Que;


void Init(Que* q, int max) {
	q->que = malloc(sizeof(int) * max);

	q->max = max;
	q->front = q->rear = q->num = 0;
}

int Enque(Que* q, int x) {
	if (q->num >= q->max) return -1; // 큐가 가득참

	q->num++;
	q->que[q->rear++] = x;

	q->rear %= q->max; // 0 -> 1 -> ... -> max -> 0 -> 1

	return 0;
}

int Deque(Que* q, int* x) {
	if (q->num <= 0) return -1; // 큐가 비어있음

	q->num--;
	*x = q->que[q->front++];

	q->front %= q->max; // 0 -> 1 -> ... -> max -> 0 -> 1

	return 0;
}

int main() {
	Que* q = malloc(sizeof(Que));
	int tmp;

	Init(q, 10);

	Enque(q, 4);
	Enque(q, 3);

	Deque(q, &tmp);
	Deque(q, &tmp);

	q->max = q->num = q->front = q->rear = 0;
	free(q->que);

	return 0;
}

#endif