Python의 스택 구현 이해

by

자료 구조는 프로그래밍 세계에서 중추적인 역할을 수행합니다. 자료를 효율적으로 조직하고 관리하는 방법을 제공하여 프로그램의 성능을 향상시키는 데 기여합니다. 그중 스택은 가장 기초적이면서도 핵심적인 자료 구조 중 하나입니다.

이제 스택의 개념과 Python에서 이를 구현하는 다양한 방법을 자세히 살펴보겠습니다.

스택이란 무엇인가?

스택은 마치 책이나 의자를 차곡차곡 쌓아 놓은 더미와 유사한 구조를 가집니다. 이러한 스택은 LIFO(Last-In/First-Out) 원칙, 즉 ‘후입선출’이라는 규칙에 따라 동작합니다. 다시 말해, 가장 마지막에 스택에 들어간 요소가 가장 먼저 스택에서 제거되는 구조입니다. 실제 사례를 통해 좀 더 자세히 알아보겠습니다.

만약 여러 권의 책이 쌓여 있는 더미가 있다고 가정해 봅시다.

맨 위에서 세 번째 책을 꺼내려면, 그 위에 놓인 두 권의 책을 먼저 제거해야 합니다. 이처럼 맨 위에 있는 책은 더미의 가장 마지막에 놓였지만, 제거할 때는 가장 먼저 제거됩니다. 프로그래밍에서의 스택 자료 구조는 이와 동일한 LIFO 원칙에 기반합니다.

스택의 주요 연산

스택에는 일반적으로 다음과 같은 두 가지 주요 연산이 있습니다.

1. 푸시(Push)

스택의 맨 위에 새로운 자료를 추가하는 연산입니다.

2. 팝(Pop)

스택의 맨 위에 있는 자료를 제거하는 연산입니다.

아래 그림을 통해 푸시 및 팝 연산을 시각적으로 확인할 수 있습니다.

스택의 작동 방식을 더 자세히 이해하기 위해 몇 가지 보조 함수를 추가로 정의해 보겠습니다.

다음 함수들을 살펴보겠습니다.

피크(Peek)

스택의 최상위 요소(가장 최근에 추가된 요소)를 반환하되, 스택에서 제거하지는 않습니다.

isEmpty()

스택이 비어 있는지 여부를 확인하여 boolean 값(True 또는 False)으로 반환합니다.

이제 스택 자료 구조의 이론적인 개념은 충분히 다루었으므로, 실제 구현으로 넘어가 보겠습니다.

만약 온라인 컴파일러를 사용할 수 없다면, 여러분의 PC에 Python이 설치되어 있다고 가정하겠습니다.

스택 구현하기

스택은 다른 자료 구조에 비해 비교적 쉽게 구현할 수 있습니다. Python에서는 다양한 방법으로 스택을 구현할 수 있습니다.

하나씩 자세히 살펴보겠습니다.

#1. 리스트를 이용한 구현

Python의 내장 리스트 자료형을 활용하여 스택을 구현해 보겠습니다. 다음은 스택을 단계별로 구현하는 과정입니다.

1단계: Stack이라는 이름의 클래스를 정의합니다.

class Stack:
	pass

2단계: 데이터를 저장할 리스트가 필요합니다. Stack 클래스 안에 elements라는 이름의 빈 리스트를 초기화합니다.

class Stack:
	def __init__(self):
		self.elements = []

3단계: 스택에 데이터를 추가하기 위한 push 메서드를 구현합니다. 이 메서드는 데이터를 인자로 받아 elements 리스트에 추가합니다.

class Stack:
	def __init__(self):
		self.elements = []

	def push(self, data):
		self.elements.append(data)
		return data

4단계: 스택의 최상위 요소를 제거하는 pop 메서드를 구현합니다. 리스트의 pop 메서드를 활용하면 간단하게 구현할 수 있습니다.

class Stack:
	## ...
	def pop(self):
		return self.elements.pop()

