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