[자료구조/알고리즘] 파이썬 리스트와 덱을 활용한 스택과 큐 구현

  이 글은 유데미 '컴공선배 알고리즘캠프' 강좌를 듣고 공부한 내용을 정리한 내용입니다. 

 

 알고리즘 문제 중 DFS 문제에서 스택과 큐가 활용된다. 

 

스택

 파이썬에는 C++처럼 스택이라는 자료형이 따로없어 리스트로 스택을 구현했다. 스택이라는 자료형은 먼저 들어온 자료가 나중에 나가는 선입후출 구조이다. 따라서 아래의 코드를 실행한 결과 마지막에 추가된 789가 먼저 출력되는 것을 확인해볼 수 있다. 

s = []
s.append(123)
s.append(456)
s.append(789)

print("size:", len(s))

while len(s) > 0:
    print(s[-1])
    s.pop(-1)

 

  조금 특이한 것이 -1의 인덱스를 준 것이다. 파이썬에서 음수 인덱스를 쓰면 가장 맨 뒤로 가서 맨 뒤에서부터 역순으로 센다. 따라서 여기서 -1번째 인덱스의 값은 789이며 먼저 pop했기 때문에 789 > 456 > 123 순서로 출력되는 것이다. pop()을 하면 요소를 반환한 후 자료형에서 없앤다. 

 

 스택의 실사용 예는 인터넷에서 우리가 웹서핑을 하다가 뒤로가기를 해서 방금 방문했던 페이지로 갈 때이다. 방문 기록을 마지막에 방문한 순서 대로 나오기 때문에 스택을 이용한 구현임을 알 수 있다. 

 

 

큐 

 스택과 반대로 첫번째로 들어간 요소가 첫번째로 나온다. (FIFO) 일상생활의 예로 맛집을 기다리는 줄을 생각할 수 있다. 먼저 온 사람이 먼저 줄에서 빠져나오는 구조이다. 

 

from collections import deque 

q = deque()
q.append(123)
q.append(456)
q.append(789)

print("size:", len(q))
while len(q) >0:
    print(q.popleft())      # 값을 왼쪽에서 뺀다

 원래 Queue모듈이 따로 있는데, 얘는 멀티스레드 환경에서 멀티스레드를 고려한 기능을 짰을 때 스레드 safe하도록 구현되어있어 속도가 좀 느리다. 알고리즘 풀 땐 이것이 필요하지 않기 때문에 deque을 쓴다. 덱은 큐의 상위호환 같은 자료구조인데, 큐는 항상 데이터를 뒤로만 넣을 수 있었는데 덱은 맨 앞에서도, 뒤에서도 양쪽으로 넣고 빼고가 가능한 자료구조다. (double-ended Queue의 축약표현)

 

 백준에서 알고리즘 문제를 풀 때 큐를 쓸일이 있다면 deque을 쓰자! 

 

 

 

시간복잡도 

 큐와 스택 모두 삽입/삭제시 N개의 데이터 각각에 대해 따로 해주는 것이 없기 때문에 시간복잡도 O(1)이다.