![]()
큐의 구현 큐는 두가지 방법을 통해서 구현할 수 있다 배열을 활용하여 선형 형태로 큐를 구현하는 것. 배열을 활용하여 원형 형태로 큐를 구현하는 것 선형 큐 다음처럼 선형 큐는 일반 선형 배열 형태로 구현한다. Front 와 Rear를 통해 큐의 맨 앞과 뒤를 표시한다. 초기상태의 표시를 위해 front와 rear는 -1로 시작한다. Front위치에는 아무것도 저장하지 않는다 공백 상태 : Front = Rear 포화 상태 : Rear = Max_index 선형 큐의 문제는 dequeue를 통해 요소를 큐에서 제거함에도 불구하고 배열 크기만큼의 데이터만 저장할 수 있다는 점에 있다. 즉, 아무리 dequeue연산을 통해서 요소를 제거해도 이미 이전에 5개의 요소를 저장한 바가 있다면 더 이상 해당 큐를 ..
![]()
큐 먼저 들어온 데이터가 먼저 나가는 형태의 자료구조를 말한다. 이를 선입선출(FIFO)이라고 한다. 큐의 가장 대표적인 예시는 매표소에서의 대기열을 들 수 있다. 먼저 대기줄에 들어온 사람이 먼저 나가게 되므로 이는 큐를 이해하기 적절한 예시이다. ADT 객체 : 0개 이상의 요소들로 구성된 선형 리스트 연산 : create(max_size) ::= 최대 크기가 max_size인 공백 큐를 생성한다. init(q) ::= 큐를 초기화 한다. is_empty(q) ::= size == 0이면 true 반환 is_full ::= size == max_size이면 true 반환 peek(q) ::= 큐의 가장 앞의 요소 값을 반환한다. enqueue(q, e) ::= 큐의 가장 뒤에 요소 e를 추가한다 de..
Queue & Deque 이번 챕터에서는 큐와 덱에 대해서 알아본다. 이전에 알아보았던 스택까지 합쳐서 스택, 큐, 덱에 대한 아주 간단한 아이디어는 다음과 같다. Stack 후입 선출 LIFO 예) 접시 쌓기 Queue 선입 선출 FIFO 예) 줄서기 Deque Double ended queue 즉, 앞과 뒤 말단에서 삽입,삭제 이루어짐. 이번 챕터에서 다루게 될 내용은 다음과 같다. 큐 선형 큐 원형 큐 예시) 버퍼 덱 선형 원형
