def) 스택 (Stack): 먼저 들어온 데이터가 나중에 나가는 자료구조 게임을 즐겨 하신 분들은 스택이라는 용어에 익숙하실지도 모르겠습니다. 공식 번역 등에서는 '중첩'이라고도 하는 스택을 쌓으면 능력치가 오르는 몇몇 스킬, 아이템들이 있죠.롤에서 볼 수 있는 메자이라든가 이와 비슷하게 상자를 쌓아올리듯이 데이터를 쌓는 자료구조를 스택(stack)이라고 합니다. 스택 자료구조의 특징으로는 먼저 들어온 데이터가 나중에 나간다는 점입니다. 우리가 박스를 쌓은 뒤에 꺼낼 때는, 가장 마지막에 올렸던 박스부터 꺼내고 그 위의 있는 다른 박스들까지 다 꺼내고 나서야 처음 쌓은 박스를 꺼낼 수 있죠. 반대로 가장 마지막에 들어온 데이터/박스가 가장 먼저 나갑니다.
스택 예제
스택에 여러 개의 데이터를 삽입하고 삭제하는 예시를 확인해보겠습니다. 전체 연산은 아래와 같다고 해보겠습니다. 아래 그림들은 전체 연산의 순서대로 스택의 데이터를 표현한 것입니다. 앞서 말한대로 나중에 들어온 원소가 가장 먼저 삭제되는 것을 알 수 있습니다.
스택은 ML 뿐만 아니라 다양한 프로그램 개발에 있어서 가장 기본적이고 기초적인 자료구조이기 때문에 그 작동 방식을 잘 알아둘 필요가 있습니다.
스택의 시간복잡도
저번 포스트에서 파이썬 리스트를 설명하며 시간 복잡도를 이야기할 때, 일부 함수가 스택 자료구조에서 사용된다는 것을 표에서만 간단하게 짚고 넘어갔는데요. 이번에는 스택에서 제공하는 여러 연산을 비교하며 시간복잡도를 알아보겠습니다.
연산
시간복잡도
설명
1
삽입(Push)
$O\left(1\right)$
스택에 원소를 삽입
2
추출(Pop)
$O\left(1\right)$
스택에서 원소 추출
3
최상위 원소(Top)
$O\left(1\right)$
스택의 최상위 원소, 즉 마지막에 들어온 원소를 확인
4
Empty
$O\left(1\right)$
스택이 비어 있는지 확인
파이썬에서 스택 구현하기 - 리스트 자료형
그럼 다시 한 번 파이썬의 리스트 자료형으로 돌아와서, 스택 자료구조가 어떻게 작동하는지 알아보겠습니다. 파이썬의 리스트 자료형과 관련된 함수 중에서 append()와 pop() 메서드 기억하시나요? 이 두 메서드는 각각 리스트의 마지막 위치에 원소를 삽입, 마지막 위치로부터 원소를 추출하는 메서드이고, 시간복잡도는 $O\left(1\right)$로 동일합니다. 이 두 메서드를 조합하면 파이썬에서 스택을 구현할 수 있습니다.
class Stack:
def __init__(self):
self.stack = []
def push(self, data):
# Append an element at tail
self.stack.append(data)
def pop(self):
if self.is_empty():
return None
# Extract the element at tail
return self.stack.pop()
def top(self):
if self.is_empty():
return None
# Return the element at tail
return self.stack[-1]
def is_empty(self):
return len(self.stack) == 0
stack = Stack()
arr = [9, 7, 2, 5, 6, 4, 2]
for x in arr:
stack.push(x)
while not stack.is_empty():
print(stack.pop())
연결 리스트로 스택 구현하기
연결 리스트와 관련된 테크닉 중 하나로 스택을 연결 리스트로 구현하는 방식이 있습니다. 이럴 경우 삽입과 삭제를 할 때 $O\left(1\right)$의 시간복잡도를 보장할 수 있다는 장점이 있습니다. 왜 그런지를 알아보기에 앞서, 먼저 머리(head)라는 위치에 대해 정의해보겠습니다.
def) 머리 (Head): 남아있는 원소 중 가장 마지막에 들어온 데이터를 가리키는 포인터
스택을 연결 리스트로 구현할 때는 바로 이 머리를 가리키는 하나의 포인터만 가지면 됩니다. 그렇게 되면 머리에 해당하는 데이터부터는 자신의 포인터로 다음 데이터를 가리키면서 우리가 알고 있는 연결 리스트가 구현되어 있기 때문입니다.
삽입 연산
삽입과 삭제 연산 예시를 보면서 작동 방식을 알아보겠습니다. 먼저 삽입 연산입니다. 삽입할 때는 머리 위치에 데이터를 넣기만 하면 됩니다.
삽입 연산 수행 전.삽입 연산 후.
삭제 연산
반대로 삭제할 때는 머리(head) 위치에서 데이터를 꺼내주면 됩니다. 이 때, 머리를 맨 앞 원소가 아닌 그 뒤의 원소라 바꿔주는 것만으로도 간단하게 삭제가 이뤄집니다.
ㅅ
파이썬에서의 구현
연결 리스트 때와 마찬가지로 파이썬에서 스택을 클래스 형태로 구현해보겠습니다. 강의에서 제공한 아래의 예제 코드를 참고해주세요.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
# Data insertion
def push(self, data):
node = Node(data)
node.next = self.head
self.head = node
# Data extraction
def pop(self):
if self.is_empty():
return None
# Extract a node from head
data = self.head.data
self.head = self.head.next
return data
# The highest rank element (top)
def top(self):
if self.is_empty():
return None
return self.head.data
# Print elements in a row
def show(self):
cur = self.head
while cur:
print(cur.data, end = " ")
cur = cur.next
# Find out if the stack is empty
def is_empty(self):
return self.head is None
stack = Stack()
arr = [9, 7, 2, 5, 6, 4, 2]
for x in arr:
stack.push(x)
stack.show()
print()
while not stack.is_empty():
print(stack.pop())
22일차 후기
정신차려보니 3주차 미션도 끝나있고 벌써 4주차가 시작되었습니다. 뭐야 내 한 달 어디갔어 돌려줘요.
