스택, 큐, 덱 (stack, queue, daque)

 

스택(Stack)

• 선입후출의 특징을 가진 알고리즘이다. (흔히 박스쌓기에 비유)
• 컴퓨터 내부에서 재귀함수의 구현은 스택으로 이루어진다.

Python에서 스택을 사용할때는 특별한 구현 필요없이, <list>.append() 함수와 <list>.pop() 만을 사용하면 그대로 스택을 구현할 수 있다.

 

Python - stack

stack = []
stack.append(3)
stack.append(4)
stack.pop()

 

 

 

큐(Queue)

• 선입선출의 특징을 가졌다. (흔히 줄서기에 비유)
• 삽입되는 곳을 front 제거되는곳을 back 이라고 한다.
• BFS(너비 우선 탐색) 에 유용하게 사용된다.
• deque을 append 함수만 추가하고, popleft()로만 삭제하면 큐이다.

 

 

덱(Deque)

• 스택과 큐의 장점을 모두 갖고있다.
• 큐(Queue)는 front로만 삽입하고 back에서만 삭제한다. 하지만 덱은 front로 삽입/삭제가 가능하고, back에서도 삽입/삭제가 가능하다.

Python에서 큐를 사용할때는 collections의 deque를 사용하면된다. Deque을 한쪽 방향에서만 삭제하고, 반대쪽에서만 삽입한다면 큐와 같다.

 

Python - Queue / deque

from collections import deque

queue = deque()
queue.append(4) # 삽입
queue.append(3)
queue.popleft() # append 하면 오른쪽에서 삽입하므로, pop은 왼쪽에서 해준다.
queue.reverse() # 순서를 뒤집는 메서드도 있다.