스택, 유서깊은 자료형을 찾아서
스택은 프로그래밍이라는 개념이 탄생할 때부터 사용된 가장 고전적인 자료구조로, 현재에도 대부분의 앱에서 활용되는 자료구조입니다.
고전적인 자료구조, 즉 초기부터 활용될 수 있었던 이유는 특유의 직관성 때문으로 보입니다. 입구와 출구가 같은 용기나 저장소에 무언가를 안쪽부터 채워서 담았다가, 입구쪽부터 하나씩 꺼내 쓰는 형태니까요.
현재까지 대부분의 앱에서 사용된다는 것은, 현대의 문제풀이 방식과도 어울리면서 다른 자료구조형보다 효율적이라는 의미로 보입니다.
스택의 구조와 기능
스택의 구조는 그림과 같이, 한쪽 면이 막힌(조회시 None을 출력하는) 구조로 이루어졌습니다. 스택에는 필수적으로 요소를 넣는 push, 요소를 빼내는 pop, 내용물의 유무를 확인하는 is_empty의 기능이 필요합니다.
해당 자료구조를 파이썬으로 작성해보면 다음과 같습니다.
1. 클래스 Node 생성
#클래스 Node 생성
class Node:
# 초기화 함수를 통해 Node의 초기데이터값 설정
def __init__(self, val, next):
# (노드이름).val로 접근하면 저장된 val값을 호출
self.val = val
# (노드이름).next로 접근하면 저장된 next(노드)를 호출
self.next = next
노드를 선언하는 이유는 Single Linked List의 형태로 작성하여,함수가 요소간과 요소-스택의 상태를 활용하도록 하기 위함입니다.
2. 클래스 Stack 생성
class Stack:
# 초기화(__init__)메소드를 통해 Stack의 데이터값 초기화
def __init__(self):
# (스택이름).top을 None으로 초기화.
self.top = None스택의 초기 self.top 값을 None으로 선언하여 자료구조를 생성했습니다.
3. 클래스 안에 함수 선언 - 1 : push
def push(self, val):
# self.top 값을 새로 넣은 Node값으로 초기화합니다. next는 직전 self.top을 가리킵니다.
self.top = Node(val, self.top)푸쉬 함수입니다. 새로운 값(val)을 인자로 받으면, Node 클래스로 받아서 저장합니다.
그때 노드가 가리키는 값은 가장 최근에 들어온 노드입니다.(혹은 들어온 노드가 없는 경우, None을 가리킵니다. 이를 통해 한쪽이 막힌 형태의 자료형을 구현했습니다.)
4. 클래스 안에 함수 선언 - 2 : pop
def pop(self):
# 예외처리입니다. 스택 안에 값이 없으면 함수는 아무것도 반환하지 않습니다.
if self.top is None:
return None
# topNode 변수에 현재 top값을 저장합니다.
topNode = self.top
# self.top값을 기존 top이 가리키는 값으로 갱신합니다.
self.top = self.top.next
# 저장된 기존 top값을 반환합니다.
return topNode스택 안에 아무 값이 없으면 pop()함수는 아무것도 반환하지 않습니다.
값이 있으면, 가장 나중에 저장된 값(self.top)을 반환하고, self.top값을 갱신합니다.
5. 클래스 안에 함수 선언 - 3 : is_empty
def is_empty(self):
# self.top이 특정 값을 담고 있지 않다면 True를 반환합니다.
return self.top is None스택의 특징
-
후입선출(LIFO) : pop으로 요소를 꺼내면 먼저 들어온 값이 가장 나중에 반환되고, 나중에 들어온 값이 먼저 반환됩니다.
-
시간복잡도
- Insertion O(1)
- Deletion O(1)
- Search O(n)
삭제나 삽입시 맨 위에 데이터를 삽입하거나 삭제하기 때문에 시간복잡도는 늘 O(1) 의 시간복잡도를 가집니다. 하지만 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도를 가집니다.
마무리
베인 3타 터지기 전에, 밀린 TIL stack 바로바로 pop하자
