stack, queue, deque in python

stack, queue, deque에 대해 알아보자.

 

---

stack은 선입후출! - 먼저 들어온 것이 나중에 빠져나간다.

컵 모양이라 생각하면 똑같다. 1,2,3,4가 stack이라는 리스트에 들어갔다면 꺼낼 때는 4,3,2,1순으로 나와야한다.

python에서 특정한 라이브러리가 없는 것으로 알고있다.

stack은 평범한 리스트로 구현이 가능하다.

stack=[]

stack.append(1)
stack.append(2)
# stack = [1,2]

stack.pop()
# 결과 : 2
stack.pop()
# 결과 : 1

stack.append(3)
stack.append(4)
# stack = [3,4]
stack.insert(0,5)
# stack = [5,3,4]

stack.pop(0)
# 결과 : 5
stack.pop(0)
# 결과 : 3
# stack = [4]

 

---

queue는 선입선출! - 먼저 들어온 것이 먼저 빠져나가야한다.

라우터와 같다. 먼저 들어온 것은 먼저 처리해줘야한다.

예를 들어 1,2,3,4가 들어왔으면 나가는 것은 1,2,3,4가 나가줘야 한다.

이 것도 list로 구현이 가능하다. 아까의 stack.pop(0) 된다. 하지만 list의 pop(0)을 써주면 앞의 원소를 꺼내고 나머지가 하나씩 앞으로 와야하기 때문에 정렬에 따른 시간복잡도가 증가한다.

그렇기에 파이썬에서는 queue라는 라이브러리를 제공해준다.

from queue import Queue

que=Queue()

que.put(1)
que.put(2)
que.put(3)
# que = [1,2,3]

que.get()
# 결과 : 1
que.get()
# 결과 : 2

que[0]
que[-1]
# 에러가 발생함!

queue라이브러리에선 append와 pop대신 put과 get을 쓴다.

그리고 이 라이브러리는 방향성이 없기 때문에 que[0]을 하면 에러가 발생한다.

이럴 때 쓸 수 있는 것이 deque 라이브러리이다.

 

 

 

---

이 deque라이브러리는 queue의 라이브러리를 보완해준 친구다.

deque는 방향성을 가지고 있기에 위의 에러가 나는 것을 처리해줄 수 있고, 앞이든 뒤든 원하는 곳에서 가져올 수 있다.

이 deque에는 popleft()나 appendleft()라는 함수를 가지고 있다.

from collections import deque

dq=deque([4,5,6])

dq.append(1)
dq.append(2)
# dq = [4,5,6,1,2]

dq.popleft()
# 결과 : 4
dq.popleft()
# 결과 : 5


dq2=deque([4,5,6])
dq2.appendleft(1)
dq2.appendleft(2)
# dq2 = [1,2,4,5,6]

dq2.pop()
# 결과 : 6
dq2.pop()
# 결과 : 5

기존에 append()를 썼을 경우 dq[-1]에 값이 들어온다. 그러면 popleft()로 처음 들어왔던 값=dq[0]을 꺼낼 수 있다.

이 때의 방향은 오른쪽에서 왼쪽이다.   (나가는 값)<----(들어오는 값)

 

반대로 appendleft()를 쓸 경우 dq2[0]에 들어오게 된다. 방향성은 왼쪽에서 오른쪽으로 바꼈으므로

(들어오는 값)------>(나가는 값)

꺼낼 때는 pop()으로 꺼내주면 된다.