queue 자료구조

Kaydenna92·2022년 6월 9일
0

Algorithm

목록 보기
7/36

queue

  • 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식
  • stack과 반대되는 개념
  • 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 경우 사용

python 에서 queue 사용하기

  1. list 자료구조 사용
  2. Collections 모듈의 deque 사용하기
  3. queue 모듈의 Queue 클래스 사용하기

1. List 자료구조 사용

queue = [1,2,3]
queue.append(4)
queue.append(5)
print(queue)

>>> [1,2,3,4,5]

queue.pop(0)
>>> 1
queue.pop(0)
>>> 2
queue.pop(0)
>>> 3
  • list의 append() 함수를 이용하면 뒤에 데이터를 추가할 수 있음
  • pop(0) 함수를 사용하면 맨 앞의 데이터를 뺄 수 있음
    -> 큐 자료구조를 사용하는 효과
  • but, 시간 복잡도에서 O(N), N이 커질 수록 느려진다.

2. deque

from collections import deque
que = deque()

que.append(1)
que.append(2)
que.append(3)
print(que)
>>> deque([1, 2, 3])

que.popleft()
>>> 1
que.popleft()
>>> 2
  • O(1)의 시간복잡도를 가지고 있기 때문에 성능이 뛰어나다.
  • but, 무작위 접근의 시간 복잡도가 O(N)이고, 내부적으로 linked list를 사용하고 있기 때문에 N번째 데이터에 접근하기 위해 N번 순회가 필요.
  • appendleft() : 맨 앞에 데이터를 추가

3. queue

from queue import Queue
que = Queue()
que.put(1)
que.put(2)
que.put(3)

que.get()
>>> 1
que.get()
>>> 2
  • deque와 달리 방향성이 없기 때문에 데이터의 추가와 삭제가 하나의 메서드로 처리된다.
  • 데이터 추가 : put()
  • 데이터 삭제 : get()
profile
persistently

0개의 댓글