까먹기 전에 적어두는 Stack, Queue

stack : 후입선출

queue : 선입선출

 

스택구조

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

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

    def push(self, val):
        self.top = Node(val, self.top) # 값을 val로 기존의 self.top를 next로 가지는 새로운 노드를 생성하여 새로운 self.top로 함

    def pop(self):
        if not self.top:
            return None

        node = self.top
        self.top = node.next # self.top을 현재 노드(pop예정인 최상단 노드)의 next로 변경
        return node

    def is_empty(self):
        return self.top is None

 

 

큐 구조

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

class Queue:
    def __init__(self):
        self.front = None

    def push(self, val):
        if not self.front:
            self.front = Node(val, None)
            return

        node = self.front # self.front부터 탐색시작
        while not node.next: # 탐색중인 노드의 next값이 없을때까지 반복
            node = node.next # 다음 노드로 이동
        node.next = Node(val, None) # 현재 노드(반복문을 거쳐왔으므로 가장 끝 노드)의 next에 새로운 노드를 만들고 값은 val, next는 없음(새로운 가장 끝값 생성)

    def pop(self):
        if not self.front:
            return None
        node = self.front
        self.front = node.next # 기존의 self.front의 next를 새로운 self.front로 함
        return node.data # (가장 앞에 있는) 노드의 데이터를 출력

    def in_empty(self):
        return self.front is None

 

몇시간동안 강의와 씨름한 뒤에 어떤 방식으로 작동하는 알게 되었다. 큐구조 구현할때 실수를 하지 않았다면 더 빨리 끝났을지도...

 

아무튼 이제 큐와 스택의 작동방식을 제대로 알게되었고 코드로 구현할 수도 있다.