큐
큐는 FIFO: First-In First-Out (선입선출) 구조이다.
큐의 응용
큐는 현실세계의 실제상황을 시뮬레이션 하는 상황에서 많이 응용된다.
선형 큐(Linear Queue)
1차원 배열을 이용하여 구현한 큐
- 선형큐는 삽입과 삭제를 반복하다보면 rear이 맨 마지막 인덱스를 가리키고 앞에는 비어있을 수 있지만 이를 꽉 찼다고 인식함.
- 배열에 앞부분이 비어 있더라도 사용하지 못한다.
- 요소들을 이동시키면 되지만 상당히 비효율
원형 큐(Calcular Queue)
배열이 원형으로 처음과 끝이 연결되어 있다는 개념
(실제로 원형으로 변화하는 것은 아니고 선형 큐와 마찬가지로 1차원 배열)
- 선형 큐의 문제점을 보안
- 선형 큐에서 간단하게 변경 가능
덱(deque)
덱(deque): double-ended queue
front와 rear에서 삽입 삭제가 가능한 큐
- 스택과 큐의 연산들을 모두 가지고 있음
- add_front, delete_front = push, pop
- add rear, delete_front = enqueue, dequeue
- 원형 큐에서 확장하면 손쉽게 구현
