1. 스택: Stack
•
스택 : 데이터를 후입선출(LIFO, Last-In-First-Out) 순으로 관리하는 선형 자료구조
•
스택 문제를 Python으로 구현하면 deque나 list로 쉽게 구현할 수 있다.
1-1. 구현: 파이썬 내장 자료구조를 활용한 구현
# deque 구현
from collections import deque
stack = deque()
# 원소 추가
stack.append(1)
stack.append(2)
stack.append(3)
# 스택 출력
print("스택:", stack)
# 맨 위(뒤) 원소 제거
popped_element = stack.pop()
print("pop된 원소: ", popped_element)
print("제거 후 스택: ", stack)
# 맨 위(뒤) 원소 확인
top_element = stack[-1]
print("맨 위(뒤)의 원소: ", top_element)
print("현재 스택: ", stack)
# 스택의 크기 확인
print("스택의 크기: ", len(stack))
# 스택이 비어 있는지 확인
print("스택이 비어 있는지 확인: ", not stack)
# 스택 순회
while stack:
print(stack.pop(), end=' ')
Python
복사
1-2. 구현: 연결리스트를 활용한 구현
•
스택을 파이썬에서 미리 구현되어 있는 자료구조로 구현하는 것이 아니라 내가 정의한 class로 구현할 수도 있다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class ImplementedStack:
def __init__(self):
self.top = None
def push(self, data):
if self.top is None:
self.top = Node(data)
else:
node = Node(data)
node.next = self.top
self.top = node
def pop(self):
if self.top is None:
return None
node = self.top
self.top = self.top.next
return node.data
def peek(self):
if self.top is None:
return None
return self.top.data
def is_emppty(self):
return self.top is None
Python
복사
1-3. 시간 복잡도
•
스택 각 연산의 시간 복잡도
◦
push
▪
시간 복잡도 :
◦
pop
▪
시간 복잡도 :
◦
맨 위 원소 확인
▪
시간 복잡도 :
◦
스택의 크기 확인
▪
시간 복잡도 :
◦
스택이 비어 있는지 확인
▪
not stack or len(stack) == 0
▪
시간 복잡도:
◦
순회, 특정 값의 존재 여부 확인
▪
시간 복잡도:
2. 큐: Queue
•
큐 : 데이터를 선입선출(FIFo, First-In-First-Out) 순으로 관리하는 선형 자료 구조
•
큐 문제를 Python으로 구현하면 deque로 쉽게 구현할 수 있다.
2-1. 구현: 파이썬 내장 자료구조를 활용한 구현
from collections import deque
queue = deque()
# 맨 뒤에 원소 삽입
queue.append(1)
queue.append(2)
queue.append(3)
# 큐 출력
print("큐: ", queue)
# 맨 앞의 원소 삭제
popped_element = queue.popleft()
print("삭제된 원소: ", popped_element)
# 맨 앞의 원소 확인
front_element = queue[0]
print("맨 앞의 원소: ", front_element)
# 큐의 크기 확인
print(len(queue))
# 큐가 비어 있는지 확인
print("큐가 비어 있는지 확인: ", not stack)
# 큐 순회
while queue:
print(queue.pop(), end=' ')
Python
복사
2-2. 구현: 연결리스트를 활용한 구현
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
def enqueue(self, data):
if self.front is None:
self.front = self.rear = Node(data)
else:
node = Node(data)
self.rear.next = node
self.rear = node
def dequeue(self):
if self.front is None:
return None
node = self.front
if self.front == self.rear:
self.front = self.rear = None
else:
self.front = self.front.next
return node.data
def is_empty(self):
return self.front is None
Python
복사
1-3. 시간 복잡도
•
큐 각 연산의 시간 복잡도
◦
enqueue
▪
시간 복잡도 :
◦
dequeue
▪
시간 복잡도 :
◦
맨 위 원소 확인
▪
시간 복잡도 :
◦
큐의 크기 확인
▪
시간 복잡도 :
◦
큐가 비어 있는지 확인
▪
not stack or len(stack) == 0
▪
시간 복잡도:
◦
순회, 특정 값의 존재 여부 확인
▪
값 in queue
▪
시간 복잡도: