4-2. Queue

생성일: 2021년 10월 8일 오후 5:03

Queue

• ordered group of homogeneous items
• FIFO : First in, First out
• 가장 먼저 들어온 것이 먼저 나간다.
• 운영체제에서 많이 사용
• Enqueue (ItemType newItem): 넣기
• Dequeue (ItemType& item) : 빼기
• 앞과 뒤를 가르키는 두개의 Stack Pointer가 필요
• 계속 뒤로 밀리는 형식이므로 갈수록 공간이 줄어든다.
  ⇒ 해결방법 : circular structure 형태로 구현
• rear, front 가 max에서 멈추지 않고 첫 번째 공간으로 이동함
• 문제점
  • full과 empty를 구별하지 못함 (둘다 rear + 1 == front)
• 해결방법 1
  • 공간중 하나를 빈공간으로 만들어 front가 계속 item이 없는 한칸 앞을 가르키게 함
  • full 일 때, rear + 1 == front
  • empty 일 때, rear == front
  • Intialize front and rear
    • 둘 다 한칸 뒤인 -1에서 시작 ⇒ circular structure이므로 제일 마지막 칸을 의미함
• 해결방법 2
  • length변수를 만들고 해당 변수가 Queue의 크기를 계속 트래킹하도록 함

부가설명

Palindrome(회문 체크)

회문 = 앞에서 읽으나 뒤에서 읽으나 동일한 문구

Palindrome인지 구분할 때 Stack과 Queue가 유용하게 사용될 수 있다.

1. 문장을 한글자 씩 Stack에 넣는다.
2. 같은 문장을 한글자씩 Queue에 넣는다.
3. Stack은 뒤에서부터 뺄 수 있고 Queue는 앞에서부터 한글자씩 다시 뺄 수 있다.
4. 이렇게 반복하면서 문장의 앞과 뒤를 한글자씩 비교한다.
5. 모든 글자가 동일하면 Palindrome 임을 알 수 있다.

Queue에서 반복문

Queue에서는 Stack과는 다르게 front와 rear 를 이용하여 반복문을 돌아야 한다.

이때 circular structure에서는 front가 rear보다 앞에 있을 수도 있고 뒤에 있을 수도 있다.

reserved space가 있어서 front가 한 칸 앞을 가르키고 있을 때 (가장 흔한 구조) Queue의 반복문은 다음과 같다.

for (int i = (front + 1) % maxQue; i != (rear + 1) % maxQue; i = (i +1) % maxQue)

front가 빈칸이기 때문에 한칸 더한 값부터 시작한다. i는 rear까지 포함시켜야 하므로 rear에 1을 더한값이 되기 전까지 한칸씩 늘어나게 한다.

여기서 주의해야 할 점은 i ≤ (rear + 1) % maxQue가 아니라 ≠을 사용한 것이다.

처음부터 front가 rear보다 큰 숫자일 때는 ≤가 바로 false가 되기 때문에 for문이 실행되지 않는다.

모든 위치를 나타내는 변수를 maxQue로 나눈 나머지로 이용해야 하는 것 또한 중요하다.

int i = (front + 1) % maxQue;
while(i != (rear + 1) % maxQue)
{
...
 i = (i +1) % maxQue;
}