스택과 큐는 프로그래밍이라는 개념이 탄생할 때부터 사용된 가장 고전적인 자료구조 중 하나로, 그중에서도 스택은 거의 모든 애플리케이션을 만들 때 사용되는 자료구조다.
스택은 LIFO(Last In First Out- 후입 선출), 큐는 FIFO(First In First Out - 선입 선출)로 처리된다.
파이썬은 스택 자료형을 별도로 제공하지는 않지만, 리스트가 사실상 스택의 모든 연산을 지원한다. 큐 또한 마찬가지다. 리스트는 큐의 모든 연산을 지원한다. 다만 리스트는 동적 배열로 구현되어 있어 큐의 연산을 수행하기에는 효율적이지 않기 때문에, 큐를 위해서는 데크(Deque)라는 별도의 자료형을 사용해야 좋은 성능을 낼 수 있다. 그러나 굳이 성능을 구려하지 않는다면 리스트는 스택과 큐의 모든 연산을 지원하기 때문에 사실상 리스트를 잘 사용하기만 해도 충분하다.
스택
스택은 다음과 같은 2가지 주요 연산을 지원하는 요소의 컬렉션으로 사용되는 추상 자료형이다.
- push(): 요소를 컬렉션에 추가한다.
- pop(): 아직 제거되지 않은 가장 최근에 삽입된 요소를 제거한다.
문제1
유효한 괄호 - 괄호로 된 입력값이 올바른지 판별하라.
- 입력
-()[]{}
-{{]- 출력
-true
-false
전형적인 스택 문제로, 기본기를 점검할 수 있는 좋은 문제이다. (,{,[는 스택이 푸시하고 ),},]를 만날 때 스택에서 팝한 결과가 매핑 테이블 결과와 매칭되는지 확인하면 된다. 팝 했을 때 결과가 일치하지 않으면 False를 리턴하도록 구현하면 된다.
stack = []
table = {
')':'(',
'}':'{',
']':'['
}
...
if char not in table:
stack.append(char)
elif not stack or table[char] != stack.pop():
return False여기서 stack은 간편하게 파이썬의 동적 배열 구현인 리스트를 사용했다. 파이썬 리스트는 스택 연산인 푸시와 팝이 O(1)에 동작하기 때문에 성능에도 큰 문제가 없다. 이제 실제로 실행시키기 위해서는 예외 처리가 필요하다. 아래와 같이 예외 처리가 가능하다.
elif not stack or table[char] != stack.pop():
return False
return len(stack) == 0이 코드에서는 팝 결과가 일치하지 않는지 확인하는 것 외에도 스택이 비어 있는지 여부를 함께 확인하여 True, False를 결정하게 된다. 이처럼 예외 처리가 반드시 포함되어야 한다. 전체 코드는 다음과 같다.
def isValid(self, s: str) -> bool:
stack = []
table = {
')':'(',
'}':'{',
']':'['
}
for char in s:
if char not in table:
stack.append(char)
elif not stack or table[char] != stack.pop():
return False
return len(stack) == 0문제2
일일 온도 - 매일의 화씨 온도 리스트 T를 입력받아서, 더 따듯한 날씨를 위해서는 며칠을 더 기다려야하는지를 출력하라.
- 입력
-[73,74,75,71,69,72,76,73]- 출력
-[1, 1, 4, 2, 1, 1, 0, 0]
현재의 인덱스를 계속 스택에 쌓아두다가, 이전보다 상승하는 지점에서 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교해서, 더 높다면 다음과 같이 스택의 값을 pop()으로 꺼내고 현재 인덱스와 스택에 쌓아둔 인덱스의 차이를 정답으로 처리한다.
while stack and cur > temperatures[stack[-1]]:
last = stack.pop()
answer[last] = i - last
stack.append(i)아울러 answer의 디폴트는 0이다. 만약 더 높은 온도가 나오지 않아 스택이 비워지지 않았다면 해단 인덱스는 해당 없음, 즉 문제에서 요구하는 바와 같이 0으로 남게 된다. 이 풀이의 전체 코드는 다음과 같다.
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
answer = [0]*len(temperatures)
stack = []
for i, cur in enumerate(temperatures):
#현재 온도가 스택 값보다 높다면 정답처리
while stack and cur > temperatures[stack[-1]]:
last = stack.pop()
answer[last] = i - last
stack.append(i)
return answer큐
큐는 시퀀스의 한쪽 끝에 엔티티를 추가하고, 다른 반대쪽 끝에는 제거할 수 있는 엔티티 컬렉션이다.
FIFO(선입서출)로 처리되는, 줄을 서는 것에 비유할 수 있는 큐는 상대적으로 스택에 비해서는 쓰임새가 적다. 그러나 스택에 비해서 그렇다는 얘기일 뿐, 이후에 살펴보게 될 데크나 우선순위 큐 같은 변형들은 여러 분야에서 매우 유용하게 쓰인다. 사실상 파이썬의 리스트는 큐의 모든 연산을 지원하기 때문에 그대로 사용해도 무방하지만 좀 더 나은 성능을 위해서는 이후에 살펴볼 양방향 삽입, 삭제가 모두 O(1)에 가능한 데크를 사용하는 편이 좋다.
문제3
** 큐를 이용한 스택 구현 - 큐를 이용해 연산을 지원하는 스택을 구현하라.
push(x) : 요소 x를 스택에 삽입한다.
pop() : 스택의 첫 번째 요소를 삭제한다.
top() : 스택의 첫 번째 요소를 가져온다.
empty() : 스택이 비어 있는지 여부를 리턴한다.
파이썬의 리스트나 데크는 스택과 큐의 모든 기능을 제공하기 때문에 이 문제는 원래 큐 ADT에는 없지만 파이썬의 자료형에서 지원하는 기능을 사용하면 매우 쉽게 풀 수도 있다. 그러나 여기서는 문제의 의도에 맞게 큐의 FIFO에 해당하는 연산만 사용해서 구현해본다. 먼저 큐의 선언은 데크로 한다.
self.q = collections.deque()큐를 데크로 선언했지만 문제의 의도에 맞게 여기서는 큐의 연산만을 사용해 구현할 것이다. push()할 때만 다소 복잡한 편인데, 다음 요소를 삽입한 후 방금 삽입한 요소를 맨 앞에 두는 상태로 전체를 재정렬한다.
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())이렇게 하면 큐에서 맨 앞 요소를 끄집어낼 때 스택처럼 가장 먼저 삽입한 요소가 나오게 될 것이다. 물론 요소 삽입 시 시간 복잡도가 O(n)이 되어 다소 비효율적이긴 하지만, 이렇게 하면 스택을 큐로 어렵지 않게 구현할 수 있다. 전체 코드는 다음과 같다.
import collections
class Mystack:
def __init__(self):
self.q = collections.deque()
def push(self, x):
self.q.append(x)
#요소 삽입 후 맨 앞에 두는 상태로 재정렬
for _ in range(len(self.q)-1):
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]
def empty(self):
return len(self.q) == 0