스택(STACK)과 큐(QUEUE)

내가 아는 것과 구현 할 수 있는 것은 다른 문제이다.

스택과 큐는 프로그래밍이라는 개념이 탄생할 때부터 사용된 가장 고전적인 자료구조 중 하나다.

그중 스택은 거의 모든 애플리케이션을 만들 때 사용되는 자료구조이다!

스택: LIFO(후입선출)

큐: FIFO(선입선출)

파이썬은 스택 자료형을 별도로 제공하지 않는다. 대신 리스트가 스택과 큐의 모든 연산을 지원한다

다만, 큐의 연산을 수행하기에는 효율적이지 않기 때문에, 데크(Deque)라는 별도의 자료형을 사용해야 좋은 성능을 낼 수 있다

• 연결 리스트를 이용한 스택 ADT 구현

# Node와 Stack이 필요하다
class Node:
    # Node는 두 가지로 구성이 된다. 내가 가지고 있는 값(item)과 가리키고 있는 값(next)
    def __init__(self, item, next):
        # 나의 item은 item 이다
        self.item = item
        self.next = next

class Stack:
    def __init__(self):
        # Stack을 처음 만들었을 때는 top이 None 이다.
        self.top = None

    # push, pop, is_emtpy 3개가 존재해야한다.

    # 비었는지 안 비었는지 어떻게 알까?
    def is_emtpy(self):
        # 이 녀석의 top이 none인지 아닌지 보면 된다. bool 값
        return self.top is None

    # 밀어 넣을 때는 어떻게 할까?
    def push(self, val):
        # 기존의 top이  지정 대상이다(self.top)
        self.top = Node(val, self.top)

    # 값을 꺼낼때
    def pop(self):
        # 비어있는지 안 비었는지에 따라 다르다
        # 오류를 방지 위해 if not이 필요하다
        if not self.top:
            return None
        # 비어있지 않다면 top을 node로 꺼내준다
        node = self.top
        # 새로운 top을 기존 아래에 있는 것으로 지정을 해준다
        self.top = self.top.next

        return node.item

• 연결 리스트를 이용한 큐 ADT 구현

# 우리가 필요한 것 Node, Queue
class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next


class Queue:
    def __init__(self):
        # queue를 만들때는 앞에 있는 녀석을 지정해주는 것이 중요하다
        self.front = None

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

    def push(self, value):
        # 비어있는지 안 비어있는지 확인 먼저 해야한다
        if not self.front:
            self.front = Node(value, None)
            return

        # 안 비었다면 -> 끝까지 가야한다
        node = self.front
        # 다음이 존재하는 한 계속 간다
        while node.next:
            node = node.next

        # 끝에 도달한 상태이다
        node.next = Node(value, None)

    def pop(self):
        # 비어있는지 확인 먼저!
        if not self.front:
            return None
        # 제일 앞에 있는 녀석을 꺼내서
        node = self.front
        # front를 바꿔주기 위해 기존의 다음 node를 front로 지정한다
        self.front = self.next
        # node의 item을 꺼내준다
        return node.item