[자료구조] Stack 스택-Python으로 구현하기

1. 스택이란?

 스택(Stack) 이란 자료구조의 하나입니다. 스택은 먼저 들어간 요소가 나중에 나온다고 해서 FILO(First In Last Out) 이라고 말합니다. 스택의 사용 예시로는 재귀 함수의 실행 과정이 있습니다. 재귀함수를 호출할 때 호출 당한 함수가 끝난 뒤 호출을 한 함수가 끝나는 것과 같이 스택에 들어간 요소가 나오기 위해서는 그 이후에 삽입한 요소들이 모두 나와야 합니다.

2. 스택의 연산

 기본적으로 스택은 pop과 push 연산을 수행해 요소를 변경합니다. pop은 스택의 가장 위 요소를 제거하는 역할을 하고, push는 스택의 위에 새로운 원소를 삽입하는 역할을 합니다. 스택에서 중간 값만을 변경하거나 삭제할 수는 없습니다.

 스택을 직관적으로 이해해 봅시다. 스택을 다음 그림과 같이 표현해 보겠습니다.  

(그림 1)과 같은 스택에서 pop을 하면 스택의 가장 위에 있는 원소인 4가 제거되어 (그림 2)의 모습으로 바뀐다. 즉 pop 연산은 스택의 가장 위(top)요소를 제거 합니다. 

 (그림 2) 에서 (그림 3)으로 변할 때 push 연산은 스택의 가장 위에 11을 추가합니다. push 연산 또한 스택의 가장 위(top) 요소에 적용된다는 것을 알수 있습니다. 

 

스택을 FILO(First In Last Out) 와 같이 말하는 이유에 대해서 설명하겠습니다. 위 예시에서 스택의 가장 밑에 위치한 12가 pop되기 위해서는 그 위 의 4, 10, 7이 pop 되고, 12가 top에 위치한 상태여야 할 것입니다. 즉 가장 먼저 스택에 삽입되었을 12가 가장 마지막으로 나오게 된다는 것입니다. 

 

3. Python 구현

 Python으로 스택을 Class와 배열을 통해 직접 구현해보겠습니다. 사실 파이썬의 배열은 동적 배열이기 때문에 직접 만들어 쓰기에 어렵지 않습니다.

 

class Stack:
    def __init__(self):
        self.arr=[]
    def push(self,a):
        self.arr.append(a)
    def pop(self):
        del self.arr[-1]
    def size(self):
        return len(self.arr)
    def top(self):
        return self.arr[-1]
    def siz(self):  #size는 다른 함수로 이미 사용되고 있기 때문에 사용 불가...
        return len(self.arr)

 

 참고로 C++를 사용하는 경우 STL 라이브러리에 최적화 된 스택 라이브러리가 존재하기 때문에 실무 또는 P/S에서는#include<stack> 을 통해 STL 스택을 사용할 수 있습니다. 파이썬에도 스택 라이브러리가 있었던 것으로 기억하는데 찾아보니 검색되지 않네요. 혹시 파이썬의 스택 라이브러리에 대해 아시는 분은 댓글로 알려주시면 감사하겠습니다.