[코딩테스트/Python] 꼭 필요한 자료구조 기초: 스택과 큐

자료 구조에 대해 왜 알아야 할까?

프로그래밍 문제 중 "탐색" 유형은 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 코딩 테스트에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로는 DFS, BFS가 있는데, 해당 알고리즘을 잘 이해해야만 탐색 유형 문제들을 잘 풀어갈 수 있다. 탐색 알고리즘을 이해하기 위한 필수적인 자료구조로는 스택, 큐, 재귀 함수 등이 있다. 해당 개념을 완벽히 이해하고 넘어가보자! (재귀 함수는 다음 포스팅에서 다루고자 한다. )

 

자료 구조, 스택과 큐

자료 구조는 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 자료 구조 중 스택과 큐를 쓰기 위해서는 이를 이루는 두가지 주요 함수에 대해 알아야 한다. 

• 삽입 (push): 데이터 삽입
• 삭제 (pop): 데이터 삭제 

파이썬에서 삽입은 append, 삭제는 pop 함수를 통해 수행할 수 있다. 데이터를 추가하고, 삭제함으로써 프로그램 내의 자료를 관리하는 것이다. 그런데, 데이터가 없을 때 삭제를 수행한다던가 데이터가 maximum으로 있는 상태에서 삽입을 한다면 문제가 발생할 수 있다. 이를 언더플로, 오버플로라고 한다. 

• underflow: 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생
• overflow: 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생

스택 (Stack) 

스택은 박스 쌓기에 비유할 수 있다. 박스를 쌓을 때는 선입후출 (First In Last Out) 구조 또는 후입선출 (Last In First Out) 구조로 수행해야한다. 생각해보면 당연하다. 실제 물건을 쌓을 때도 아래에 있는 박스를 치우기 위해서는 위에 있는 것들을 먼저 치우고 치워야 하는 것처럼, 프로그램 내에서도 자료들을 순서대로 처리해야 한다. 

파이썬 구현 시, 별다른 라이브러리 사용 없이 append()와 pop()을 통해 처리할 수 있다. stack이라는 빈 리스트를 만들고 리스트 내에 숫자를 채우고, 삭제할 수 있다. 

stack=[]
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,7을 차례대로 쌓은 후 가장 마지막에 있는 7을 삭제한다. 5,2,3이 있는 상태에서 1,4를 추가하여 [5,2,3,1,4]의 리스트에서 마지막 4를 삭제하면 [5,2,3,1]이 출력된다. stack[::-1]을 출력하면 최상단 원소부터 출력된다. 

큐 (Queue)

스택을 상자에 비유했다면 큐는 대기줄에 비유할 수 있다. 큐에는 선입선출 (First In First Out) 개념으로 작동된다. 나중에 온 사람일 수록 나중에 들어가기 때문에 흔히 "공정한" 자료구조라고 비유된다. 

큐를 파이썬에서 구현하기 위해서는 list(queue)를 사용할 수 있다. 하지만 큐는 파이썬 collections 모듈에서 제공하는 deque 자료 구조로 구현하는 것이 더 효율적이다. deque는 스택과 큐의 장점을 모두 채택한 것으로, 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다. 

##queue
from collections import deque
queue = deque()
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)

빈 큐를 하나 구현한 후  5,2,3,7을 차례로 추가한다. 그 후 한 원소를 제거해줘야 하는데 큐에서는 선입선출 개념으로 작동되므로 가장 먼저 들어온 5가 삭제된다. 그 후 1,4를 추가하여 2,3,7,1,4가 된 현 상태에서 가장 먼저 들어온 2를 제거하면 최종적으로 [3,7,1,4]가 출력된다. 

 

스택과 큐를 잘 활용하면 여러 문제들에서 코드를 효율적으로 구현할 수 있다. 

 

[reference]

도서 "이것이 코딩 테스트다" (https://github.com/ndb796/python-for-coding-test)