23.01.17 Stack, Queue, Tree, Graph

Stack

데이터를 순차적으로 저장하고, 저장한 순서의 마지막부터 출력하는 자료구조

 

특징

// a,b,c,d를 스택에 push하고 3번 pop하기

//Integer형 스택 선언
Stack<Integer> stack = new Stack<>(); 

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
---------------------------
a <- b <- c <- d
---------------------------
들어간 순서대로 a,b,c,d가 저장됨


stack.pop();
stack.pop();
stack.pop();
---------------------------
a
---------------------------
d, c, b
마지막에 들어온 데이터부터 출력

입력과 출력이 한 방향에서 이루어져서 First In Last Out 구조를 가지고 있다.

 

메서드

• push(): 스택에 데이터 추가
• pop(): 가장 나중에 추가된 데이터를 리턴하고 삭제
• size(): 데이터 크기 리턴
• peek(): 가장 나중에 추가된 데이터 리턴
• show(): 스택의 모든 데이터를 String 타입으로 변환하여 리턴
• clear(): 모든 데이터 삭제

 

Queue

데이터를 순차적으로 저장하고, 저장한 순서대로 출력하는 자료구조

 

메서드

• add(): 큐에 데이터 추가
• poll(): 가장 먼저 추가된 데이터를 리턴하고 삭제
• size(): 데이터 크기 리턴
• peek(): 가장 먼저 추가된 데이터 리턴
• show(): 큐의 모든 데이터를 String 타입으로 변환하여 리턴
• clear(): 모든 데이터 삭제

Graph

여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조

 

각종 용어들

• 정점 (vertex), 노드(node): 그래프의 기본 원소
• 간선 (edge): vertex를 이어주는 선. 노드간의 관계
• 인접 정점 (adjacent vertex): edge에 직접적으로 연결되어 있는 vertex
• 가중치 그래프 (weighted Graph): 연결 강도가 표현되어 있는 그래프
• 비가중치 그래프 (unweighted Graph): 연결 강도가 없는 그래프
• 무(방)향 그래프 (undirected graph): 각 노드에서 상호 방향으로 이동 가능한 그래프
• 단방향 그래프(directed): 일방통행 그래프
• 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 들어오는 간선과 나가는 간선의 갯수
• 자기 루프 (self loop): 정점에서 진출하는 간선이 다른 정점을 거치지 않고 자기 자신에게 진입하는 경우 
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있는 그래프

메서드

• setGraph(size): 그래프에 size만큼의 버텍스 추가
• getGraph(): 인접 행렬 정보가 담긴 배열 반환
• addEdge(from, to): fromVertex와 toVertex 사이의 간선 추가
• hasEdge(from, to): fromVertex와 toVertex 사이의 간선 여부를 Boolean형태로 리턴
• removeEdge(from, to): fromVertex와 toVertex 사이의 간선 삭제

Tree

단방향 그래프의 한 구조

 

각종 용어들

• 루트(Root): 트리 구조의 시작점이 되는 노드
• 리프(Leaf): 트리 구조의 끝지점. 자식 노드 없음
• 깊이(depth): 루트로부터 하위 계층의 특정 노드까지의 깊이
• 레벨(Level): 같은 깊이를 가지고 있는 노드
• 높이(hight): 리프 노드를 기준으로 루트까지의 높이
• 서브트리(Sub tree): 트리 내부에 트리 구조를 갖춘 것

메서드

• addChildNode(value): value를 Tree에 계층적으로 추가
• removeChildNode(node):  node를 Tree에서 삭제
• getChildrenNode(): 현재 트리의 children 리턴
• contains(value): 트리에 포함된 데이터 검색해서 boolean형으로 리턴