파이썬 - stack(스택), queue(큐)

목차

-시작

-stack

-queue

-문제

시작

stack과 que는 핵심 유형으로 분류될 만큼 중요한 자료구조입니다.
또한 다양한 알고리즘에 응용이 되어 사용됩니다.
이 두 알고리즘은 개념적으로 쉽지만.
처음 접한다면 문제에 응용하는데 까다롭습니다.
그래서 꼭! 문제를 풀어 보고 어떤 상황에 사용하면 좋은지 익혀야 합니다.

stack

stack은 사전에서 찾아보면.
쌓아 올린다는 뜻을 가지고 있습니다.
그래서 stack 자료구조는 자료가 들어오면 맨위에 쌓고.
자료가 나갈떈 마지막에 쌓아 올린 자료를 내보냅니다.

stack 자료구조에 데이터를 저장하는 행위를 push라고 하고.
마지막 데이터를 빼내는 행위를 pop이라고 합니다.

위의 그림은 텅!빈 스택에 1과 2를 순차적으로 들여보내고(push).
이들을 다시 내보내는(pop) 그림입니다.

파이썬에서 stack구현

파이썬에서 stack은 다양한 방법으로 구현이 가능하지만.
push와 pop을 진행할때 O(1)의 시간복잡도를 가져야 합니다.

이게 무슨 말이냐. 이해를 위해 예를 들어 봅시다.
파이썬에서 stack을 구현할 떄 가장 많이 사용하는 방법은 list를 이용하는 방법입니다.
list를 스택으로 보고 왼쪽에서 오른쪽으로 쌓아올린다고 생각을 합니다.
그러면 append() 메서드를 push로 pop() 메서드를 pop으로 대응 시킬수 있습니다.

stack = []
stack.append(1)
stack.append(2)
stack.pop()
stack.pop()


-----출력결과
[1]
[1, 2]
[1]
[]

 

note

append(ele)는 리스트의 가장 마지막에 파라매터로 받은 ele를 추가하는 메서드이고
pop(i)은 리스트의 i번째 원소를 제거하고 그 값을 리턴하는 메서드입니다.
만약 pop에 파라매터가 없다면, 마지막 원소를 제거하고 리턴합니다.

만약에 list를 스택으로 보고 오른쪽에서 왼쪽으로 쌓아 올린다고 생각하면 어떨까요?
그러면 pop하면 위와 달리 가장 앞의 원소가 제거되고 값을 리턴해야 합니다.
이를 구현해 보면

stack = []
stack.insert(0, 1)
stack.insert(0, 2)
stack.pop(0)
stack.pop(0)

----출력결과
[1]
[1, 2]
[1]
[]

note

insert(i, ele)는 리스트의 i번째 위치에 ele를 추가하는 메서드입니다.

이 둘의 차이는 무었일까요? 단순히 뱡향의 차이만 있을까요?
파이썬의 list는 맨뒤의 원소를 추가 삭제 하는데 O(1)의 시간 복잡도가 사용이 되지만.

맨 앞의 원소를 추가, 삭제 하기 위해서는 O(n)의 시간 복잡도가 사용됩니다.

여기서 n은 리스트의 길이입니다.

이에 대한 사항이 이해가 안되신 다면 여기를 클릭해 주세요.

클릭 !

그래서 후자의 경우 stack을 제대로 구현했다고 생각할 수 없습니다.list의 append()와 pop()을 이용하여 구현합시다.

queue

queue는 '줄을 서서 기다린다' 라는 의미를 가지고 있습니다.
그래서 가장 마지막에 들어온 자료가 가장 먼저 나갔던 stack과 달리.
가장 먼저 들어온 자료가 가장 먼저 나가는 자료구조입니다.
queue에서 자료가 들어오는 행위를 enqueue라고 하고.
나가는 행위를 dequeue라 합니다.

파이썬에서 queue구현

자! 큐를 구현해 봅시다.

어떻게 할까요?

잘모르니까.

list로 비벼봅시다.

stack에서 했던대로 append(ele)와 pop(0)을 이용하면 구현할 수 있을 것 같습니다.

append(ele)를 이용하면 데이터가 왼쪽에서 오른쪽으로 쌓이고.

가장 먼저들어온 데이터는 list의 0번쨰에 위치한 자료입니다.

이를 pop(0) 메서드를 이용하면 제거할 수 있습니다.

하지만!!

pop(0)는 O(n)의 시간복잡도를 가지고 있습니다.

슈레기 구현이란 것이죠.

queue도 입력, 삭제 모두 O(1)이 되어야 합니다.

 

리스트를 이용하여 입력, 삭제 모두 O(1)로 만드는 것은 불가능합니다.

그래서 파이썬에서는 deque라는 모듈을 제공하고 있습니다.

enqueue는 deque의 append()메서드로

dequeue는 popleft() 메서드로 사용하면 모두 O(1)의 시간복잡도로 구현할 수 있습니다.

popleft()는 리스트이 pop(0)와 비슷하게 첫번째 원소를 제거하고 이를 리턴하지만.

내부적인 구현이 달라 제거시 시간복잡도가 O(1)입니다.

from collections import deque

q = deque()

q.append(1)
print(q)

q.append(2)
print(q)

q.popleft()
print(q)

q.popleft()
print(q)

.............출력 결과
deque([1])
deque([1, 2])
deque([2])
deque([])

 

문제

1. Remove Adjacent Duplicates

2. 

이전글 - 파이썬 컬렉션 자료구조

다음글 - 파이썬 순열 조합