[WIL]Queue(Python)

1. Queue(큐)란?

• Queue(큐)는 컴퓨터의 기본적인 자료구조로써 여러 데이터가 입력되면 먼저 입력된 데이터가 먼저 사용되는 것을 의미하며 FIFO(First In First Out)라고 불리기도 한다.
  나중에 입력된 값이 먼저 나가는 LIFO(Last In Frist Out)의 구조인 Stack과 반대의 개념이다.

• 큐라는 개념은 컴퓨터에서만 사용되는 것이 아닌 일상에서 자주 사용하는 개념을 가지고 온 것이다. 우리가 음식점 앞에 줄서있다고 가정한다면 먼저 도착한 손님이 먼저 식당을 이용하게 되는데 이런 것들을 큐라고 볼 수 있다.

2. python에서의 Queue

• Linked list를 통해 큐를 구현하거나 list를 사용할수도 있지만 python에서는 deque(데크)라는 자료구조를 제공한다.
  List를 이용한다면 Queue를 간단하게 구현할 수 있다. List 자료구조의 pop()함수를 이용해 pop(0)를 하게 되면 리스트의 첫번째 값을 리스트에서 제거하며 반환하게 된다.
  여기서 List에서 첫번째 데이터를 제거할 경우 다음에 존재하는 데이터들을 1칸씩 앞으로 당기게 된다.
  이런 연산으로 인해 List의 pop(0)는 O(n)의 시간복잡도를 가지게 된다.

• 반면 deque는 양방향 큐를 이용해 구현되어 있는 자료구조로 양방향으로 데이터 입출력이 가능하고 양방향모두 O(1)의 시간복잡도로 접근할 수 있다는 장점이 있다.

3. List vs Deque

queue = [1,2,3,4,5,6]
queue.append(7)
[1,2,3,4,5,6,7]
queue.pop(0)
[-,2,3,4,5,6,7]
[2,-,3,4,5,6,7]
[2,3,-,4,5,6,7]
[2,3,4,-,5,6,7]
[2,3,4,5,-,6,7]
[2,3,4,5,6,-,7]
[2,3,4,5,6,7]

• 위의 코드는 list를 이용한 queue의 예제이다.
  queue에 7이라는 값을 넣어준다면 queue의 마지막에 찾아가서 붙게될 것이다.
  문제는 queue.pop(0)이다. pop(0) 연산을 실행할 경우 list는 첫번째 데이터를 반환한 후 뒤에 존재하는 데이터들을 모두 1칸씩 앞으로 옮기게 되는데 이것을 shift된다고 하고 O(n)의 시간복잡도를 가지게 된다.

from collections import deque
queue = deque([1,2,3,4,5,6])
queue.append(7)
1-2-3-4-5-6-7
queue.popleft()
2-3-4-5-6-7

• 반면 deque의 경우 popleft()라는 함수를 통해 첫번째 값을 반환할 수 있는데 list와는 다르게 양방향 큐로써 첫번째 데이터를 제거하더라도 다른 데이터를 움직일 필요없이 다음에 존재하는 데이터를 첫번째 데이터로써 가리키면 됨으로써 O(1)의 시간 복잡도를 가진다.