백준
스택 :
큐 : 1158(완) ,13335(풀고싶따ㅠㅠ)
덱 : 2346

큐(Queue)

: 한쪽으로데이터가들어오고반대쪽으로빠져나가는FIFO(First In First Out) 형식의자료구조
먼저들어온데이터가먼저나감

• offer(x): 데이터 x를 큐의 맨 뒤에 추가 (성공하면 true 반환, 실패 시 false 반환)
• poll(): 큐의 맨 앞 데이터를 제거하고 반환 (비어있으면 null 반환)
• peek(): 큐의 맨 앞 데이터(front)를 제거하지 않고 반환 (비어있으면 null 반환)
• isEmpty(): 큐가 비어 있는지 확인
• size(): 큐의 현재 크기를 반환
• clear(): 큐를 비움

덱(Deque)

: 양쪽 끝에서 삽입과 삭제를 허용하는 자료구조

• 배열 기반 덱: 고정된 크기의 배열을 사용하여 덱을 구현하며, 순환 배열을 사용하여 양쪽 끝에서의 삽입과 삭제를 효율적으로 처리
• 연결 리스트 기반 덱: 이중 연결 리스트를 사용하여 덱을 구현하며, 노드의 추가와 삭제가 양쪽 끝에서 O(1) 시간에 이루어짐

• addFirst(x): 데이터 x를 덱의 앞쪽에 추가
• addLast(x): 데이터 x를 덱의 뒤쪽에 추가
• offerFirst(x): 데이터 x를 덱의 앞쪽에 추가 (실패 시 false 반환)
• offerLast(x): 데이터 x를 덱의 뒤쪽에 추가 (실패 시 false 반환)
• removeFirst(): 덱의 앞쪽에서 데이터를 제거하고 반환 (예외 발생 가능)
• removeLast(): 덱의 뒤쪽에서 데이터를 제거하고 반환 (예외 발생 가능)
• pollFirst(): 덱의 앞쪽에서 데이터를 제거하고 반환 (비어있으면 null 반환)
• pollLast(): 덱의 뒤쪽에서 데이터를 제거하고 반환 (비어있으면 null 반환)
• getFirst(): 덱의 앞쪽 데이터를 반환 (제거하지 않음, 예외 발생 가능)
• getLast(): 덱의 뒤쪽 데이터를 반환 (제거하지 않음, 예외 발생 가능)
• peekFirst(): 덱의 앞쪽 데이터를 반환 (제거하지 않음, 비어있으면 null 반환)
• peekLast(): 덱의 뒤쪽 데이터를 반환 (제거하지 않음, 비어있으면 null 반환)
• isEmpty(): 덱이 비어 있는지 확인
• size(): 덱의 현재 크기를 반환
• clear(): 덱을 비움

트리(Tree)

트리는 정점(node)과 간선(edge)으로 연결된 그래프의 특수한 형태이다.
부모-자식 개념을 가지는 비순환적 경로로 연결되어 있는 자료구조이다

이진트리

: 각노드가 최대2개의 자식노드를 가질때. (최대Degree = 2)
같은 루트에 같은 자식노드가 하나 연결되어 있어도 자식노드의 위치가 왼쪽과 오른쪽으로 다르다면 서로 다른 트리

트리순회(Tree Traversal)

: 트리의 모든 노드를 방문하는 과정

트리순회종류

전위순회(Preorder)
: 트리를 복사하거나, 전위표기법을 구하는데 주로 사용됨
1. Root 노드를방문
2. 왼쪽서브트리를전위순회
3. 오른쪽서브트리를전위순회

중위순회(Inorder)
: 이진 탐색트리(BST)에서 오름차순혹은 내림차순으로 값을 가져올때 주로 사용됨
1. 왼쪽서브트리를 중위순회
2. Root 노드를방문
3. 오른쪽서브트리를 중위순회

후위순회(Postorder)
: 트리를 삭제할때 주로 사용됨
1. 왼쪽서브트리를 후위순회
2. 오른쪽서브트리를 후위순회
3. Root 노드를방문

힙(Heap)

완전이진트리구조
우선순위큐를 구현하기위한 자료구조
부모노드와 자식노드 사이의 우선순위 관계만 보장하며, 왼쪽 자식과 오른쪽 자식 사이에는 특별한 순서기준이 없다
최댓값 또는 최솟값을 빠르게 찾을 수 있음

우선순위 큐란?
각 데이터에 우선순위(priority)가 부여되어, 가장 높은 우선순위(또는 가장 낮은 우선순위)의 데이터를 빠르게 찾아내고 처리할 수 있도록 하는 자료구조

• 배열 기반 힙: 고정된 크기의 배열을 사용하여 힙을 구현하며, 부모-자식 노드 간의 인덱스 관계를 이용해 데이터에 접근
• 포인터를 이용한 트리 구조(링크드 힙)로도 구현할 수 있지만 배열 기반 힙이 캐시 친화적이고, 공간 사용 면에서도 효율적이기 때문에 주로 사용됨

• insert(x): 데이터 x를 힙에 추가
• extractMin(): 힙에서 최솟값을 제거하고 반환
• extractMax(): 힙에서 최댓값을 제거하고 반환
• peek(): 힙의 최솟값 또는 최댓값을 제거하지 않고 반환
• heapify(): 배열을 힙 구조로 변환
• isEmpty(): 힙이 비어 있는지 확인
• size(): 힙의 현재 크기를 반환
• clear(): 힙을 비움

그래프(Graph)

정점(node 또는 vertex)과 간선(edge)으로 이루어진 자료구조이다.

• addNode(x): 노드 x를 그래프에 추가
• addEdge(x, y): 노드 x와 y를 연결하는 간선을 추가
• removeNode(x): 노드 x를 그래프에서 제거
• removeEdge(x, y): 노드 x와 y를 연결하는 간선을 제거
• findPath(x, y): 노드 x에서 y까지의 경로를 찾음
• traverse(): 그래프를 순회하며 데이터를 처리

• 방향 그래프: 노드 간의 관계가 방향성을 가지는 경우 사용
  • 예시: 웹 페이지 간의 하이퍼링크 (A 페이지에서 B 페이지로의 링크는 있지만, 반대는 아닐 수 있음)
• 무방향 그래프: 노드 간의 관계가 상호적인 경우 사용
  • 예시: 친구 관계를 나타내는 소셜 네트워크 (A가 B의 친구이면, B도 A의 친구)
• 가중치 그래프: 간선에 가중치(비용, 거리 등)가 있는 경우 사용
  • 예시: 도로 망에서 도시 간의 거리나 교통 비용을 나타내는 그래프 (각 도로의 거리가 가중치로 사용됨)