큐(Queue)

큐(Queue)

• 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조
• 양쪽으로 입구와 출구가 모두 뚫려있다고 생각하면 된다.
• 줄을 서는 행위와 유사하다.
  • 놀이공원에 입장하기 위해 줄을 설 때, 먼저 온 사람이 먼저 들어가게 되는 것
• 선입선출, FIFO(First In First Out) 구조

큐 동작 예시

• 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() 이라고 할 때
  

• 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
  

• 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
  

• 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
  

• 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
  

• 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
  

• 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
  

• 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
  

• 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
  

https://freedeveloper.tistory.com/370?category=888096

큐 구현 예시

💡 list 이용

queue = [1, 2, 3]
queue.append(4)
~~> queue : [1, 2, 3, 4]

queue.append(5)
~~> queue : [1, 2, 3, 4, 5]

queue.pop(0)
~~> queue : [2, 3, 4, 5]

queue.pop(0)
~~> queue : [3, 4, 5, 6]

queue = [3, 2, 1]
queue.insert(0, 4)
~~> queue : [4, 3, 2, 1]

queue.insert(0, 5)
~~> queue : [5, 4, 3, 2, 1]

queue.pop()
~~> queue : [5, 4, 3, 2]

queue.pop()
~~> queue : [5, 4, 3]

• list는무작위 접근에 최전화된 자료 구조이기 때문에 성능 측면에서 추천되지 않는다.
• 기존에 queue가 담고 있던 모든 데이터를 앞/뒤로 쉬프트(shift)해주지 않으면 queue[i]의 결과값이 정확하지 않을 수 있다.
• 시간 복잡도 : O(N)
  
  

💡 deque 이용

• collections 모듈의 deque는 double-ended queue의 약자로 데이터를 양방향에서 추가하고 제거할 수 있게 해주는 자료 구조이다
• list에는 없는 popleft()라는 메서드를 제공해주어 첫 번째 데이터를 제거할 수 있게 해준다.

from collections import deque

queue = deque([1, 2, 3])
queue.append(4)
~~> queue : deque([1, 2, 3, 4])

queue.append(5)
~~> queue : deque([1, 2, 3, 4, 5])

queue.popleft()
~~> queue : deque([2, 3, 4, 5])

queue.popleft()
~~> queue : deque([3, 4, 5])

from collections import deque

queue = deque([3, 2, 1])
queue.appendleft(4)
~~> queue : deque([4, 3, 2, 1])

queue.appendleft(5)
~~> queue : deque([5, 4, 3, 2, 1])

queue.pop()
~~> queue : deque([5, 4, 3, 2])

queue.pop()
~~> queue : deque([5, 4, 3])

• popleft()와 appendleft()메서드 모두 O(1) 의 시간 복잡도를 가진다.
• 하지만 자료 구조 특성상 무작위 접근의 시간 복잡도 : O(N)
  - 내부적으로 linked list를 사용하고 있기 때문에 i번째 데이터에 접근하려면 앞/뒤부터 i번 순회해 접근할 수 밖에 없다.
  
  

💡 Queue 사용

• 멀티 쓰레딩(threading) 환경에서 사용
• 내부적으로 라킹(locking)을 지원하여 여러 개의 쓰레드가 동시에 데이터를 추가하거나 삭제할 수 있다.
• deque와 달리 방향성이 없기 때문에 데이터 추가와 삭제가 하나의 메서드로 처리
  • 데이터 추가 : put(x)
  • 데이터 삭제 : get()

from queue import Queue

que = Queue()
que.put(1)
que.put(2)
que.put(3)
que.get()
~~> 1

que.get()
~~> 2

que.get()
~~> 3

• Queue의 성능도 deque와 마찬가지로 데이터를 추가 및 삭제 : O(1),
  데이터 접근은 O(N) 의 시간 복잡도를 가진다.