스택/큐

스택(Stack)

• 가장 처음에 들어간 요소가 가장 나중에 나오는 자료구조
• Last In First Out - LIFO라고 부른다!
• 시간 복잡도
  • 삽입: O(1)
  • 삭제: O(1)

 

• 파이썬에선 사실 스택을 사용할 때, 그냥 list를 사용하면 된다 하지만 큐는 다르다!!!
• 왜 둘다 linked list를 기반으로 한 자료구조인데 차이가 날까?
• 파이썬의 list는 사실 array이고 스택을 사용하려면 맨 뒤의 요소를 pop()해도 시간 복잡도는 똑같지만 큐 같은 경우는 맨 앞의 요소를 빼기 위해 pop(0)을 해야하는데 array에서 맨 앞의 요소를 빼는 것은 O(n)의 시간이 걸리기 때문이다!!

# 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조
class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next


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

    # 기존의 top과 자리를 바꿔줌!
    # O(1)
    def push(self, item):
        self.top = Node(item, self.top)

    # 0(1)
    def pop(self):
        if not self.top:
            return None
        top_node = self.top
        self.top = self.top.next
        return top_node.item

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

---

큐(queue)

• 가장 처음에 들어간 요소가 가장 마지막에 나가는 자료구조
• First In First Out - FIFO라고 부른다!
• 연산
  • 삽입: O(n)
  • 삭제: O(1)

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

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

    # O(n)
    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)

    # O(1)
    def pop(self):
        if not self.front:
            return None

        node = self.front
        self.front = self.front.next
        return node.item

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