1-4. [자료구조이론] 스택(Stack)

Shy·2023년 8월 1일

자료구조 ＆ 알고리즘(Python)

목록 보기

4/24

스택

한쪽 끝에서 자료를 넣거나 뺼 수 있는, 데이터를 제한적으로 접근할 수 있는 구조

스택(Stack)은 컴퓨터 과학에서 매우 중요한 자료구조 중 하나다. 스택은 항목들이 쌓여 있는 구조를 뜻하며, LIFO(Last-In, First-Out) 원칙을 따른다. 이 말은, 가장 마지막에 스택에 추가된 항목이 가장 먼저 제거된다는 뜻이다.

스택은 일상생활에서도 쉽게 볼 수 있다. 예를 들어, 접시를 쌓아두는 곳을 생각해보자. 새로운 접시는 스택의 맨 위에 놓이며, 사용할 때는 맨 위의 접시부터 꺼내게 된다.

스택은 다음과 같은 기본 연산을 제공한다.

Push: 스택의 맨 위에 새로운 항목을 추가한다.
Pop: 스택의 맨 위에 있는 항목을 제거하고 그 항목을 반환한다. 스택이 비어 있을 경우, pop 연산은 에러를 반환한다.
Peek/Top: 스택의 맨 위에 있는 항목을 반환하지만 제거하지는 않는다. 스택이 비어 있을 경우, 이 연산은 에러를 반환한다.
isEmpty: 스택이 비어 있는지 확인한다.

스택은 여러가지 문제를 해결하는 데 유용하게 사용된다. 함수 호출 스택, 실행 취소 스택, 메모리 관리 등 다양한 컴퓨팅 문제에 적용되며, 괄호 짝 맞추기, 히스토리 관리(웹 브라우저의 앞/뒤 버튼), 트리 또는 그래프 데이터 구조의 깊이 우선 탐색(DFS) 등 다양한 알고리즘에도 사용된다.

큐는 FIFO, 스택은 LIFO를 쓰는것이 차이가 있다.

스택의 활용

스택은 다양한 프로그래밍 시나리오와 알고리즘에서 중요하게 활용됩니다. 몇 가지 주요한 사용 예시는 다음과 같다.

함수 호출: 프로그램이 함수를 호출할 때, 호출된 함수의 매개변수, 리턴 주소, 로컬 변수 등이 스택에 저장된다. 이는 함수가 종료될 때까지 유지되며, 이후에는 스택에서 제거된다. 이러한 스택의 사용은 중첩된 함수 호출을 가능하게 하며, 프로그램의 실행 흐름을 관리한다.
실행 취소(undo): 많은 프로그램(텍스트 에디터, 웹 브라우저 등)에서 사용자가 수행한 최근 작업을 저장하는 데 스택을 사용하여, 사용자가 "실행 취소"를 선택할 때 이전 상태로 돌아갈 수 있다.
문법 검사: 프로그래밍 언어에서 괄호나 태그 등의 짝을 확인할 때 스택이 사용된다. 여는 괄호나 태그를 만나면 스택에 푸시하고, 닫는 괄호나 태그를 만나면 스택에서 팝하여 짝이 맞는지 확인한다.
깊이 우선 탐색(DFS): 트리나 그래프의 깊이 우선 탐색에 스택을 사용할 수 있다. 현재 노드를 스택에 푸시하고, 인접한 노드를 방문하면서 탐색을 진행한다. 더 이상 방문할 노드가 없으면 스택에서 팝하여 이전 노드로 돌아간다.
표현식 평가: 스택은 수학적 표현식(중위, 후위 표기법 등)의 평가에도 사용된다. 연산자와 피연산자를 적절히 스택에 푸시하고 팝하면서 표현식을 평가한다.
메모리 관리: 특히 컴퓨터의 메모리 관리에서 스택은 중요한 역할을 한다. 컴파일러는 메모리에 스택을 만들어 로컬 변수를 저장하고, 이 스택은 프로그램의 실행 도중 동적으로 커지거나 줄어들 수 있다.

위와 같은 방식으로 스택은 다양한 문제를 풀거나 특정 작업을 수행하는 데 유용한 도구로 활용된다.

스택 예제

# 스택 생성
stack = []

# 스택에 요소 추가 (push 연산)
stack.append('apple')
stack.append('banana')
stack.append('cherry')

print(stack)  # 출력: ['apple', 'banana', 'cherry']

# 스택에서 요소 제거 (pop 연산)
item = stack.pop()
print(item)  # 출력: 'cherry'
print(stack)  # 출력: ['apple', 'banana']

