코딩테스트를 위한 스택과 큐 기본 이론

1. 탐색(search)

 

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

 

코딩테스트를 통과하기 위해 그래프, 트리 등의 자료구조 안에서 탐색을 할줄 알아야한다

 

이를 위한 대표적인 탐색 알고리즘이 바로 DFS/BFS

 

 

2. 자료구조

 

데이터를 표현하고 관리하고 처리하기 위한 구조

 

스택(stack)과 큐(queue)는 자료구조의 기초 개념

 

 

3. 스택과 큐에서 고려해야할 부분

 

스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성

 

삽입(push): 데이터를 삽입한다

 

삭제(pop): 데이터를 삭제한다

 

실제 스택과 큐를 사용할 때는 삽입과 삭제 외에도 오버플로우와 언더플로우도 고민해야함

 

오버플로우(overflow): 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때, 즉 저장 공간을 벗어나 데이터가 넘쳐흐를때 발생

 

언더플로우(underflow): 특정한 자료구조에 전혀 데이터가 들어있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태이므로 언더플로우

 

deque 사용하면서 이런 경우가 많았지 deque에 아무것도 안들어있는데 pop연산을 수행해서 에러나는 경우

 

 

4. 스택(stack) 자세히

 

스택(stack)은 박스 쌓기에 비유할 수 있다

 

흔히 박스는 아래에서부터 위로 차곡차곡 쌓는다

 

그리고 아래에 있는 박스를 치우려면? 위에 있는 박스를 먼저 치워야 아래에 있는 박스를 치울 수가 있다

 

이러한 구조를 First In Last Out 혹은 Last In First Out 이라고 부른다

 

'먼저 들어간 것은 나중에 나온다' 혹은 '나중에 들어간 것은 먼저 나온다'

 

스택 구조대로 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()를 각 스텝별로 순서대로 표현

 

스택 구조 연산 순서대로 표현

 

파이썬 코드로 구현

 

stack = []

#삽입(5-2-3-4) - 삭제() - 삽입(1-4) - 삭제()

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)

stack.pop()

stack.append(1)
stack.append(4)

stack.pop()

print(stack) #최하단부터 순서대로 출력
print(stack[::-1]) #최상단부터 반대로 출력

[5, 2, 3, 1]
[1, 3, 2, 5]

 

파이썬에서 스택은 기본 리스트에서 append()와 pop()을 이용해 동일하게 구현할 수 있다

 

append()는 리스트의 가장 뒤쪽에 데이터를 삽입(push)하고 pop()은 리스트의 가장 뒤쪽에 데이터를 삭제(pop)한다

 

 

5. 큐(queue) 자세히

 

큐는 대기 줄에 비유할 수 있다

 

놀이공원에 입장하기 위해 줄에 설 때 먼저 온 사람이 먼저 들어갔다가 즐기고 먼저 나오고

 

나중에 온 사람은 나중에 들어갔다가 즐기고 나중에 나온다.

 

그래서 흔히 공정한 자료구조라고 비유하고 이런 구조를 First In First Out이라고 부른다

 

'먼저 들어간 것이 먼저 나옴'

 

큐는 입구와 출구가 모두 뚫려있는 터널과 같은 형태이다. 

 

삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()를 차례대로 수행

 

큐의 연산 수행을 차례대로 표시

 

파이썬 코드로 구현

 

#큐를 구현하는 deque 라이브러리 사용
from collections import deque

queue = deque()

#삽입(5-2-3-7) - 삭제() - 삽입(1-4) - 삭제()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)

queue.popleft() #가장 먼저 들어간, 가장 왼쪽의 원소를 제거

queue.append(1)
queue.append(4)

queue.popleft()

print(queue)

queue.reverse() # 큐를 역순으로 배열함

print(queue)

print(list(queue)) #리스트로 변경

deque([3, 7, 1, 4])
deque([4, 1, 7, 3])
[4, 1, 7, 3]

 

파이썬으로 큐를 구현할 때는 collections의 deque를 활용

 

deque는 스택과 큐의 장점을 모두 채택함

 

데이터를 삽입하고 삭제하는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 간단

 

deque 객체를 리스트 자료형으로 변경하고자 한다면 list() 함수를 활용