자료구조 연결된 스택 구현 (Linked Stack) [파이썬]

안녕하세요. 오늘은 자료구조를 구현하는 가장 기본적인 방식(배열, 연결된 구조)중 하나인 연결된 구조를 파이썬으로 직접 구현해보는 시간을 갖겠습니다. 연결된 구조, 연결된 리스트가 뭔지 알고 싶으시다면 이 글 [작성 예정] 을 참고해주세요.

 

파이썬의 함수로 구현하는 것이 아니라 직접 구현해보겠습니다. 

참고 자료는 파이썬으로 쉽게 배우는 자료구조입니다.

 

class Node:
    def __init__(self, data, link = None):
        self.data = data
        self.link = link

# Node를 만들어보자 Node는 Data 필드와 Link 필드로 구성되어 있다.
# Link는 맨 처음 생성 될 때 아무것도 가르키지 않고 있어야 함으로 None을 디폴트 값으로 준다.
# 파이썬에서는 None, C언어에서는 Null이다.

# 연결된 스택 클래스를 만들어보자.

class LinkedStack:
    #연결된 구조로 만든 스택에는 top만 있으면 된다. 메모리가 꽉 차지않는 이상 계속 만들 수 있기 때문에
    # 배열로 만든 스택처럼 용량을 지정할 필요가 없다.
    def __init__(self,top = None):
        #처음에 top은 None을 가르키고 있어야한다.
        self.top = top
   
    def isFull(self):
        #연결된 구조로 만든 스택은 가득 찰 일이 거의 없다.. 항상 False을 반환해야한다.
        return False
   
    def isEmpty(self):
        #비어있는 지 확인하려면 top이 None을 가르키고 있다면 비어있는 것이다.
        return self.top == None
        #None이면 True를 그렇지 않으면 False를 리턴 해줄 것이다.

    def push(self, e):
        #isFull은 의미가 없기 때문에 검사 하지 않는다.
        #n에 노드(데이터가 e고 현재 link가 None인)를 만들어서 넣어준다.  
        n = Node(e)
        #n의 link가 현재 top을 연결해준다.    
        n.link = self.top
        #top이 다음 노드의 링크를 가르키게 해준다.
        self.top = n        
       
    def pop(self):
        #비어있을 수 있기 때문에 isEmpty는 의미가 있다.
        if not self.isEmpty():
            #먼저 현재 상단의 노드를 n에 집어 넣는다.
            n = self.top
            #top이 다음 걸 가르키게 한다.
            self.top = n.link
            #pop은 뭘 제거했는 지 알려줘야하기 때문에 데이터를 반환한다.
            return n.data
    def peek(self):
        if not self.isEmpty():
            return self.top.data

    def __str__(self):
        #str을 안해주면 스택의 내용을 출력해주는게 아니라 스택 객체의 정보를 알려준다.
        #0x00~~ 이런식으로..!
       
        #모든 노드를 순서대로 방문해야한다.
        #먼저 빈 리스트를 만들어주고
        arr = []
        node = self.top
        while not node == None :
            arr.append(node.data)
            node = node.link
        return str(arr)
   
    #자, 그럼 이제 test를 해보자. test는 

if __name__ == '__main__':

    S = LinkedStack()
    S.push('A')
    S.push('B')
    S.push('C')
    print(S)
  
    print('[%s] is deleted.' % S.pop()); 
    print(S)

코드를 실행하면 이렇게 나옵니다.

 

스택이기 때문에 A,B,C를 넣으면 

 

C

B

A 

 

이런식으로 쌓이는데. 만약 pop을 한다면 가장 위에 있던 C가 빠져나오게 된다!