끄적끄적 코딩
article thumbnail

큐 (Queue)

한쪽 끝(rear)에서는 삽입연산만 이루어지며 다른 한쪽 끝(front)에서는
삭제연산만 이루어지는 FIFO(First In First Out) 형식의 자료구조

https://untitledtblog.tistory.com/70


큐의 연산

- enqueue : 큐에 데이터를 넣는 작업
- dequeue : 큐에서 데이터를 꺼내는 작업
- front : 데이터를 꺼내는 부분에 데이터를 반환
- rear : 데이터를 넣는 부분에 데이터를 반환

시간복잡도

삽입/삭제 : 원소를 삽입 삭제하는 경우 O(1)
검색 : 탐색을 하려면 원소를 하나하나 꺼내 확인해야 한다. O(n)

선형 큐

일반적인 큐의 형태

push가 될 때 rear(back) 포인터를 하나 증가, pop이 될 때마다 front 포인터를 증가하는 방식으로 구현

큐에 데이터를 넣는 경우: 프론트는 고정, 리어가 추가되는 데이터를 가리키며 이동함

데이터를 삭제시(Front가 고정):데이터가 삭제될 때 마다 데이터를 한칸씩 이동해야 한다.

데이터를 삭제시(Rear가 고정) : 프론트의 포인터가 증가하며 내보낼 데이터를 순차적으로 가리킴

 

선형 큐 문제점

Rear가 배열의 끝까지 이동이 되면 더이상 새로운 데이터를 받을 수 없음. 가득 찼다고 판단
이런경우를 해결하려면 재정렬이 필요하다.

 

원형 큐

리어를 다시 첫번째를 가리키게 하여 저장공간을 순환적으로 사용하는 큐
선형큐의 단점을 보완하기 위해 만들어짐
rear와 front가 같은 곳을 가리키는 경우 빈 원형큐를 의미

데이터 삽입

 

데이터 삭제

 

데이터 포화 상태

칸이 비어있는 이유 : rear와 front가 같은 곳을 가리키면 비어있는지 포화인지 알 수가 없기 때문

'자료구조' 카테고리의 다른 글

덱 (Deque)  (0) 2021.05.07
우선순위 큐 (Prioity Queue)  (0) 2021.05.06
스택 (Stack)  (0) 2021.05.06
힙 (Heap)  (0) 2021.05.05
트리 (Tree), 이진 트리 (Binary Tree)  (0) 2021.05.05

검색 태그