큐(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)
- python 리스트에서의 구현
큐에 적용 가능한 주요 연산
- Queue() : 빈 큐 생성
- enqueue(item) : 기존 Rear 위치에 item 삽입
- dequeue() : Front 위치에 존재하는 item 삭제 및 반환
- is_empty() : 큐가 empty면 True 반환
- size() : 큐의 사이즈 반환