스택과 큐

1. 스택

: 선입후출 리스트

스택은 들어가는 방향과 나오는 방향이 같다.

그래서 먼저 들어간 것이 가장 마지막에 나가고, 마지막에 들어간 것이 가장 먼저 나가게 된다.

stack = []

stack.append(n) #마지막 인덱스에 원소 삽입
stack.pop(n)  #마지막 원소를 제거

 

 

이렇게 일반적인 리스트처럼 구현해서 사용하면 된다.

 

 

 

 

 

2. 큐

: 선입선출 리스트

원래 큐는 한 방향으로 들어가고, 다른 한쪽으로 나오는 배열인데

deque는 양방향으로 들어가고 나올 수 있다.

 

 

 

collection 라이브러리의 deque 기능을 import하면,

(from collections import deque)

popleft()       #첫번째 원소를 제거
pop()           #마지막 원소를 제거
appendleft(x)   #첫번째 인덱스에 원소 삽입
append(x)       #마지막 인덱스에 원소 삽입

 

이렇게 선입선출, 선입후출이 모두 가능해진다.

 

 

deque는 왜 써야 할까?

일반적인 append()와 pop()메서드로 입력, 출력할 때는 
뒤에서 입력, 뒤에서 출력하는 stack은 잘 구현이 되지만, 

앞에서 입력하거나 가장 앞쪽의 원소를 제거하거나 첫번째 인덱스에 원소를 삽입려고 하면 시간 복잡도가 O(1)이 아니라 O(N)이 된다. 

 

deque로 구현하면 popleft()를 통해서 가장 앞쪽의 원소를 O(1)의 시간복잡도로 제거할 수 있으므로

queue 자료구조에서 꼭 이용하는 것이 좋다!

 

 

 

 

 

 

#

스택을 사용해야 할 때 스택 라이브러리 대신 재귀 함수를 구현하는 경우가 많다. 재귀함수는 단순 반복문으로 구현할 수도 있지만 상황에 맞게 선택해서 구현해야 한다. dfs 알고리즘에서도 흔히 재귀함수를 호출하는 방법을 통해서 stack을 구현한다.

 

#

bfs에서는 deque를 이용해서 deque에 가장 먼저 삽입된 원소부터 주변을 탐색하는 반복문을 돌리게 된다.

 

일반적으로는 bfs가 dfs보다 조금 더 빠르다.