Queue API
- Queue 자료구조는 Stack과 정반대의 특성을 지닙니다.
- 대표적으로 FIFO, 들어온 순서대로 나가는 특성을 지니고 있죠.
Queue: linked-list representation
- 파이썬에서는 포인터라는 개념이 없기 때문에 더욱 어색하지만 개념은 간단한 것 같습니다.
- 아이템을 추가할 때는 맨 앞에, 제거할 때는 맨 뒤에서 하다보니 가리키는 주소값이 두 군데여야 한다는 것입니다.
Queue dequeue: linked-list implementation
Queue: linked-list implementation in Java
- 굳이 파이썬으로 이런 코드를 짤 필요는 없는 것 같습니다..
단순히 deque를 불러와서 추가할 줄만 알면 충분합니다.
참고로 popleft를 쓰면 배열의 맨 앞에 원소를 추가할 수 있습니다. - performance에 대해 조금만 더 생각을 해보면, 최악의 경우 원소를 추가하는 것은 상수 시간, 제거하는 것은 선형 시간이 소요됩니다.
- linked list의 맨 앞을 찾는 것은 다른 추가 작업이 필요하지 않기 때문에 상수 시간이 걸립니다.
- 하지만 맨 끝의 값을 찾는 것은 N개로 이어진 각 노드들을 모두 타고 넘어가야 하기 때문에 선형 시간(N)이 소요됩니다.
Queue: resizing array implementation
출처: Coursera, Algorithms, Part 1, Princeton University
'Algorithms, Part 1 > 2주차' 카테고리의 다른 글
Stacks and Queues(6) : Stack and Queue Applications(optional) (0) | 2023.04.12 |
---|---|
Stacks and Queues(5) : Iterators (0) | 2023.04.12 |
Stacks and Queues(4) : Generics (0) | 2023.04.12 |
Stacks and Queues(2) : Resizing Arrays (0) | 2023.04.11 |
Stack and Queues(1) : Stacks (0) | 2023.04.11 |