큐(Queue)
큐(Queue)?
큐는 FIFO(First In First Out)구조로 가장 먼저 들어간 값이 가장먼저 나오는 구조입니다.
삽입하는 put 동작과 삭제하는 get 동작이 있습니다.
front(앞)에서 값을 얻어내고, rear(뒤)에 값을 넣습니다.
1. 큐 형태
2. 큐 종류
큐의 종류는 선형 큐, 원형 큐, 우선순위 큐 등이 있습니다.
- 선형 큐(Linear Queue) : 기본적인 큐의 형태로 막대모양의 큐로 빈 공간 사용 시 모든 자료를 꺼내거나 옮겨야 한다는 단점이 있음
- 원형 큐(Circular Queue) : 선형큐의 단점을 보완하는 구조로 front와 rear가 연결된 형태
- 우선순위 큐(Priority Queue) : 데이터 삽입 시 우선순위에 따라 정렬 후 저장하는 방식
배열을 이용한 원형 큐 예제
원형큐의 경우 front, rear 구분을 위한 공간이 하나 필요합니다.
그래서, 크기가 10인 큐의 경우 사용가능한 공간은 9가 됩니다.
큐로 사용할 int형 배열 선언 및 초기화 함수
초기화 함수
front와 rear값을 같게하면 초기화 가능
put 함수
(rear+1) % 큐 크기 == front 일 경우 오버 플로우 발생
원형큐는 아래 그림과 같이 모듈러를 생각하면 편합니다.
get 함수
front와 rear가 같을 경우 빈 값이므로 언더플로우 발생
큐의 값을 출력하는 함수
참고 : C로 배우는 알고리즘 (이재규)
'언어 > Data Strcuture' 카테고리의 다른 글
[C] 삽입 정렬(Insertion Sort) (0) | 2019.04.19 |
---|---|
[C] 선택 정렬(Selection Sort) (0) | 2019.04.19 |
[C] 트리(Tree) (0) | 2019.04.07 |
[C] 스택(Stack) (1) | 2019.03.29 |
[C] 연결리스트(LinkedList) (0) | 2019.03.28 |