스택(Stack)
FILO
(First In, Last Out) 구조를 띄고 있는 자료구조로, 삽입과 삭제 연산이 동일한 한군데에서 발생
- 삽입과 삭제 연산에 있어 시간복잡도가
O(1)
- 이전에 활용한 데이터를 역으로 추적하거나, 나중에 들어온 데이터가 빨리 나가야할때 사용
- Python에서는 LifoQueue라는 구현체가 있으나,
List
의 pop을 활용하면 스택처럼 사용 가능
큐(Queue)
FIFO
(First In, First Out) 구조를 띄고 있는 자료구조로, 삽입과 삭제 연산이 서로 다른 곳에서 발생
- 삽입과 삭제 연산에 있어 시간복잡도가
O(1)
- 맨 앞을 front, 맨 뒤를 rear, 삽입 연산을 enqueue, 삭제 연산을 dequeue라고 함
- 주로 순차적으로 진행되는 일을
스케쥴링
할때 사용
- Python에는 Queue가 있으나, 효율성 측면에서 주로
deque
를 사용
큐의 구현
List 😵
- 끝 원소 삭제 :
O(1)
- 임의의 원소 삭제:
O(n)
- 삭제후 모든 원소를 이동시켜야함
👉🏻 그러니 리스트로 큐처럼 사용하지 말것!
list = []
list.append(x)
list.pop(0)
Queue 😔
- 데이터 추가/삭제:
O(1)
- 인덱스 접근 불가
- 멀티스레드 환경에 최적화되어있음
from queue import Queue
q = Queue()
q.put(x)
q.get()
deque 🤩
- 큐와 스택의 구조를 합친 자료구조로 양쪽에서 삽입과 삭제 가능
- 데이터 추가/삭제:
O(1)
- 인덱스 접근 가능
👉🏻 코딩테스트 환경에서는 덱을 쓰는것이 적합
from collections import deque
q = deque([0])
q.appendleft(1); q.append(2)
q.popleft(); q.pop()
q.rotate(1)
q.rotate(-1)
PriorityQueue
- 데이터 추가/삭제: O(log n)
- 기본 정렬은 첫번째 요소에 대한 오름차순
from queue import PriorityQueue
pq = PriorityQueue(maxsize=8)
pq.put(4)
pq.put(1)
pq.put(7)
pq.put(3)
print(que.get())
que.put((3, 'A'))
que.put((1, 'B'))
que.put((2, 'C'))
print(que.get()[1])
print(que.get()[1])
print(que.get()[1])
Reference
🔗 https://github.com/VSFe/Algorithm_Study