728x90
반응형
본 포스트는 필자가 학습하고 작성한 글이기 때문에 틀린 내용이 있을 수 있습니다.
1. 스택 (Stack) 개요
데이터를 저장하는 기본적인 자료 구조 중 하나로, 선입후출(LIFO: Last In, First Out)의 특성을 가진다.
즉, 마지막에 추가된 항목이 가장 먼저 제거된다.
1.1. 장점
- 구현이 간단하다.
- 데이터의 추가와 삭제의 시간 복잡도가 O(1)이다.
1.2. 단점
- 스택의 크기가 고정된 경우, 스택 오버플로우(스택이 가득 참)나 스택 언더플로우(스택이 비어 있음)가 발생할 수 있다.
- 스택의 중간 데이터에 접근하기 어렵다.
1.3. 주요 연산
- push : 스택의 맨 위에 새로운 항목을 추가합니다.
- pop : 스택의 맨 위 항목을 제거하고 반환합니다.
- peek or top : 스택의 맨 위 항목을 확인하되 제거하진 않습니다.
- is_empty : 스택이 비어있으면 True, 아니라면 False를 반환합니다.
- get_size : 스택의 크기(항목의 수)를 반환합니다.
1.3.1. 시간 복잡도
- push : O(1)
- pop : O(1)
- peek : O(1)
1.3.2. 공간 복잡도
- 모든 경우 : O(n)
2. 구현
스택의 구현은 Array(python에서의 list)나 Linked List로 할 수 있다.
2.1. 리스트 기반 스택
<python />
class Stack:
def __init__(self):
self.items = []
def push(self, item):
"""top에 item 추가"""
self.items.append(item)
def pop(self):
"""top item을 제거하고 리턴"""
if not self.is_empty():
return self.items.pop()
def peek(self):
"""top item을 제거하지 않고 리턴"""
if not self.is_empty():
return self.items[-1]
def is_empty(self):
"""stack이 비어있는지 확인"""
return len(self.items) == 0
def get_size(self):
"""스택의 길이를 리턴"""
return len(self.items)
2.2. 연결 리스트 기반 스택
<python />
class StackNode:
def __init__(self, data):
self.data = data
self.next = None
class StackUsingLinkedList:
def __init__(self):
self.top = None
self.no = None
def push(self, data):
"""top에 item 추가"""
new_node = StackNode(data)
if self.top is None:
self.top = new_node
return
new_node.next = self.top
self.top = new_node
self.no += 1
def pop(self):
"""top item을 제거하고 리턴"""
if self.is_empty():
return None
popped_node = self.top
self.top = self.top.next
popped_node.next = None
self.no -= 1
return popped_node.data
def peek(self):
"""top item을 제거하지 않고 리턴"""
if self.is_empty():
return None
return self.top.data
def is_empty(self):
"""stack이 비어있는지 확인"""
return self.top is None
def get_size(self):
"""스택의 길이를 리턴"""
return self.no
728x90
반응형
