[알고리즘] 자료구조 (stack, queue, deque), Tree 정리
자료구조 (stack, queue, deque)
Stack
LIFO(Last In First Out) / FILO(First In Last Out)
한 쪽만 뚫여있는 구조
pop() : 스택에서 가장 위에 있는 항목을 제거
push(Item) : Item 하나를 스택의 가장 윗 부분에 추가
peek () : 스택의 가장 위에 있는 항목을 반환
isEmpty() : 스택이 비어 있을 때 true를 반환
IsFul() : 스택이 가능 가 있는지 확인
getSize() : 스택에 있는 요소 수를 변환
사용 용어 : top, bottom, push, pop
Queue
FIFO(First In First Out)
양쪽이 뚫려있는 구조 - 한쪽은 데이터 삽입 한쪽은 데이터 추출만 진행
enQueue() : 큐에 끝 (rear)에 항목 추가, 데이터 삽입
deQueue() : 큐에 맨 앞 (front)에 있는 항목을 제거
peek() : 큐에 맨 앞에 있는 항목을 반환
isfull() : 큐에 가득 찼는지 확인
isempty() : 큐가 비어 있는 확인
사용 용어 : front, rear, enQueue, deQueue
원형 큐, 이중 큐
Deque
Double Ended Queue
큐의 앞과 뒤 모두에서 삽입 및 삭제가 가능한 큐
Tree 트리의 구조
전위 순회 (preorder)
뿌리를 먼저 방문 : 뿌리 → 왼쪽 자식 → 오른쪽 자식 순
def preorder(self, n):
if n!= None:
print(n.item, '', end='') # 노드 방문
if n.left:
self.preodrer(n.left) # 왼쪽 서브 트리 순회
if n.right:
self.preodrer(n.right) # 오른쪽 서브 트리 순회
def preorder(self):
def _preorder(node):
print(node.item, end=' ')
if node.left:
_preorder(node.left)
if node.right:
_preorder(node.right)
_preorder(self.root)
OUTPUT 1→2 →4 →8 →5 →3 →6 →7
중위 순회 (inorder)
왼쪽 하위 트리를 방문 하고 뿌리 방문 : 왼쪽 자식 → 뿌리 → 오른쪽 자식
def inorder(self, n):
if n!= None:
if n.left:
self.inorder(n.left)
print(n.item, '', end='') # 노드 방문
if n.right:
self.inorder(n.right)
def inorder(self):
def _inorder(node):
if node.left:
_inorder(node.left)
print(node.item, end=' ')
if node.right:
_inorder(node.right)
_inorder(self.root)
OUTPUT 8 →4 →2 →5 →1 →6 →3 →7
후휘 순회 (postorder)
하위 트리 먼자 방문 후 뿌리 : 왼쪽자식 → 오른쪽 자식 → 뿌리
def postorder(self, n):
if n!= None:
if n.left:
self.postorder(n.left)
if n.right:
self.postorder(n.right)
print(n.item, '', end='') # 노드 방문
def postorder(self):
def _postorder(node):
if node.left:
_postorder(node.left)
if node.right:
_postorder(node.right)
print(node.item, end=' ')
_postorder(self.root)
OUTPUT 8 →4 →5 →2 →6 →7 →3 →1