5.2 Linked Structures - Queue

생성일: 2021년 10월 15일 오후 9:44

기존의 Queue를 Linked Structure로 구현

Queue in Linked Structures

• 여기서는 reversed space와 같은 Array로 구현한 Queue에서 필요한 개념이 필요 없다.
• 포인터 변수 2개로 front와 rear를 트래킹한다.
• Array 로 구현한 Queue와 다르게 처음으로 아이템을 넣을 때 front 도 rear처럼 그 아이템을 가르키도록 해야한다.
• front가 nullptr이면 해당 Queue는 비어있다.
• rear가 가르키고 있는 Node의 next 값이 nullptr이면 Queue의 마지막 아이템이다.
• 아이템 추가 (Enqueue)
  • 새로운 아이템을 담은 노드 생성
  • 비어있는 큐라면 front도 새로만든 노드를 가르키게 함
  • 이전의 rear가 가르키는 노드의 next가 새 노드를 가르키게 함
  • rear가 새로 만든 노드를 가르키게 함
• 아이템 제거 (Dequeue)
  • tempPtr이 기존의 front가 가르키고 있던 노드를 가르키게 함
  • front를 기존의 front가 가르키고 있던 노드의 next 값을 가지게 함
  • tempPtr을 delete

Array와 Linked로 구현한 Queue의 비교