파이썬에서의 추상데이터타입![1]

본 포스트는 python3.7, pycharm환경에서 작성되었습니다.

 

파이썬에서의 추상데이터타입![1]

 

앞서서 c에서의 스택과 큐에 대해서 알아보았습니다. 그렇다면 객체지향언어인 파이썬에서는 어떻게 구현될까요? 우선 c에서의 데크는 구현하지 않았기 때문에 스택과 큐만 구현해보도록 하겠습니다.

 

추상데이터 타입(Abstract Data Type이하 adt)은 전체적인 자료구조의 클래스에 모델을 가르킵니다. 

 

자료구조는 크게 배열기반의 연속방식과 포인터 기반의 연결 방식으로 분류합니다.

 

연속방식	포인터 기반의 연결 방식
연속적으로 할당된 자료구조 즉, 단일 메모리에 물리적으로 연속적으로 구성되는 메모리 조각인 메모리 슬래브로 구성됩니다.   유형 : 문자열, 리스트, 튜플, 딕셔너리	포인터에 연결되는 메모리 청크 등 스택, 큐, 힙, 데크 등이 있다.

 

1.스택

배열의 끝에서만 데이터를 접근할 수 있는 선형 자료구조 입니다. c포스트에서 말씀 드렸듯이, 이는 후입선출(LIFO)방식을 따릅니다. 즉, 블럭쌓기와 같은 구조라 생각하면 쉽습니다.

 

그렇다면 파이썬에서 스택의 명령은 어떤것이 있을까요

push()	스택의 맨 끝에 항목을 삽입한다
pop()	스택 맨 끝 항목을 return 한 후 remove
top/peek	스택 맨 끝 항목을 조회
empty()	스택이 비어 있는지 확인
size()	스택의 사이즈를 확인

등으로 이루어져 있습니다. 언뜻보면 리스트명령와 비슷하면서도 다릅니다.

 

코드로 구현하여 그 차이점을 보겠습니다.

 

class Stack(object):
        def __init__(self):
                self.data = []
                #데이터를 받아올 스택의 리스트를 구현
 
        def isEmpty(self):
                return not bool(self.data)
 
        def push(self, item):
                self.data.append(item)
 
        def pop(self):
                item = self.data.pop()
                if(item is not None):
                        return item
                else:
                        print("스택이 비어 있습니다")
 
        def size(self):
                return len(self.data)
 
        def peek(self):
                if self.data:
                        return self.items[-1]
 
                else:
                        print("스택이 비어 있습니다.")
 
 
        def __repr__(self):
                return repr(self.data)
 
if __name__ == "__main__":
        stack = Stack()
        print("스택이 공백인지 확인합니다. {0}".format(stack.isEmpty()))
        print("스택에 1-9까지 수를 삽입합니다.")
        for i in range(1,10):
                stack.push(i)
 
        print("스택의 길이 : {0}".format(stack.size()))
        print(stack)

앞서 포스팅한 c와는 구현방식도 다르지만, 좀 더 쉽게 구현할 수 있습니다. 리스트형태로 들어가 데이터를 후입선출 방식을 따르며 정상작동하는 모습을 확인할 수 있습니다. 

 

스택은 깊이 우선탐색 분야에서 활발하게 사용됩니다! 

 

다음은 큐에 대한 포스트를 하도록 하겠습니다.

 

봐주셔서 감사합니다~

 

댓글/피드백 환영합니다.