모두의 알고리즘 with 파이썬: 02 회문 찾기 알고리즘

icon_wait 잠깐만요

리스트를 이용한 큐와 스택 구현

리스트로 큐와 스택의 동작을 구현하면 다른 모듈을 사용하지 않고도 간단히 큐와 스택을 사용할 수 있다는 장점이 있습니다. 하지만 엄밀하게 말하면 이 방법은 효율적이지 않습니다(큐가 비효율적입니다).

효율성이 중요한 프로그램이라면 파이썬의 collections 모듈에 있는 deque(double-ended queue)를 이용하여 다음과 같은 방식으로 큐를 만들어 사용할 수 있습니다.

>>> from collections import deque

>>> qu = deque()

>>> qu.append(1) # 1을 큐에 추가(enqueue)

>>> qu.append(2) # 2를 큐에 추가(enqueue)

>>> qu.popleft() # 큐에서 1을 꺼냄(dequeue)

>>> qu

deque([2]) # 1을 꺼냈으므로 2가 남아 있습니다.

참고로 큐와 스택을 리스트로 만들면 왜 큐가 더 비효율적일까요?

앞에서 살펴본 택시 정류장에서 줄 서기를 생각하면 감을 잡을 수 있습니다. 큐에서 맨 앞사람이 빠져나가면 줄의 맨 앞이 비게 됩니다. 따라서 줄에 남은 모든 사람이 ‘귀찮게도’ 한 발씩 앞으로 움직여야 합니다.

하지만 줄의 맨 뒷사람이 택시를 기다리다 포기하고 줄을 떠난다면 어떨까요? 줄에 남은 사람들은 아무 상관이 없겠지요?

① 리스트로 만든 큐에서 자료 꺼내기(dequeue)

qu.pop(0) → 리스트의 0번 위치에서 자료를 빼내면 0번 위치가 비므로 남은 자료를 전부 한 칸씩 당겨 주는 처리가 필요

② 리스트로 만든 스택에서 자료 꺼내기(pop)

st.pop() → 리스트의 맨 뒤에서 자료를 빼내면 남은 자료의 위치는 변화가 없음

파이썬에서 큐와 스택과 같은 자료 구조를 활용하는 방법을 더 자세히 알고 싶다면 파이썬 공식 문서를 참고하면 도움이 될 것입니다.

신간 소식 구독하기

뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.