스택, 큐, 덱
스택 (stack)
한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다.
데이터를 삽입하는 것을 흔히 Push, 데이터를 빼내는 것을 Pop이라고 하며 위에서 LIFO - Last In First Out라는 말에서 알 수 있듯이
가장 늦게 Push된 값이 Pop할 때 나오게 된다는 것이다.
그림으로 간단하게 살펴보자.
다음 그림과 같이 넣을 때는 가장 위에 Push가 되고 뺄 때는 가장 위에 있는 것이 Pop된다.
이러한 자료구조를 스택이라고하는데 파이썬으로 이를 살펴보면 다음과 같이 List로 쉽게 구현이 가능하다.
stack = []
for i in range(1, 6):
stack.append(i)
result = "stack pop : "
while stack:
result += str(stack.pop())
if stack: result += " -> "
print(result)
여기에서 보면 for문을 통해 스택에 차례대로 push되는 모습을 확인할 수 있고 그 후에 차례대로 pop되는 결과를 확인할 수 있다.
큐 (queue)
먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다.
삽입 즉, Push 자체는 스택과 동일하게 진행되지만 Pop에서 스택과 달리 FIFO(First In First Out)로 가장 먼저 Push된 값을 빼내는 것이다.
그림으로 간단하게 살펴보자
다음 그림과 같이 넣을 때는 가장 위에 Push가 되고 뺄 때는 가장 아래있는 것이 Pop된다.
이러한 자료구조를 큐라고 하는데 파이썬으로 이를 살펴보면 다음과 같이 Collections의 deque으로 쉽게 구현이 가능하다.
from collections import deque
deque = deque([])
for i in range(1, 6):
deque.append(i)
result = "queue popleft : "
while deque:
result += str(deque.popleft())
if deque: result += " -> "
print(result)
여기에서 보면 for문을 통해 큐에 차례대로 값이 push되는 모습을 확인할 수 있고 그 후에 차례대로 pop되는 결과를 확인할 수 있다.
덱 (deque)
덱은 스택과 큐을 합친 형태라고 생각하면 된다.
양쪽에서 삽입과 삭제가 가능하다.
앞에서 스택과 큐에 대한 설명으로 충분히 이해가 갔을테니 코드로 바로 살펴보자.
deque은 큐에 사용했던 deque을 그대로 사용하면 된다.
from collections import deque
#Case 1
deq = deque([])
for i in range(1, 6):
deq.append(i)
result = "deque append, popleft : "
while deq:
result += str(deq.popleft())
if deq: result += " -> "
print(result)
#Case 2
deq = deque([])
for i in range(1, 6):
deq.append(i)
result = "deque append, pop : "
while deq:
result += str(deq.pop())
if deq: result += " -> "
print(result)
#Case 3
deq = deque([])
for i in range(1, 6):
deq.appendleft(i)
result = "deque appendleft, popleft : "
while deq:
result += str(deq.popleft())
if deq: result += " -> "
print(result)
#Case 4
deq = deque([])
for i in range(1, 6):
deq.appendleft(i)
result = "deque appendleft, pop : "
while deq:
result += str(deq.pop())
if deq: result += " -> "
print(result)
다음과 같이 append, appendleft, pop, popleft를 활용하여 충분히 활용할 수 있다.
이에 대한 복잡도를 확실히 정리해보자.
복잡도
방금 위에서 설명한 삽입, 삭제의 연산들은 모두 O(1)으로 해결이 가능하기에 각각의 상황에 맞게 잘 활용하는 것이 중요하다고 볼 수 있다.