이 예제에서는, 'cherry'가 스택에 마지막에 추가되었으므로 'cherry'가 먼저 제거된다. 이러한 행동은 스택의 LIFO(Last In, First Out) 원칙을 따르는 것이다.

위와 같은 방식으로 파이썬의 기본 데이터 타입을 활용해 스택을 간단하게 구현하고 활용할 수 있다. 이 외에도 파이썬 표준 라이브러리의 collections.deque나 queue.LifoQueue 등을 이용하여 스택을 구현할 수도 있다.

스택 예제2

def recursive(data):
   if data < 0:
      print('ended')
   else:
      print(data)
      recursive(data - 1)
      print('returned', data)

이 코드는 재귀적(recursive) 함수를 사용하여 입력된 숫자부터 0까지 카운트다운하는 간단한 프로그램이다.

재귀적 함수는 함수가 자신을 다시 호출하는 것을 의미한다. 이 경우에는 recursive 함수는 자신을 호출하면서 입력값 data를 1씩 감소시킨다.

함수의 동작은 다음과 같다.

입력값 data가 0보다 작으면, "ended"를 출력하고 함수를 종료한다.
그렇지 않으면, 현재 data 값을 출력하고, data 값을 1 감소시켜 자기 자신(recursive 함수)을 다시 호출한다.
재귀 호출이 종료되면, "returned"와 함께 현재 data 값을 다시 출력한다.

이를 통해 재귀의 개념과 스택의 원칙(Last-In, First-Out)을 쉽게 이해할 수 있다. 마지막으로 호출된 재귀 함수가 가장 먼저 종료되고, 이후에는 이전에 호출된 함수 순서대로 종료되는 것을 볼 수 있다.
예를 들어, 이 함수에 3을 입력하면 다음과 같이 출력된다.

3
2
1
0
ended
returned 0
returned 1
returned 2
returned 3

즉, 재귀 호출을 통해 3부터 0까지 카운트다운하고, 그 후에는 함수 호출이 이전 순서대로 종료되면서 'returned' 메시지를 출력한다.

하지만, ended에서 끝나지 않고, returned 3까지 출력되는 이유는 'recursive'함수가 재귀적으로 동작하기 때문이다.

함수는 입력값 data가 0보다 작을 때까지 자신을 계속 호출하며, 이 때 data는 매번 1씩 감소한다.

3을 입력값으로 주었을 때 함수는 아래와 같이 동작한다.

data가 3입니다. 3은 0보다 크므로 print(data)가 실행되어 3이 출력된다. 그리고 recursive(data - 1)을 호출하게 됩니다. 이 때, data 값은 3으로 고정되어 있다.
이제 data는 2입니다. 2는 0보다 크므로 print(data)가 실행되어 2가 출력된다. 그리고 recursive(data - 1)을 호출하게 된다. 이 때, data 값은 2로 고정되어 있다.
이제 data는 1입니다. 1은 0보다 크므로 print(data)가 실행되어 1이 출력된다. 그리고 recursive(data - 1)을 호출하게 된다. 이 때, data 값은 1로 고정되어 있다.
이제 data는 0이다. 0은 0보다 크지 않지만, print(data)가 실행되어 0이 출력됩니다. 그리고 recursive(data - 1)을 호출하게 된다. 이 때, data 값은 0으로 고정되어 있다.
이제 data는 -1다. -1은 0보다 작으므로 "ended"가 출력되고 함수가 종료된다.

하지만 이제 함수의 실행이 종료되는 것이 아니다. 아직 실행이 종료되지 않은 recursive 함수 호출이 스택에 남아 있기 때문이다. 이 때 스택의 특성(Last In, First Out)이 작용하여 가장 마지막에 호출된 recursive 함수부터 종료가 시작된다.

recursive 함수는 data 값이 0인 상태로 print('returned', data)를 실행하여 'returned 0'을 출력한다.
recursive 함수는 data 값이 1인 상태로 print('returned', data)를 실행하여 'returned 1'을 출력한다.
recursive 함수는 data 값이 2인 상태로 print('returned', data)를 실행하여 'returned 2'을 출력한다.
마지막으로 recursive 함수는 data 값이 3인 상태로 print('returned', data)를 실행하여 'returned 3'을 출력한다.

따라서 이 코드는 data 값이 감소하면서 함수를 호출하고, 이후에 함수 호출이 종료될 때 각 data 값을 사용하여 'returned' 메시지를 출력한다. 이는 재귀와 스택의 동작 원리를 보여주는 좋은 예시다.

파이썬 리스트 기능에서 제공하는 메서드로 스택 사용해보기

리스트의 append() 메소드는 스택의 push 연산에 해당하며, pop() 메소드는 스택의 pop 연산에 해당한다.