필수적인 스택 연산이 구현되었습니다. 이제 스택의 상태를 파악하는 데 도움이 되는 보조 함수를 추가하겠습니다.

5단계: 음수 인덱스를 활용하여 스택의 최상위 요소를 가져오는 peek 메서드를 구현합니다. elements[-1]은 리스트의 마지막 요소, 즉 스택의 최상위 요소를 반환합니다.

class Stack:
	## ...

	def peek(self):
		return self.elements[-1]

6단계: 리스트의 길이가 0이면 스택이 비어 있는 상태입니다. 스택이 비어 있는지 여부를 확인하는 is_empty 메서드를 구현합니다.

class Stack:
	## ...
	def is_empty(self):
		return len(self.elements) == 0

리스트를 활용하여 스택 구현이 완료되었습니다.

잠깐! 구현은 완료했지만, 실제로 어떻게 사용하는지 살펴보지 않았습니다. 어떻게 사용할 수 있을까요?

이제 스택을 사용하는 방법을 살펴보겠습니다. 먼저 Stack 클래스의 객체를 생성해야 합니다. 어렵지 않으니 함께 해봅시다.

class Stack: 
    ## ...

if __name__ == '__main__':
    stack = Stack()

스택 객체를 생성했고, 이제 사용할 준비가 되었습니다. 다음 단계를 따라 스택 연산을 테스트해 보겠습니다.

  • is_empty 메서드를 사용하여 스택이 비어 있는지 확인합니다. True가 반환되어야 합니다.
  • push 메서드를 사용하여 숫자 1, 2, 3, 4, 5를 스택에 푸시합니다.
  • 다시 is_empty 메서드를 호출하면 False가 반환되어야 합니다. 확인해 보십시오.
  • peek 메서드를 사용하여 스택의 최상위 요소를 출력합니다.
  • pop 메서드를 사용하여 스택에서 최상위 요소를 제거합니다.
  • peek 메서드를 사용하여 다시 최상위 요소를 확인합니다. 4가 출력되어야 합니다.
  • 이제 스택의 모든 요소를 팝합니다.
  • 마지막으로 is_empty 메서드를 호출하면 True가 반환되어야 합니다. 확인해 보십시오.

위 단계를 모두 성공적으로 완료했다면 스택 구현에 성공한 것입니다. 위의 단계를 코드로 작성해 보십시오.

코드를 작성했나요? 아직 작성하지 못했더라도 걱정하지 마십시오. 아래 코드를 참조하십시오.

class Stack: 
    def __init__(self): 
        self.elements = [] 
    
    def push(self, data): 
        self.elements.append(data) 
        return data 
    
    def pop(self): 
        return self.elements.pop() 
        
    def peek(self): 
        return self.elements[-1] 
        
    def is_empty(self): 
        return len(self.elements) == 0

if __name__ == '__main__':
    stack = Stack()
    
    ## is_empty 메서드 확인 -> true
    print(stack.is_empty())

    ## 요소 푸시
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)

    ## 다시 is_empty 메서드 확인 -> false
    print(stack.is_empty())

    ## 스택의 최상위 요소 출력 -> 5
    print(stack.peek())

    ## 최상위 요소 제거 -> 5
    stack.pop()

    ## peek 메서드를 사용하여 최상위 요소 확인 -> 4
    print(stack.peek())

    ## 모든 요소 제거
    stack.pop()
    stack.pop() 
    stack.pop() 
    stack.pop() 

    ## 마지막으로 is_empty 메서드 확인 -> true
    print(stack.is_empty())

축하합니다! 리스트 자료형을 사용하여 스택을 처음부터 구현했습니다. 위의 코드를 실행하면 아래와 같은 결과를 얻을 수 있습니다.

True
False
5
4
True

리스트 데이터 유형은 그 자체로 스택처럼 사용할 수 있습니다. 위에서 구현한 스택은 다른 프로그래밍 언어에서 스택을 구현하는 데에도 도움이 될 것입니다.

