파이썬 stack and deque(덱) + 예제 코드

덱은 무엇일까? 덱을 이해하려면 기존의 stack을 이해하고 있어야한다.

stack은 후입선출구조를 가지고 있다. 아래 사진을 보면 단번에 이해가 갈것이다.

stack 설명

이제 덱을 알아보자 덱은 기존 stack에서 먼저 들어간 자료를 빼내려면 시간복잡도 O(N)을 소요해 원소를 빼내는 단점을 보완할 수 있는 자료구조이다. 따라서 리스트의 앞부분을 조작하고 싶을때 많이 사용된다. 추후 BFS문제에 필수로 사용되니 꼭 알고 넘어가자.!!

stack =[0,2,1,5] 일때 stack.pop(0)을 해주면 stack의 가장 앞부분인 0이 삭제되긴 하지만 시간복잡도 O(N)을 가짐.

놀랍게도 덱을 사용하면 첫번째 원소를 빼는 작업을 O(1)만에 수행할 수 있다. 우선 덱을 사용하려면 모듈을 가져와야 한다. 사진을 통해 설명하겠다.

from collections import deque

deque 작동원리 설명

아래와 같은 소스코드를 실행시켜 보면서 deque와 stack사용법을 익혀보자.

 

from collections import deque

list_0 =[]
list_0.append(1)
list_0.append(2)
list_0.append(3)
print('list_0:',list_0)
list_1 = deque(list_0)#list_0을 deque자료형으로 바꿀 수 있음.
print('list_1:',list_1)
list_1.appendleft(0)
list_1.append(4)
print('list_1:',list_1)
list_1.append(list_1.popleft())#이렇게 하면 처음 원소를 마지막 원소로 넘길 수 있음.
print('list_1:',list_1)
list_1.appendleft(list_1.pop())#이렇게 하면 마지막 원소를 처음 원소로 넘길 수 있음.
print('list_1:',list_1)

https://www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

위에 문제를 풀어보는걸 추천한다..!!