[자료구조,Python] 파이썬으로 만들어보는 스택Stack

Stack

Stack의 자료구조에서 핵심은 First in last out 입니다. 즉 제일 먼져 들어온 데이터블록이 제일 마즈막에 나갑니다.

다시한번 실과 빨간색 데이터 블록으로 예를 들어보죠. 이번에는 실 끝에 매듭을 묶어서 매달아 놓을 수 있게 만들어 놓았습니다.

이 그림처럼 말이죠. 이 그림을 보면 빨간색 데이터 블록은 묶여진 매듭에 의해 매듭이 묶여져 있지 않은 한쪽으로밖에 나가지 못합니다. 또 빨간색 데이터 블록을 빼낼 수 있는 출구가 하나밖에 없어서(매듭이 묶여져 있지 않은곳) 처음 들어간 데이터블록은 어쩔 수 없이 제일 마즈막에 나올 수 밖에 없습니다.

우리는 이와같은 현상을 First in Last Out 이라고 이야기합니다.

그리고 이것은 Stack의 모든 것 입니다.

Stack 에는 대표적인 2가지 메소드가 있다. push 와 pop 이다.

Push는 말 그대로 Push다. 실에 빨간색 데이터 블록을 밀어넣는 행동이라고 생각하면 편하다. 즉 데이터를 삽입하는 메소드 이다.
반면 POP 은 Push와 반대이다. 실에 있는 빨간색 데이터 블록을 뺴내오는 행동이라고 생각하면 편하다. 즉 데이터를 추출하는 메소드 이다.

우리는 singly linked list에서 시작과 끝 데이터 블록 수를 표현하는 Header , tail, size 로 구성했다.
하지만 눈치챌 사람들은 챌 수 있었듯이, 스택은 데이터의 삽입과 삭제가 한곳에서만 일어난다. 그렇기 떄문에 데이터 삽입에 활용한 tail을 스택에서는 필요가 없어진다.

스택에서는 제일 처음 데이터의 삽입과 추출이 이루워지는 TOP 과** 빨간색 데이터 블록 수 즉 데이터의 크기를 표현하는 Size** 이 두가지가 필요하다.

class Node

먼져 노드를 만들어야한다. 노드는 data라는 빨간색 블록과 data의 다음 값이 저장될 next를 필요로한다. 우리는 node 클래스에서 이 객체를 생성한다(push 와 pop을위하여).

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
    
    def get_data(self):
        return self.data
        #현재 data를 return 
        
    def get_next(self):
        return self.next
        #다음 data를 return
        
    def set_next(self, next):
        self.next = next
        #다음 data를 setting

Class Stack

우리는 위에서 이야기한 push 와 pop의 동작을 수행하는 메소드를 만들어 볼 것이다.

Push Method

def push(self,data):
    new_node = Node(data)
    self.size += 1
    if self.top == None:
        self.top = new_node
    else:
        new_node.set_next(self.top)
        self.top = new_node

저장된 값이없으면 top이 새로운 대이터를 가리키게 했고, 아닌경우는 새로운 데이터 다음값을 현재 top에 저장되어있는 데이터로 바꿔주고, 새로운 데이러를 top으로 지정했다.

Pop Method

def pop(self):
    topData = self.top
    if topData != None:
        self.top = topData.get_next()
        self.size -= 1
    return topData

top에 저장된 데이터가 없을때만 작동한다. top에 저장된 데이터가 없다는 뜻은 텅빈 노드만 있다는 의미와 같은의미이기 때문이다. top에 데이터가 있을경우, top은 다음 블록을 가리키게 한다.

내 코드

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        
    def get_data(self):
        return self.data
    
    def get_next(self):
        return self.next
    
    def set_next(self, next):
        self.next = next
        
class Stack:
    def __init__(self):
        self.size = 0
        self.top = None
        
    def push(self,data):
        new_node = Node(data)
        self.size += 1
        if self.top == None:
            self.top = new_node
        else:
            new_node.set_next(self.top)
            self.top = new_node
            
    
    def pop(self):
        topData = self.top
        if topData != None:
            self.top = topData.get_next()
            #topData = topData.get_next()
            self.size -= 1
        return topData

        
    def print_stack(self):
        print(">> current stack")
        node = self.top
        while node != None:
            print(node.get_data())
            node = node.get_next()
        print(">>>>>>>>>>>")

stack = Stack()
stack.push("Apple")
stack.push("Kiwi")
stack.push("Banana")
stack.print_stack()

node = stack.get_at(0)
if node != None:
    print(node.get_data())
else:
    print("index error")
print(">>>>>>>>>>>>")
while True:
    node = stack.pop()
    if node is None:
        break
    else:
        print("Pop : " + node.get_data())
        if node == None:
            break
stack.print_stack()

topData = topData.get_next() 와 self.top = topData.get_next() 로 진행했을때 결과에 차이가 있었다.

나는 topData 라는 참조변수가 self.top을 참조하게끔 했다. 그 후 topData의 다음값을 topData로 저장했고, 그것을 리턴했다.

while문에의해 다시 pop메소드로 돌아왔을 때 우리는 self.top을 변경하지않고 topData만 변경했기 때문에 다시 apple이 topData에 참조되어있었다. 그렇기때문에 계속 Kiwi가 출력되었던 것이다.

출력값

>> current stack
Banana
Kiwi
Apple
>>>>>>>>>>>
Banana
>>>>>>>>>>>>
Pop : Banana
Pop : Kiwi
Pop : Apple
>> current stack
>>>>>>>>>>>