큐(Queue)

큐(Queue)

• FIFO : First In First Out / 먼저 들어온 게 먼저 나간다
• 시간 복잡도
  • 삽입, 삭제 : O(1)
  • 검색 : O(n)
• 용어
  • Enqueue : 삽입
  • Dequeue : 삭제
  • Front : 앞, 삭제되는 곳
  • Rear : 뒤, 삽입되는 곳
• 배열의 경우 원형 배열로 구현을 추천
  • 선형일 경우, 삭제해도 데이터가 계속 밀려나는 현상이 일어난다.
• 아니면 연결 리스트를 사용해 구현
• 예 : 은행의 번호표(Queue)