스택과 큐는 배열에서 발전된 형태의 자료구조.

비슷하지만 처리 방식이 다름.

스택

스택 = 삽입과 삭제 연산이 후입선출 LIFO (Last in First out) 마지막으로 들어온 아이가 제일 먼저 나감

• 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있음
• 스택에서 값을 빼낼 때, pop은 top이 가리키는 값을 스택에서 뺌
• 새 스택이 들어가면 top이 됨
  • top: 삽입과 삭제가 일어나는 위치
  • push: top위치에 새로운 데이터 삽입
  • pop: top위치에 현재 있는 데이터를 삭제하고 확인
  • peek: top위치에 현재 있는 데이터를 단순 확인
• 깊이 우선 탐색 DFS, 백트래킹 종류에 효과적으로 사용됨
• 재귀 함수 알고리즘 원리와 일맥상통하는 후입선출 개념을 잘 기억할 것
• 코딩 테스트에서는 스택 응용 문제가 많이 출제 되니.. 제대로 이해 할 것

큐

큐 = 삽입과 삭제 연산이 선입선출 FIFO (First in First out) 먼저 들어온 데이터가 먼저 나감

• 새 값 추가는 큐의 rear에서 삭제는 큐의 front에서 이루어짐
• 삽입과 삭제가 양방향에서 이루어짐
  • rear: 큐에서 가장 끝 데이터를 가리키는 영역
  • front: 큐에서 가장 앞의 데이터를 가리키는 영역
  • add: rear부분에 새로운 데이터를 삽입
  • poll: front부분에 있는 데이터를 삭제하고 확인
  • peek: 큐의 맨 앞 front에 있는 데이터를 확인할 때 사용
• 너비 우선 탐색 BFS에서 자주 사용
• 우선순위 큐 = 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조 → front는 항상 최댓값 또는 최솟값이 위치하며, 일반적으로 heap을 이용해 구현하므로 개념만 알고 있을 것!