[JAVA] Stack과 Queue

 

📌 Stack

삽입과 삭제 연산이 후입선출(LIFO)로 이루어지는 자료구조

➡️ 삽입과 삭제 연산이 한 쪽에서만 일어남

❗️ DFS(Depth First Search) 깊이 우선 탐색, 백트래킹에서 주로 사용됨!

❓ 후입선출이란? 

- 가장 마지막에 넣었던 값을 먼저 빼내는 방식

- ex. 웹브라우저 방문 기록 (이전으로 누르면 바로 직전의 창으로 돌아감)

 

 

✔️ 스택 용어

 

• 위치
  • top : 삽입과 삭제가 일어나는 위치
• 연산
  • push : top에 새로운 데이터를 삽입하는 연산
  • pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
  • peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산

 

 

📌 Queue

삽입과 삭제 연산이 선입선출(FIFO)로 이루어지는 자료구조

➡️ 삽입과 삭제 연산이 양 방향에서 일어남

❗️ BFS(Breadth First Search) 너비 우선 탐색에서 주로 사용!!

❓ 선입선출이란? 

- 가장 먼저 넣었던 값을 먼저 빼내는 방식

- ex. 편의점 재고 정리

 

✔️ 큐 용어

• rear : 큐에서 가장 끝 데이터를 가리키는 영역
• front : 큐에서 가장 앞의 데이터를 가리키는 영역
• add : rear 부분에 새로운 데이터를 삽입하는 연산
• poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산
• peek : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산

 

 

📌 우선순위 큐  (Priority queue)

일반적인 큐의 구조FIFO를 가지지만, 값이 들어간 순서와 상관 없이 우선 순위가 높은 데이터가 먼저 나오는 자료구조

 

큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치함

 ➡️ 일반적으로 힙(heap)을 이용해서 구현

 

❓ Heap이란?

- 완전 이진 트리 구조

- 이진 힙(binary heap)이라고도 하고, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기본으로 한 자료구조

- 부모 노드의 키 값과 자식 노드의 키 값 사이에는 대소 관계가 성립함

➡️ 키 값 대소 관계에는 오로지 부모 자식 간에만 성립되며 형제 노드 사이에는 대소 관계가 성립되지 않음