파이썬 스택, 큐

파이썬에서 스택과 큐를 사용하는 방법을 알아봅시다!!

 

스택(Stack)

 - 나중에 넣은 데이터가 먼저 반환되도록 설계한 메모리 구조

 - Last In First Out (LIFO)

 - 데이터의 입력은 Push ( append() ), 출력은 Pop ( pop() )

 

큐(Queue)

 - 먼저 넣은 데이터가 먼저 반환되도록 설계한 메모리 구조

 - First In First Out (FIFP)

 - 데이터의 입력은 Push ( append() ), 출력은 Pop ( pop(0) )

 

큐에서 pop(0)을 하면 앞에서 하나를 비우고 뒤에 있는 모든 데이터들을 한칸씩 앞으로 당기는 작업을 한다.

따라서 시작 복잡도가 O(n)이 걸린다. (너무 느림!!)

 

from collections import deque # (*deque는 double ended queue의 약자입니다)
queue = deque()
queue.append(1)
queue.append(2)
queue.popleft() # 1
queue.popleft() # 2

그래서 일반적으로 위와 같은 방법을 많이 쓴다.