파이썬(Python)으로 스택과 큐 사용하는 법 / 예제 포함

스택(Stack)

스택은 말 그대로 데이터를 쌓아 올리는 자료구조입니다.

스택은 LIFO(Last-In-First-Out) 순서를 따릅니다. 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이라는 것입니다.

배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 없습니다. 하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능합니다.

 

스택이 유용한 경우는 재귀 알고리즘을 사용할 때입니다. 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어주고, 재귀 함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 합니다. 스택은 이런 일련의 행위를 직관적으로 가능하게 해줍니다.

 

스택은 또한 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해줍니다.

스택 예제

[BOJ 10828] 스택 - 파이썬 풀이

 

큐(Queue)

큐는 FIFO(First-In-First-Out) 순서를 따릅니다. 큐에 저장되는 항목들은 큐에 추가되는 순서대로 제거됩니다.

큐는 너비 우선 탐색(BFS: Breadth-First Search)을 하거나 캐시를 구현하는 경우에 종종 사용됩니다.

예를 들어 BFS를 하는 경우, 처리해야 할 노드의 리스트를 저장하는 용도로 큐를 사용합니다. 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장합니다. 이렇게 함으로써 노드를 접근한 순서대로 처리할 수 있게 됩니다.

큐 예제

[BOJ 10845] 큐 - 파이썬 풀이