큐

큐(Queue)

• 한 쪽 끝 위치(Rear)에서 새로운 항목을 삽입(Enqueue)하고, 다른 한 쪽 끝 위치(Front)에서 기존 항목을 삭제 및 반환(Dequeue)하는 논리적 선형 구조
  • 시간 순으로 먼저 삽입된 항목이 먼저 삭제되는 선입선출(FIFO : First-In, First-Out) 구조
  • Rear(뒤)에서만 삽입이 이루어지고 Front(앞)에서만 삭제가 이루어지는 특수한 리스트.
• python에서의 큐
  • python 리스트에서의 구현
    • enqueue : O(1) (append())
    • dequeue : O(N) (삭제 후 자리이동)
  • 단순 연결 리스트로 구현
    • enqueue : O(N)
    • dequeue : O(1) (pop())
  • 환형 연결 리스트 : enqueue dequeue 모두 O(1)

 

큐에 적용 가능한 주요 연산

• Queue() : 빈 큐 생성
• enqueue(item) : 기존 Rear 위치에 item 삽입
• dequeue() : Front 위치에 존재하는 item 삭제 및 반환
• is_empty() : 큐가 empty면 True 반환
• size() : 큐의 사이즈 반환