04-1 큐(Queue)

※ 큐란?

스택과 다르게 한쪽에선 삽입연산이 일어나고 한쪽에서는 삭제연산이 일어나는 선입선출(FIFO, First In First Out)의 

자료구조.

한쪽은 프론트(front)로 정하여 삭제연산만 수행하고 한쪽은 리어(rear)로 정하여 삽입 연산만 수행하도록 제한한다. 

큐에서 이루어 지는 삽입연산을 enQueue라 하고 삭제연산을 deQueue라 한다.

※ 선형큐와 원형 큐

선형 큐는 우리가 생각하는 일반적인 큐(바로 위의 그림)이며 원형 큐는 선형큐를 말아논것과 같은 개념이다.

물리적인 형태는 같지만 코딩을 통해 원형의 형태의 개념으로 구현할 수 있다.

원형큐의 장점과 각각의 차이점은 04-2에 있으니 기억이 나지 않으면 가서 확인하자.

※ 연결 큐와 덱

연결 큐와 덱 모두 연결 자료구조를 사용해 구현한다.

연결 큐는 왼쪽 아래 그림과 같이 선형 큐와 같지만 연결 자료구조로 구현한 것이고

덱은 오른쪽 아래와 같이 큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로, 스택의 성질과 큐의 성질을 모두가지고 있다.