스택과 큐

스택과 큐는 리스트에서 조금 더 발전한 형태의 자료구조.

둘의 구조는 비슷하지만 처리 방식은 다르다.

스택과 큐의 핵심 이론

---

스택

• 삽입과 삭제 연산이 후입선출(LIFO : Last-in First-out)의 구조로 이루어지는 자료구조.

💡 스택 용어

위치

• top : 삽입과 삭제가 일어나는 위치

연산

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

---

• 스택은 깊이 우선 탐색(DFS : Depth First Search), 백트래킹 종류의 코딩 테스트에 효과적
  • DFS는 재귀함수로 많이 구현하긴 함
• 후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하기 때문

---

큐

• 큐는 삽입과 삭제 연산이 선입선출(FIFO : First-in First-out)로 이뤄지는 자료구조

💡 큐 용어

위치

• back : 큐에서 가장 끝 데이터를 가리키는 영역
• front : 큐에서 가장 앞의 데이터를 가리키는 영역

연산

• push : back 부분에 새로운 데이터를 삽입하는 연산
• pop : front 부분에 있는 데이터를 삭제하고 확인하는 연산

---

• 큐는 너비 우선 탐색(BFS : Breadth First Search)에서 자주 사용

---

출처 - 하루코딩