자료구조 중에서 정말 간단하고 기본이 되는 것이 바로 스택과 큐라고 생각한다.
스택(Stack)
👉 이미지 출처 : https://ooeunz.tistory.com/7
파이썬에서 스택은 list와 list 안에 함수를 이용하면 쉽게 구현할 수 있다.
push
stack = [1, 2, 3]
stack.append(4)
print(stack) # [1, 2, 3, 4]파이썬에서는 스택에 원소를 넣을때는 append를 쓴다. push는 존재하지 않는다.
pop
top = stack.pop()
print(top) # 4
print(stack) # [1, 2, 3]스택에서 원소를 제거할때는 pop을 쓴다. pop은 제거된 원소를 반환해준다. 만약 원소를 제거하지 않고 가장 위에 뭐가 있는지 알고 싶다면 stack[-1]을 쓰면 된다.
큐(Queue)
큐도 마찬가지로 list와 append(), pop(0)을 사용하면 뒤에서 추가하고, 앞에서 빼내는 것이 가능하다. 하지만 일반적으로는 deque 객체를 사용해서 구현하는데 그 이유는 뭘까? 🤔
list에서 pop(0)을 사용한다면 가장 앞에 원소를 제거하면 뒤에 있던 모든 원소들을 앞으로 한칸씩 이동해야 하기 때문에 시간복잡도는 O(N)이 된다. 이는 내부적으로 양방향 linked list를 사용하고 있기 때문이다.
하지만 deque도 단점이 있는데 무작위 접근의 시간복잡도가 O(N)이라는 것이다. 즉, i번째 데이터에 접근하려면 맨앞이나 뒤에서부터 i번(혹은 그보다 작은) 순회가 필요하다. 반면 list는 연속된 공간안에 저장되어있으므로 바로 접근이 가능하다. (🔎참고)
import
from collections import dequedeque를 사용하려면 collections모듈의 deque를 불러와야 한다.
append
queue = deque([1, 2, 3])
queue.append(4)
print(queue) # deque([1, 2, 3, 4])append 사용은 기본적으로 같다. 만약 가장 왼쪽에다가 추가하고 싶다면 appendleft()를 사용하면 된다.
popleft
deque에서는 pop(0)이 아니라 popleft()를 사용해서 왼쪽 원소를 제거해준다.
a = queue.popleft()
print(a, queue) # 1 deque([2, 3, 4])아. 그냥 pop()을 사용할 수는 있다. 이때는 가장 뒤 원소를 제거해준다.
🤚 맨뒤에서 추가하고 맨앞에서 빼내거나, 맨앞에서 추가하고 맨뒤에서 빼내거나 상관은 없다. 하지만 나는 일반적으로 append와 popleft를 많이 사용한다.
References
