스택(Stack)

<aside> 🗒️ Sketch) 할 일을 접착식 메모지에 적기

• 메모지를 떼내서(pop), 할 일 적고 다시 포스트잇 위에 올려놓기(push)

• 푸시(push) : 가장 위에 새 항목을 추가

• 팝(pop) : 가장 위 항목을 떼어내고 읽음. </aside>

• 후입선출(LIFO, Last In First Out)

• 연산

  • push : 삽입
  • pop : 삭제

• 활용

  • 재귀 알고리즘

시간 복잡도

• 삽입 / 삭제 : $O(1)$

  $(\because)$ top에서만 가능

• 읽기 : $O(n)$

구현 코드

# stack.py

class Stack:
    def __init__(self):
        self.stack = list()
        self.size = 0

    def push(self, element):
        self.stack.append(element)
        self.size += 1

    def pop(self):
        if not self.empty():
            self.stack.pop()
            self.size -= 1

    def top(self):
        if not self.empty():
            return self.stack[self.size - 1]
        return None

    def empty(self):
        return self.size == 0

• 테스트 및 실행 결과

큐(Queue)

<aside> 🚏 대기열

ex. 버스 정류장 - 먼저 줄 선 사람이 먼저 버스에 탐

</aside>