관련 자료를 위해 리스트 관련 문서를 참조할 수도 있습니다.

이제 스택처럼 사용할 수 있는 collections 모듈의 내장 deque를 살펴보겠습니다.

#2. collections 모듈의 deque를 이용한 구현

deque(양방향 큐)는 양쪽 끝에서 요소를 추가하거나 제거할 수 있는 특징을 가지고 있기 때문에 스택으로도 활용할 수 있습니다. LIFO 원칙을 따르도록 약간의 조작만 거치면 됩니다.

deque는 이중 연결 리스트를 기반으로 구현되어 있습니다. 이러한 특징 덕분에 요소의 삽입 및 삭제 성능이 일관적입니다. 연결 리스트의 중간 요소에 접근하는 데에는 O(n)의 시간이 소요되지만, 스택에서는 중간 요소에 접근할 필요가 없기 때문에 deque를 스택으로 활용하는 데 아무런 문제가 없습니다.

스택을 구현하기 전에, 큐를 사용하여 스택을 구현할 때 사용하는 메서드를 먼저 살펴보겠습니다.

  • append(data) – 데이터를 스택에 푸시하는 데 사용
  • pop() – 스택에서 최상위 요소를 제거하는 데 사용

피크(peek) 메서드나 isEmpty 메서드와 직접적으로 대응되는 메서드는 없습니다. peek 메서드 대신 스택 전체를 출력하는 방식으로 대체할 수 있습니다. 또한 스택이 비어 있는지 여부는 len 메서드를 활용하여 확인할 수 있습니다.

이제 collections 모듈의 deque를 사용하여 스택을 구현해 봅시다.

from collections import deque

## deque 객체 생성
stack = deque()

## 스택이 비어 있는지 확인 -> true
print(len(stack) == 0)

## 요소 푸시
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)

## 다시 스택이 비어 있는지 확인 -> false
print(len(stack) == 0)

## 스택 출력
print(stack)

## 최상위 요소 제거 -> 5
stack.pop()

## 스택 출력
print(stack)

## 모든 요소 제거
stack.pop()
stack.pop()
stack.pop()
stack.pop()

## 마지막으로 스택이 비어 있는지 확인 -> true
print(len(stack) == 0)

이것으로 collections 모듈의 deque를 사용하여 스택을 구현하는 방법을 알아보았습니다. 위의 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.

True
False
deque([1, 2, 3, 4, 5])
deque([1, 2, 3, 4])
True

지금까지 스택을 구현하는 두 가지 방법을 살펴보았습니다. 스택을 구현하는 다른 방법이 또 있을까요? 네! 이 튜토리얼에서 스택을 구현하는 마지막 방법을 살펴보겠습니다.

#3. LifoQueue를 이용한 구현

LifoQueue라는 이름 자체가 LIFO(후입선출) 원칙을 따른다는 것을 알려줍니다. 따라서 스택으로 활용하기에 적합합니다. LifoQueue는 Python의 queue 모듈에서 제공되며, 스택 구현에 유용한 몇 가지 편리한 메서드를 제공합니다. 이러한 메서드를 살펴보겠습니다.

  • put(data) – 데이터를 큐에 추가(푸시)합니다.
  • get() – 큐에서 최상위 요소(가장 최근에 추가된 요소)를 제거(팝)합니다.
  • empty() – 큐(스택)가 비어 있는지 여부를 확인합니다.
  • qsize() – 큐(스택)에 들어 있는 요소의 개수를 반환합니다.

이제 queue 모듈의 LifoQueue를 사용하여 스택을 구현해 봅시다.

from queue import LifoQueue

## LifoQueue 객체 생성
stack = LifoQueue()

## 스택이 비어 있는지 확인 -> true
print(stack.empty())

## 요소 푸시
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)

## 다시 스택이 비어 있는지 확인 -> false
print(stack.empty())

## 모든 요소 제거
print(stack.get())
print(stack.get())
print(stack.get())

## 스택 크기 출력
print("Size", stack.qsize())

