Stacks and Queues(3) : Queues

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