[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 21

* 수업은 JS 기반이지만 Python으로 구현

Section 21

스택 소개

• 후입선출, LIFO 원칙을 따르는 데이터 모음으로, 함수 호출을 다루는 호출 stack 같은 것이다.
• push와 pop을 수행할 때, O(1)이어야 한다.

스택 사용하는 경우

• 함수의 호출을 다룰 때
• Undo / Redo를 수행할 때
• 인터넷 브라우저에 있는 방문 기록을 보여줄 때

 

파이썬에서 리스트를 이용하여 LIFO 성질인 stack을 구현하는 두 가지 방법이 있다. 첫 번째는 리스트에 뒤로 쌓은 다음에 뒤부터 지우는 것이고, 두 번째는 리스트에 앞으로 쌓은 다음에 앞부터 지우는 것이다. 두 방법 중 전자가 더 효율이 좋은 이유는 새로운 항목의 추가 혹은 기존 항목의 제거에서 해당하는 요소의 인덱스만 수정하면 되기 때문이다. 그러나 효율성만을 따질 때는 LIFO 성질을 가진 stack을 활용하는 경우가 많지 않다. 게다가 매번 가장 나중에 들어온 요소를 삭제하는 pop을 수행할 때마다 포인터 next를 활용해 last 위치까지 것은 비효율적이므로 class를 이용한 구현에서는 후자의 방식을 활용할 것이다.

# LIFO 확인용 ver.1

stack = []

stack.append("google")
stack.append("X")
stack.append("youtube")

print(stack)

print(stack.pop())
print(stack)
print(stack.pop())
print(stack)
print(stack.pop())
print(stack)

# LIFO 확인용 ver.2

stack = []

print(stack.insert(0, "create new file"))
print(stack)
print(stack.insert(0, "resized file"))
print(stack)
print(stack.insert(0, "cloned out wrinkle"))
print(stack)

print(stack.pop(0))
print(stack)
print(stack.pop(0))
print(stack)
print(stack.pop(0))
print(stack)

 

class 소개

• 연결리스트에서 활용한 Node를 이용해서 값끼리 연결하며, first와 last라는 포인터 변수와 size라는 크기를 나타내는 변수를 constructor 함수에서 정의한다.
• 초기에는 포인터는 None으로 size는 0으로 정의한다.

push method 소개

• 값 하나를 입력하는 함수로, 그 값을 갖고 새로운 노드를 만든다.
• 만약 stack에 노드가 하나도 없을 경우, 입력값을 first이자 last가 되도록 설정한다.
• 만약 stack에 노드가 하나라도 있을 경우, 현재 first 값을 변수에 저장해두고, 새로운 값을 first로 지정한다.
• 새롭게 생성된 노드와 원래 first를 이어준다.
• stack의 크기를 하나 늘리고, 그 값을 반환한다.

pop method 소개

• 만약 stack에 노드가 없다면 Null을 반환한다.
• 현재 first 값을 저장할 임시 변수를 만든다.
• 만약 노드가 1개 남았다면, first와 last를 Null로 설정한다.
• 만약 노드가 1개 이상 존재한다면, first 노드를 원래 first의 다음 노드로 설정한다.
• stack 크기를 하나 줄인다.
• 제거된 노드의 값을 반환한다.

 

method 구현

class Node:
    #constructor
    def __init__(self, val):
        self.val = val
        self.next = None

class Stack:
    # constructor
    def __init__(self):
        self.first = None
        self.last = None
        self.size = 0

    # instance method
    def push(self, val):
        newNode = Node(val)

        if self.first is None:
            self.first = newNode
            self.last = newNode

        else:
            tmp = self.first
            self.first = newNode
            self.first.next = tmp

        self.size += 1
        return stack.size

    # instance method
    def pop(self):
        if self.first is None:
            return None

        tmp = self.first

        if self.first == self.last:
            self.last = None
        
        # self.first.next는 val 혹은 null일 것이므로
        # stack크기와 상관없이 self.first에 지정 가능하다
        self.first = self.first.next

        self.size -= 1
        return tmp.val
        
# stack 선언
stack = Stack()

print('\n---push fcn---')
# push 수행
num = 3
print('num: ', num)
print(stack.push(num))
print('first: ', stack.first.val)
print('\n')
num = 5
print('num: ', num)
print(stack.push(num))
print('first: ', stack.first.val)
print('\n')
num = 1
print('num: ', num)
print(stack.push(num))
print('first: ', stack.first.val)
print('\n')
num = 0
print('num: ', num)
print(stack.push(num))
print('first: ', stack.first.val)
print('\n')

print('\n---pop fcn---')
# pop 수행
print(stack.pop())
print('first: ', stack.first.val, 'size: ', stack.size)
print('\n')
print(stack.pop())
print('first: ', stack.first.val, 'size: ', stack.size)
print('\n')
print(stack.pop())
print('first: ', stack.first.val, 'size: ', stack.size)
print('\n')
print(stack.pop())
print('first: ', stack.first, 'size: ', stack.size)
print('\n')
print(stack.pop())
print('first: ', stack.first, 'size: ', stack.size)
print('\n')

스택: 빅오 복잡도

• Insertion: O(1)
• Removal: O(1)
• Searching: O(N)
• Access: O(N)

 

 

큐 소개

• 선입선출, FIFO 원칙을 따르는 데이터 모음

큐 사용하는 경우

• 백그라운드 작업
• 자료를 업로딩하는 것
• 프린트 대기열

파이썬에서 리스트를 이용하여 FIFO 성질인 queue를 구현하는 두 가지 방법이 있다. 첫 번째는 리스트에 뒤로 쌓은 다음에 앞부터 지우는 것이고, 두 번째는 리스트에 앞으로 쌓은 다음에 뒤부터 지우는 것이다.

# 배열을 이용해 Queue 만들기_FIFO 확인용 ver.1
q = []
q.append("FIRST")
q.append("SECOND")
q.append("THIRD")
print(q)

print(q.pop(0))
print(q.pop(0))
print(q.pop(0))

print(q)

# 배열을 이용해 Queue 만들기_FIFO 확인용 ver.2
q = []
q.insert(0, "FIRST")
q.insert(0, "SECOND")
q.insert(0, "THIRD")
print(q)

print(q.pop())
print(q.pop())
print(q.pop())
print(q)

 

class 소개

• 연결리스트에서 활용한 Node를 이용해서 값끼리 연결하며, first와 last라는 포인터 변수와 size라는 크기를 나타내는 변수를 constructor 함수에서 정의한다.
• 초기에는 포인터는 None으로 size는 0으로 정의한다.

enqueue method 소개

• 값 하나를 입력하는 함수로, 그 값을 갖고 새로운 노드를 만든다.
• 만약 queue에 노드가 하나도 없을 경우, 입력값을 first이자 last가 되도록 설정한다.
• 만약 queue에 노드가 하나라도 있을 경우, 현재 last 값을 변수에 저장해두고, 새로운 값을 last로 지정한다.
• 새롭게 생성된 노드와 원래 last를 이어준다.
• stack의 크기를 하나 늘리고, 그 값을 반환한다.

dequeque method 소개

• 만약 queue에 노드가 없다면 Null을 반환한다.
• 현재 first 값을 저장할 임시 변수를 만든다.
• 만약 노드가 1개 남았다면, first와 last를 Null로 설정한다.
• 만약 노드가 1개 이상 존재한다면, first 노드를 원래 first의 다음 노드로 설정한다.
• queue 크기를 하나 줄인다.
• 제거된 노드의 값을 반환한다.

 

method 구현

# Node 활용
class Node():
    # constructor
    def __init__(self, val):
        self.val = val
        self.next = None
        
# queue 활용
class Queue():
    # constructor
    def __init__(self):
        self.first = None
        self.last = None
        self.size = 0

    # instance method
    def enqueue(self, val):
        newNode = Node(val)

        if self.first == None:
            self.first = newNode
            self.last = newNode
        else:
            self.last.next = newNode
            self.last = newNode

        self.size += 1

        return self.size

    # instance method
    def dequeue(self):
        
        if self.first is None:
            return None

        tmp = self.first
        if self.first == self.last:
            self.last = None

        self.first = self.first.next

        self.size -= 1

        return tmp.val
        


# queue 선언
queue = Queue()

print('\n---enqueue fcn---')
# enqueue 수행
num = 3
print('num: ', num)
print(queue.enqueue(num))
print('last: ', queue.last.val)
print('\n')
num = 5
print('num: ', num)
print(queue.enqueue(num))
print('last: ', queue.last.val)
print('\n')
num = 1
print('num: ', num)
print(queue.enqueue(num))
print('last: ', queue.last.val)
print('\n')
num = 0
print('num: ', num)
print(queue.enqueue(num))
print('last: ', queue.last.val)
print('\n')

print('\n---dequeue fcn---')
# dequeue 수행
print(queue.dequeue())
print('first: ', queue.first.val, 'size: ', queue.size)
print('\n')
print(queue.dequeue())
print('first: ', queue.first.val, 'size: ', queue.size)
print('\n')
print(queue.dequeue())
print('first: ', queue.first.val, 'size: ', queue.size)
print('\n')
print(queue.dequeue())
print('first: ', queue.first, 'size: ', queue.size)
print('\n')
print(queue.dequeue())
print('first: ', queue.first, 'size: ', queue.size)
print('\n')

 

큐: 빅오 복잡도

• Insertion: O(1)
• Removal: O(1)
• Searching: O(N)
• Access: O(N)