자료구조/Python3) 연결리스트로 스택 구현

후입 선출 (Last in First Out) 자료구조인 스택은 Python에서 이미 list[]라는 자료형으로 구현되어 있다. 그래서 내장된 append, pop 함수를 이용해서 push,pop 메소드를 간단하게 구현할 수 있다. 그래서 이번에는 리스트 자료형을 사용하지 않고 각 노드가 next 노드에 대한 포인터를 가지고 있는 연결리스트로 스택을 구현해보았다. 

 

class Node 

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

연결 리스트의 각 노드들은 값(=data)을 가지고 다음 노드에 대한 포인터 (=next)를 갖는다. 

 

class Stack

스택은 기본적으로 top 포인터를 가지고 있다. LIFO 구조로 데이터에 접근하기 위해 pop 할 때 반환되어야 하는 가장 상단에 있는 노드를 가리키는 (=top) 포인터 정보를 가지고 있다. 

class Stack:
    def  __init__ (self):
        self.top = None
    
    ...

push(data)

스택에 데이터를 추가하는 메소드이다. 스택이 비어있는 상태라면 현재 추가되는 노드가 top으로 설정된다. 그렇지 않다면 새로운 노드의 next가 현재의 top을 가리키고 현재의 top이 새로운 노드로 갱신된다. 

    def push(self, data)->None:
        new_node = Node(data)
        if not self.is_empty():
            new_node.next = self.top
        self.top = new_node

old : [TOP] A [BOTTOM]

new : [TOP] B(= new_node) -> A [BOTTOM]   

추가된 노드가 top이 되어 pop의 대상이 된다. 

pop()

pop을 하면 스택의 최상단에 있는 값이 스택에서 빠져나오면서 반환된다. 

    def pop(self)->(int or None):
        if self.is_empty():
            return None
        else :
            popped = self.top.data
            self.top = self.top.next
            return popped

전체

아래는 전체 Stack 을 구현한 클래스 코드이다. push와 pop 이 외에 빈 스택인지 확인하는 메소드와 pop하지 않고 최상단의 값을 확인만 하는 메소드, 스택 전체를 프린트하는 메소드, 스택에 쌓인 데이터 개수를 반환하는 메소드 등을 추가로 구현하였다. 

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

class Stack:
    def  __init__ (self):
        self.top = None
    
    def push(self, data)->None:
        new_node = Node(data)
        if not self.is_empty():
            new_node.next = self.top
        self.top = new_node
            
    def pop(self)->(int or None):
        if self.is_empty():
            return None
        else :
            popped = self.top.data
            self.top = self.top.next
            return popped
    
    def check_top(self)->(int or None):
        if self.is_empty():
            return None
        else : 
            return self.top.data
    
    def is_empty(self)->bool:
        if self.top == None:
            return True
        else:
            return False
    
    def print_stack(self)->None:
        if self.is_empty():
            print("Stack is Empty!")
        else:
            print("Stack Status : TOP[ ", end = "")
            current_node = self.top
            while current_node:
                print(current_node.data, end = " ")
                current_node = current_node.next
            print("]BOTTOM")

    def stack_size(self) -> int:
        current_node = self.top
        size = 0
        while current_node:
            size += 1
            current_node = current_node.next
        return size