[자료구조] 파이썬으로 구현하기 - stack, queue, deque

Stack

LIFO(후입선출) 자료구조! 재귀함수를 구현하는 대신으로 쓰이기도한다!
파이썬에는 따로 라이브러리가 있진 않고 리스트를 스택처럼 사용하면 된다.

init

st = []
st = list()

push

st.append(1) # li = [1]
st.append(2) # li = [1, 2]

pop

# st = [1, 2]
top = st.pop()
print(top) # 2

peek

st = [1, 2, 3, 4]
top = st[-1]
print(top) # 4

스택을 이용해서 문제 푸는 예시

주식 가격 - programmers

문제보기

이 문제는 인덱스를 집어넣는 스택을 써서 풀면 정말 쉽게 풀 수 있다!

인덱스를 0부터 스택에 넣어주고, top에 있는 인덱스를 가져와서 price[stack.top()] > price[currentIdx] 연산이 true 이면 popped = stack.pop()을 하고, answer[popped] = currentIdx - popped 로 저장하면 된다!

근데 다른 사람한테 설명은 못하겠다..

---

파이썬에서는 큐를 설명하기 전에 덱을 먼저 설명해야한다.
우리가 문제 풀 때는 큐를 따로 쓰지 않고 덱을 큐처럼 사용하기 때문이다.

Deque: Double Ended Queue

파이썬에서는 collections라는 모듈에서 deque라는 클래스를 제공한다. deque는 양방향 연결리스트로 구현이 돼있어 리스트보다 출입 연산이 더 효율적이다.

As deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity.

그냥 리스트를 써서 양쪽에서 push, pop하는 것보다 deque를 사용하는 게 바람직하겠다.

다음은 deque의 메서드 목록이다.

암튼 중요한 건 리스트와 달리 popleft(), appendleft()가 있다는 것이다~_~

---

Queue (deque 이용)

FIFO(선입선출) 구조형, BFS에서도 자주 쓰이고 파이썬에서는 덱을 사용한다.

리스트를 사용하는 것이 아니라서, 큐를 사용하고 싶을 때는 deque() 로 덱을 생성을 해야한다.

init

from _collection import deque
q = deque()

push

q.append(1)
q.append(2)
print(q) # [1, 2]

pop

큐는 먼저 들어간 것 (왼쪽에 있는 것)이 먼저 나와야하기 때문에, pop()이 아니라 popleft()를 사용해야한다!

popped = q.popleft()
print(popped) # 1

peek

큐의 head를 확인하려면 그냥 인덱스로 0번째 값에 접근하면 된다.

q = [2, 3, 4, 5]
head = q[0]
print(head) # 2