1. 스택(Stack)
2. 큐(Queue)
3. 덱(Deque)
스택(Stack)과 큐(Queue)는 컴퓨터의 가장 기본적인 자료구조 중 하나입니다. 데이터를 임시 저장하기 위해 사용되는 자료구조이며, 데이터를 입력하고 출력하는 방향이 정해져 있다는 점이 서로 비슷합니다.
스택(Stack)
스택은 LIFO(Last In, Fisrt Out) 형태의 자료구조로 가장 마지막에 입력된 데이터가 가장 먼저 제거되는 구조 입니다. 흔히 박스는 아래에서부터 위로 차곡차곡 쌓고 박스를 치울 때는 위에 있는 박스부터 내리는 것과 같습니다. 파이썬으로 스택을 이용할때는 리스트 자료형을 사용하여 구현합니다. append() 메소드로 리스트의 가장 뒤의 데이터를 push하고, pop() 메소드로 리스트의 가장 뒤의 데이터를 꺼낼 수 있기 때문입니다.
큐(Queue)
큐는 FIFO(First in, First Out) 형태의 자료구조로 데이터를 넣을 때에는 스택과 마찬가지로 마지막에 데이터를 추가하지만 데이터를 꺼낼 때에는 가장 앞에 있는 것을 먼저 꺼냅니다. 흔히 우리가 놀이기구 줄을 설 때 먼저 온 사람이 먼저 타는 것과 같습니다. 리스트 자료형을 사용해서 큐를 구현할 수 있는데, append() 메소드로 enqueue(push)하고, pop(0) 메소드로 데이터를 빼는 dequeue(pop)를 사용합니다.
하지만 pop(0)은 O(n)의 시간복잡도를 가지기 때문에 큐를 구현할때는 리스트보다 덱(Deque)을 사용해서 구현합니다.
덱(Deque)
파이썬 내장 모듈인 collections 에 있는 것으로 스택과 큐를 합쳐놓은 듯한 자료구조라고 생각하면 됩니다. deque는 double - ended queue의 약자로 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조입니다. deque는 양방향이기 때문에 append(), pop()과 더불어 appendleft(), popleft() 메소드를 사용하여 앞에 데이터를 삽입하거나 제거할 수 있습니다. appendleft(), popleft() 메소드는 각각 시간복잡도가 O(1)이기 때문에 리스트보다 더 효율적입니다. 다만 유의할점은 deque의 pop은 리스트와 다르게 인덱스 번호를 뽑아 올 수 없기 때문에 pop(0) 와 같은 형식으로 사용하면 에러가 발생합니다.
from collections import deque
dq = deque() # 덱 생성
dq.append(1) # dq에 뒤로 데이터 넣기
dq.appendleft(2) # dq에 앞으로 데이터 넣기
print(dq) # deque([2, 1])
print(dq.pop(0)) # error
print(dq.pop()) # 1, 맨 뒤의 데이터 꺼내기
print(dq.popleft()) # 2, 맨 앞의 데이터 꺼내기
참고자료
'자료구조' 카테고리의 다른 글
| [자료구조] 힙(heap) (2) | 2024.01.22 |
|---|
댓글