[algo] 스택과 큐란?

스택

나중에 넣은 데이터가 먼저 반환되도록 설계한 메모리 구조
Last In First Out (LIFO)라고도 함

파이썬은 따로 stack 구조를 제공하지 않기 때문에, 기본 클래스 list를 사용하여 stack을 표현할 수 있다.

• 데이터의 입력인 push로는 .append()
• 데이터의 출력인 pop으로는 .pop() : 데이터 구조에서 맨 마지막에 있는 값을 뽑아서 준다는 것
  반환값을 리턴 시켜주는 함수
  pop으로 뽑아낸 데이터는 원래 리스트 내에서 없어짐
• top으로는 stack[-1] : 마지막 원소를 제거하지 않고 가져오기만 할 때

큐

먼저 줄 선 데이터가 먼저 반환되도록 한다는 의미이다.
선입선출, First In First Out (FIFO) 라고 한다.

• 데이터의 입력인 enqueue로는 .append()
• 데이터의 출력인 dequeue로는 .pop(0) : 0을 넣어주면 0번째, 즉 가장 앞의 원소를 뽑아낸다는 뜻이니까 선입선출을 하게 되는 것

덱

스택과 큐의 기능을 모두 가진 객체로 출입구를 양쪽에 가지고 있어 스택처럼 써도 되고, 큐처럼 써도 된다.

from collections import deque
dq = deque('love')
dq
# deque(['l','o','v','e'])

1. 스택 구현 : append(), pop()

2. 큐 구현 : append(), popleft()

• enqueue로는 .append()
• dequeue로는 .popleft() : 맨 앞의 원소를 빼줌