스택과 데크(deque)

안녕하세요 Dibrary입니다.

이번에 소개할 자료구조는 스택 입니다. 연결 리스트보다 어찌보면 간단한? 자료구조입니다.
(이해하기는 굉장히 쉬운데 실제 쓰임새는 연습하지 않고는 떠오르지 않는 괴랄한... )

 

스택의 특징은 딱 하나 입니다 LIFO (LAST에 IN 한 데이터가 FIRST로 OUT 한다)

이거 한 개만 아셔도 스택 개념의 절반은 먹고 들어간다~ 이거죠.

 

 

---

스택은 반드시 LIFO만 유지되면 됩니다.
그럼 여기서 LAST에 IN한 다는 의미와 FIRST로 OUT한다는 의미가 무엇인가 코드로 살펴보겠습니다. (물론 파이썬으로요)

임의로 stack이라는 이름의 list를 만들어 보았습니다.

1, 2, 3을 순서대로 넣고 확인해 보니 순서대로 들어갔네요.

pop을 하니까 맨 마지막에 넣은 3이 제일 먼저 나왔고, 그 다음에 2, 1 순서대로 나옵니다.

 

이게 바로 LIFO 입니다.

 

---

근데, 파이썬에서는 list로 stack을 구현하면 효율상 썩 좋지 않습니다. (왜냐하면, 파이썬의 리스트는 최대 길이를 넘어선 추가가 일어나면 복사를 해서 옮기는 과정이 추가됩니다.)

 

그럼 무엇으로 하느냐~? 바로 deque 자료구조를 쓰는 거죠.

네 list랑 동작 방법이 똑같습니다. 실제 차이가 있는지 확인 해 볼까요?

분명히 차이는 있네요. (물론 단순히 넣고 빼는 과정일 뿐이라서 일반화 하기 어려워 보일 수도 있습니다만..)

 

---

이왕 deque를 쓴 김에 데크 자료구조도 짚어보겠습니다.
deque 자료구조는 원래 데크라는 자료구조를 구현한 것으로 앞 뒤 전부를 꺼낼 수 있습니다.

append를 쓰면 뒤에서부터 값이 들어가고, appendleft를 쓰면 앞에서부터 차례대로 값이 넣어진 것을 볼 수 있습니다.

그럼 값도 앞 뒤에서 꺼낼 수 있는지 보겠습니다.

pop을 쓰면 뒤에서부터 꺼내고, popleft를 쓰면 앞에서부터 꺼내는 것을 볼 수 있습니다.

 

굉장히 간단한데, 스택을 활용하는 예를 풀어보고자 하시면, 

6198번: 옥상 정원 꾸미기

이 문제를 풀어보시길 권합니다.
물론, 아예 알고리즘을 안 해본 초보자시라면 어려운데, 어느정도 코드에 익숙하다면 한번 접해보시는 걸 추천합니다.