09. 스택/큐 알고리즘 개념

 

 

01. 스택(Stack), 큐(Queue) 개념

 

 

1-1.스택(stack)이란

자료의 입력과 출력을 한 방향으로 제한한 자료구조를 의미한다.

즉, LIFO(Last In First Out)구조다.

 

스택의 예시
쌓여있는 접시에서는 맨 위에것부터 쓸 것이다. 새걸넣어도 맨위이다. 접시가 쌓인 모습을 상상하자!

 

 

1-2-1. 스택 풀이 방법

스택 자료형은 없다. deque를 이용해 스택을 쓴다는 점을 알고 있으면 좋다.

 

🔥 덱(deque)이란?

양방향 큐이다. 즉, 맨 앞과 뒤에 데이터를 삽입하고 삭제할 수 있게 해주는 자료형이다.
양 끝 엘리먼트에 대한 append, pop이 빠르다는 장점이 있어 많이들 사용한다.
삽입 제거 시, 일반적인 리스트는 연산에 O(n)인 데에 반해, 데크는 O(1)로 성능이 매우 빠르다.



🔥 List 가 아닌 덱을 사용하는 결정적 이유?

리스트로도 되기는 하는데, 리스트는 pop을 하면 모든 값들이 앞으로 당겨지는 현상이 발생한다.
데크는 앞에서도 뺐다넣다 뒤에서도 뺐다넣다 할수있고 & 중간자료는 움직이지 않고 빠졌으면 그냥 0이 그다음자료를 의미하는 자료가 된다. 즉, 당겨지는 연산을 안한다. 이는 덱을 사용하는 결정적 이유다.

🔥 deque 쓰는 법?
from collections import deque 
stack = []
dequestack = deque(stack)
위와 같은 방법을 이용해 deque를 쓴다.

# deque을 이용한 맨 뒤 삽입.삭제를 한다.

# 추가는 append를 한다.

# 접근은 [-1]을 한다.

# 삭제는 pop()을 한다.

 

 

 

 

 

1-3. 큐(queue)란

자료의 입력과 출력을 한 방향으로 제한한 자료구조를 의미한다.

즉, FIFO(First In First Out)구조다.

큐의 예시
편의점 진열된 우유를 상상하자. 제일 먼저 넣은 우유는 제일 처음 선택된다.

 

1-3-1. 큐 풀이 방법

# deque를 사용한다.

# 뒤에서 넣을땐 append & 뒤에서 꺼낼땐 pop을 한다.

# 앞에서 넣을땐 appendleft & 앞에서 꺼낼땐 popleft을 한다.