개념 - 큐 queue

선입 선출(FIFO).

용도 : 대기열. 버퍼, 등. 불규칙한 입력도 규칙적으로 나가게 할 수 있다.

스택과 마가지로 연결리스트로 구현 가능.

ADT:

enqueue(e)

dequeue()

isEmpty()

peek()

isFull()

size()

display()

배열 기반 큐를 구현 할 때 

선형적으로 구현하면 dequeue를 할 때 front의 값이 계속 커지므로, 언젠가 배열의 끝에 도달하게 된다. 

이를 방지하려면 원소를 앞으로 땡기는 복사를 해야하기에 비효율적이다. 

따라서 원형 큐 형식으로 구현하면 배열을 계속 사용할 수 있다. 

원형 큐를 구현할 때 생각해야 할 것

1. 한 칸을 비워둘 것인가?
큐에서 배열이 비워져있는지 아닌지는 front == rear의 결과로 판단한다. 

그런데 원형큐는 배열에 원소가 꽉 차있을 때에도 front == rear가 되어버린다. 따라서 enqueue시와 dequeue시에 데이터가 꽉찬건지 빈 건지 추적해줄 변수를 넣어야 한다. 한 칸의 크기가 엄청난 낭비가 아니라면 비워두는 게 보기 좋을 것이다. 비워두는 경우의 체크는 front == (rear + 1) % SIZE 면 충분하기에 간단하다.

2. front와 rear의 선 증가 후 연산,  선 연산 후 증가

enqueue를 할 때 rear의 값을 입력하고  ++시키냐, ++시키고 값을 입력하느냐에 약간의 차이가 있다.

전자의 경우는 먼저 인덱스 0부터 값을 입력하고 증가하기에, front는 곧 첫 원소의 인덱스고 rear는 원소 끝의 인덱스를 나타낸다.

후자의 경우는 front는 빈 공간의 인덱스가 되고 rear는 마지막 원소의 인덱스가 된다.

그렇담 어떤 걸 써야할까? 생각해봤는데 어느걸 쓰던 그에 맞게 함수를 구현 해놓으면 사용시에는 별로 상관 없다. 다만 클래스 내의 전치 후치 표현을 통일해서 해야한다는 걸 명심하자. 다음은 배열이 꽉 찼을 때의 비교 모습이다.

구현할 땐 반드시 그림을 미리 그려놓고 구현하도록 하자.

원형 큐 구현 : http://kid5.tistory.com/260

STL에서의 queue

std::queue는 컨테이너를 위한 어댑터(인터페이스) 역할을 한다. 벡터나 리스트도 queue 형식으로 사용할 수 있다는 뜻이다. 기본적으로는 std::deque를 컨테이너 클래스로 사용한다.

http://www.cplusplus.com/reference/queue/queue/

Member functions

(constructor)

Construct queue (public member function )

empty

Test whether container is empty (public member function )

size

Return size (public member function )

front

Access next element (public member function )

back

Access last element (public member function )

push

Insert element (public member function )

emplace 

Construct and insert element (public member function )

pop

Remove next element (public member function )

swap 

Swap contents (public member function )