# 스택을 생성하고 초기화합니다.
stack = []

# 스택에 요소를 push합니다.
stack.append("A")
stack.append("B")
stack.append("C")
print(stack)  # 출력: ['A', 'B', 'C']

# 스택에서 요소를 pop합니다.
print(stack.pop())  # 출력: 'C'
print(stack)  # 출력: ['A', 'B']

위의 코드에서, append() 메소드는 리스트의 끝에 요소를 추가하며, pop() 메소드는 리스트의 마지막 요소를 제거하고 반환합니다. 이러한 메소드들을 사용하여 파이썬 리스트를 스택처럼 사용할 수 있다.

스택의 특징인 LIFO(Last In, First Out) 원칙에 따라, 가장 마지막에 추가된 요소 'C'가 가장 먼저 제거되고 반환되었다.

연습1: 리스트 변수로 스택을 다루는 pop, push기능 구현해보기

stack_list = list()

def push(data):
	stack_list.append(data)
    
def pop():
	data = stack_list[-1]
    del stack_list[-1]
    return data
    
for index in range(10):
	push(index) #0번부터 9번까지 데이터가 들어간다.

pop() #9가 출력된다.

스택의 장점

스택 자료구조는 다양한 문맥에서 여러 가지 장점을 제공합니다. 몇 가지 주요 장점은 다음과 같다.

간결성: 스택은 간단한 데이터 구조로서, 구현이 쉽고 이해하기도 쉽다. 이로 인해 코드를 간결하게 유지할 수 있다.
순서 역술: 스택은 Last-In, First-Out (LIFO) 원칙을 따르기 때문에, 가장 마지막에 들어온 요소가 가장 먼저 나가는 방식을 자연스럽게 처리할 수 있다. 이는 특정한 종류의 문제, 예를 들어 실행 취소(undo) 기능, 괄호의 짝 맞추기 등에 유용하다.
함수 호출 관리: 컴퓨터의 메모리 관리에서, 스택은 함수 호출과 관련된 정보(리턴 주소, 지역 변수 등)를 저장하는 데 사용된다. 이는 프로그램의 실행 흐름을 유지하고 관리하는 데 중요한 역할을 한다.
깊이 우선 탐색(DFS): 스택은 트리나 그래프 데이터 구조의 깊이 우선 탐색에 이용된다. 스택을 이용하면 노드를 방문하는 순서를 쉽게 관리할 수 있다.
표현식 평가 및 변환: 수학적 표현식의 평가나 변환에 있어서 스택은 중요한 역할을 한다. 중위, 전위, 후위 표현식의 변환 및 평가를 스택을 이용해 진행한다.
메모리 효율성: 스택은 메모리를 효율적으로 사용합니다. 스택에서 데이터를 추가하거나 제거하는 연산은 일정한 시간(O(1))을 필요로 하며, 스택에 저장된 데이터는 연속적인 메모리 주소에 위치하므로 공간 효율성이 높다.

이런 장점들 덕분에 스택은 많은 컴퓨팅 문제를 해결하는 데 유용하게 사용된다.

스택의 단점

스택이 유용한 도구이긴 하지만, 몇 가지 단점도 존재한다.

크기 제한: 일반적으로 스택의 크기는 고정되어 있습니다. 이는 스택이 사용하는 메모리를 미리 할당해야 하기 때문입니다. 스택이 꽉 차면, 더 이상의 요소를 추가할 수 없으며, 이를 스택 오버플로우라고 부릅니다. 이는 프로그램에서 심각한 오류를 발생시킬 수 있습니다.
데이터 접근 및 검색: 스택은 LIFO(Last In, First Out) 원칙에 따라 동작하기 때문에, 가장 최근에 추가된 요소만이 직접 접근할 수 있습니다. 스택 내부의 중간 위치에 있는 요소에 접근하려면, 그 앞에 있는 요소들을 모두 제거해야 합니다. 이는 시간이 많이 소요될 수 있습니다. 또한, 특정 요소가 스택 내에 존재하는지 검색하는 것도 비효율적입니다.
복잡한 사용: 스택이 재귀 함수나 반복문 등에 종종 사용되기 때문에, 이를 적절히 사용하기 위해선 재귀적 사고나 프로그램의 흐름을 잘 이해해야 합니다. 스택을 잘못 사용하면 프로그램의 로직을 이해하기 어렵게 만들 수 있습니다.

이러한 단점들은 스택이 적합하지 않은 일부 사용 사례를 나타냅니다. 따라서, 스택을 사용할 때는 이러한 단점을 고려해야 합니다. 다른 데이터 구조(예: 큐, 링크드 리스트, 해시 테이블 등)가 더 적합한 경우도 많습니다.