Goal
큐(Queue)
특징
원형 큐(Circular Queue)큐를 논리적으로 원형 형태로 설계한 자료구조 원형큐는 큐를 배열로 구현했을 때 발생하는 문제점을 보완하기 위해 고안된 자료구조이다. 배열을 사용해서 큐를 구현할 경우 다음과 같은 문제가 있다.
위와 같은 문제(index가 증가만 하는 문제)로 배열을 이용하여 큐를 구현할 경우 선형 큐 대신 원형 큐로 구현한다. 구현 방법은 다음과 같다.
즉, 인덱스 = '(인덱스+1) % 큐의 배열 최대 크기' 로 front, rear 인덱스를 계산 (인덱스 % (MaxSize-1) 로 하지 않는 이유는 MaxSize가 1일 경우 0이 되기 때문) 여기서 환형 큐의 front, rear는 메모리 상에서 배열의 시작과 끝이 아닌, 논리적인 시작과 끝점이다 위와같이 구현하면 모든 큐 공간을 활용할 수 있게 된다. (문제 해결) 큐의 추상 자료형(ADT)객체 : FILO(선입 후출)의 접근 방법을 유지하는데 필요한 요소들의 모음
큐의 구현BOJ 큐 구현 문제 : https://www.acmicpc.net/problem/18258 - 배열 큐 - https://github.com/jihyuk124/DataStructure/tree/master/03.Queue%2C%20Deque/ArrayQueue - 연결 리스트 큐 - https://github.com/jihyuk124/DataStructure/tree/master/03.Queue%2C%20Deque/LinkedListQueue 구현 예시배열, 링크드 리스트로 스택 구현 (기초 : int를 담는 큐 구현, 심화 : 큐의 템플릿화) 큐의 사용 예시
1. 개요 선형 큐 (Linear Queue) 의 삽입 및 삭제 과정 스택(Stack)자료구조와 달리 선입선출(先入先出, First In First Out;
FIFO)의 자료구조로써, 데이터가 나가는 위치, 큐의 첫번째 위치를 Front 라고 하고 데이터가 삽입되는 지점, 큐의 마지막 데이터의 한 칸 다음 위치를 Rear 혹은 Back이라고 한다. 1. 선형 큐 (Linear Queue) 예를들어 큐 사이즈가 5인 큐가 있다고 하자. ( Front == Rear ) ( 큐 사이즈 == Rear) 2. 원형 큐 (Circular Queue) 원형 큐 (Circular Queue) 원형 큐 (Circular Queue)는 선입선출(先入先出, First In First Out; FIFO)를 그대로 유지하면서 큐의 입구와 출구를 연결하여 원형으로 만들어 사용하는
구조이다. 2. 코드 구현 2-1) 구조체 선언 큐를 관리하는 구조체, 2-2) 큐 생성 큐를 초기화 및 생성하는
함수 2-3) 데이터 삽입 (Enqueue) 큐에 데이터를 삽입하는 함수 2-4) 데이터 삭제,출력 (Dequeue) 큐에서 데이터를 빼와 출력하는 함수 2-5) 큐 상태 검사 큐가 비었는지 확인하는 함수로 Front와 Rear가 같을때 큐가 빈것으로 판별 |