[알고리즘] 자료구조 (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