[큐] 큐 Queue 6/7

1. 큐
ⓐ 특징
 - FIFO(First In First Out)의 선입선출
 - 저장된 순서에 의해 데이트거 나오는 자료 구조
 - 선형 자료구조

ⓑ Stack vs Queue
 Stack과 Queue에서의 차이는 자료의 추가, 삭제 및 반환에서 나타난다.

 일단 구조상 스택은 LIFO인 반면 큐는 FIFO를 가진다. 이에 따라 자료 추가/삭제시 다음과 같은 차이를 보인다.
 
  Stack : 제일 위인 Top에서만 자료의 추가, 삭제 및 반환 가능
  Queue : 추가 → 제일 뒤의 rear에서만 가능 / 삭제 및 반환 → 큐의 제일 앞인 front에서만 가능

ⓒ 주요 기능
 makeQue() : 큐 생성
 enQue() : 자료 추가
 deQue() : 자료 삭제
 peek() : 큐의 맨 앞 원소 반환               // Queue로 쓰는게 맞지만, 필자는 귀차니즘에 의해 Que까지만 쓴다...;

2. 배열에서의 큐
 enQue와 deQue과정을 보자.

순서는 12/34/56 이다...

  배열 큐에서 enQue와 deQue를 계속 하다 보면 자료가 뒤로 밀리며 위의 마지막과 같은 오류를 발생시킨다.
  이를 방지하기 위해 생긴것이 원형큐!!
  배열 큐에서만 존재하는 특수한 구조(원형 큐)에 대해서 보자.

3. 원형큐
 원형 큐에서는 모든 과정이 일반 큐와 같지만 front와 rear값의 증가시 최대 저장 개수 max변수를 이용하여
 배열이 꽉 차지 않는한 지속적으로 순환할 수 있게 만들어준 큐의 변형형태이다.
 원형 큐를 사용 할시 위의 6번 과정은 다음과 같이 변한다.

( rear + 1 ) % max 라는 수식을 이용

순환하도록 큐를 변환해준다.





4. 연결리스트에서의 큐
 연결리스트에서는 rear노드를 가르키는 pointer와 front노드를 가르키는 pointer를 사용하여
 enQue와 deQue를 실시한다.
 연결리스트에서 자료 추가와 삭제시에는 고려해야할 사항이 있다

 ⓐ 자료 추가
   - 공백 큐에 자료 추가시
    > front와 rear 포인터 모두가 새로운 노드를 가르킨다.
   - 공백이 아닌 큐에 자료 추가시
    > 현재 rear가 가르키고 있는 노드의 포인터에 새로운 노드 연결
    > rear노드에 새로운 노드 연결

 ⓑ 자료 삭제 
  - 자료가 2개 이상인 경우
   > 반환 포인터로 front 포인터 저장
   > front 포인터에 front -> next_node 값 저장
  - 자료가 1개 일때
   > 위의 과정에 추가적으로 rear값을 NULL로 바꿔준다.
------------------------------------------------------------------------------------------------

큐에 대한 전반적인 것을 보았습니다.

배열 원형큐와 링크드리스트 큐를 구현후 추후에 올리도록 하겠습니다~