Queue

Queue의 정의

• 순서가 있는 list, 각각의 끝에서 자료의 삽입과 삭제가 일어나는 자료구조
• 선입선출 FIFO
  • rear : 데이터의 삽입이 일어나는 곳
  • front : 데이터의 삭제가 일어나는 곳
  • addQ / Enqueue : 삽입 연산
  • deleteQ / Dequeue : 삭제 연산

stack과의 차이점

• stack : top으로 관리
• queue : rear와 front로 관리

선형 큐

• 초기 상태 : front & rear == -1
• 공백 : front == rear
• 포화상태 : rear = n-1

선형 큐의 문제점

• 큐의 크기가 5일 때, rear가 4로 판단하면 0~3 까지 자리가 남아도 포화상태라고 판단
  -> 포화 상태의 잘못된 인식 rear == n-1

• 큐 생성

n = 5 # Queue의 크기 

rear = -1 
front = -1 

my_q = [None] * n # queue 생성 

• addQ

rear += 1 # 0
my_q[rear] = 'A'

print(my_q)

rear += 1 # 1
my_q[rear] = 'B'

rear += 1 # 2
my_q[rear] = 'C'

• Dequeue

front += 1
my_q[front] = None

print(my_q)

원형큐

• 선형큐가 가지고 있는 문제를 보완하기 위해 사용

  • front의 위치와 상관 없이 rear == qSize -1 일 때 == '포화'
    • 여유 공간이 있어도 더 이상 값을 할당 할 수 없는 문제 (꽉 안찼는데 꽉찼다함)

• 초기 상태 : front = rear = 0

  • 선형큐에선 -1

• 메모리 누수 걱정 없이 무한한 AddQ와 DeleteQ를 할 수 있다

  • 하지만, front == rear가 is_empty와 is_full의 조건인건 여전
    • 비어있는지? , 차있는지 ?
      • 해결책
        • flag
        • number_of_ele_in_q = 0
          • AddQ 할 때 + 1
          • DeleteQ 할 때 -1