print(stack.get())
print(stack.get())

## 마지막으로 스택이 비어 있는지 확인 -> true
print(stack.empty())

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

True
False
5
4
3
Size 2
2
1
True

스택의 활용

이제 스택에 대한 지식이 충분히 쌓였으므로, 프로그래밍 문제에 스택을 실제로 적용해 보겠습니다. 스택을 사용하여 해결할 수 있는 문제를 살펴보겠습니다.

주어진 문자열에서 괄호, 중괄호, 대괄호의 균형이 맞는지 확인하는 프로그램을 작성해 보겠습니다.

몇 가지 예시를 살펴보겠습니다.

입력: “[{}]([])”

출력: 균형 있음

입력: “{[}]([])”

출력: 균형 없음

스택을 활용하여 위 문제를 해결할 수 있습니다. 문제 해결 단계를 살펴보겠습니다.

  • 문자를 저장할 스택을 생성합니다.
  • 문자열의 길이가 홀수이면, 괄호의 균형이 맞지 않습니다.
  • 주어진 문자열을 순회합니다.
    • 현재 문자가 여는 괄호(‘(‘, ‘{‘, ‘[‘)이면, 스택에 푸시합니다.
    • 현재 문자가 닫는 괄호(‘)’, ‘}’, ‘]’)이면, 스택에서 팝(pop)합니다.
    • 팝된 문자가 짝이 맞는 여는 괄호와 일치하면 계속 진행합니다. 그렇지 않다면 괄호의 균형이 맞지 않는 것으로 판단합니다.
  • 반복문이 끝난 후 스택이 비어 있다면 괄호의 균형이 맞는 것이고, 그렇지 않다면 균형이 맞지 않는 것입니다.

괄호 일치 여부를 확인하기 위해 앞에서 구현했던 스택 데이터 유형을 사용할 수 있습니다.

## 스택
class Stack: 
    def __init__(self): 
        self.elements = [] 
    
    def push(self, data): 
        self.elements.append(data) 
        return data 
        
    def pop(self): 
        return self.elements.pop() 
    
    def peek(self): 
        return self.elements[-1] 
        
    def is_empty(self): 
        return len(self.elements) == 0

def balance_check(expression):
    ## 문자열 길이 확인
    if len(expression) % 2 != 0:
        ## 문자열 길이가 홀수이면 균형이 맞지 않음
        return False
    
    ## 괄호 세트 정의
    opening_brackets = set('([{') 
    pairs = set([ ('(',')'), ('[',']'), ('{','}') ]) 
    
    ## 스택 초기화
    stack = Stack()
    
    ## 문자열 순회
    for bracket in expression:

        ## 현재 문자가 여는 괄호인지 확인
        if bracket in opening_brackets:
            ## 스택에 추가
            stack.push(bracket)
        else:
            ## 스택에서 마지막 괄호 꺼내기
            popped_bracket = stack.pop()
        
            ## 꺼낸 괄호와 현재 괄호 쌍이 맞는지 확인
            if (popped_bracket, bracket) not in pairs:
                return False
    
    return stack.is_empty()

if __name__ == '__main__':
    if balance_check('[{}]([])'):
        print("균형 있음")
    else:
        print("균형 없음")
    
    if balance_check('{[}]([])'):
        print("균형 있음")
    else:
        print("균형 없음")

스택을 활용하면 더 다양한 문제를 해결할 수 있습니다. 위에서 제시된 문제는 스택의 활용 예시 중 하나일 뿐입니다. 스택 개념을 적절한 곳에 응용하여 더 많은 프로그래밍 문제를 해결해 보시기 바랍니다.

마무리

드디어 튜토리얼을 마쳤습니다! 튜토리얼을 제작하는 동안 즐거웠던 만큼, 이 튜토리얼을 즐겁게 읽으셨기를 바랍니다. 이것으로 스택 관련 튜토리얼을 마치겠습니다.

즐거운 코딩하세요! 🙂 👨‍💻