꼭 필요한 자료구조 기초 (Stack,Queue, Dequeue)

탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다.

대표적인 탐색 알고리즘으로 DFS와 BFS가 있다.

이를 제대로 이해하기 위해서는 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다.

 

자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조

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

• 삽입 (Push) : 데이터를 삽입한다.
• 삭제 (Pop) : 데이터를 삭제한다.

스택과 큐를 사용할 때에는 오버플로와 언더플로에 대해서 항상 생각해야한다.

 

오버플로(Overflow) : 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생

언더플로(Underflow) : 특정한 자료구조에 데이터가 전혀 들어 있지 않을 상태에서 삭제 연산을 수행할 때 발생

스택(Stack)

스택은 박스 쌓기에 비유할 수 있다.

박스를 아래에서부터 순서대로 쌓아 올린 후 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내려야한다.

즉, 선입후출(FILO) 또는 후입선출(LIFO) 구조이다.

 

스택 예제

stack = []

#삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(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]

큐(Queue)

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

놀이공원에 입장하기 위해 줄을 선다고 할 때, 먼저 온 사람이 먼저 들어가게 되는 것과 같다.

나중에 온 자료일수록 나중에 들어가기 때문에 흔히 '공정한'자료구조라고 비유된다.

이러한 구조를 선입선출(FIFO) 구조라고 한다.

디큐(Deque)

디큐는 큐와 스택이 혼합된 개념이다.

앞, 뒤 양방향에서 push와 pop연산이 가능하다.

가장 먼저 넣은 자료부터 꺼낼 수도 있고 가장 마지막에 넣은 자료부터 꺼낼 수도 있는 방식이다.

* 큐를 사용하게 될 경우 디큐를 사용하는 것이 더 빠르고 효율적이다. 

 

큐 예제

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) # 나중에 들어온 원소부터 출력

출력

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

위의 코드의 경우 큐의 예제를 들었기 때문에 popleft를 사용하였다.

위에 상술한 대로 deque의 경우 자료를 앞에서부터 뽑을지 뒤에서부터 뽑을지 선택할 수가 있다.

먼저 들어온 자료를 먼저 뽑겠다면 queue.popleft()

나중에 들어온 자료를 먼저 뽑겠다면 queue.pop()을 사용하면 된다.