[자료구조] 스택 & 큐

스택과 큐는 지정된 순서대로 요소를 관리하고 조작하는 비슷하지만 다른 구조이다. 다른 부분으로 요소의 추가와 제거하는 방식의 차이가 있다.

스택

---

후입선출(LIFO / Last-In-First-Out): 최근 추가된 요소가 먼저 제거되고 먼저 추가된 요소가 나중에 제거된다. 이해하기 쉬운 예시로 식당에 줄을 서있는데 늦게 온 사람이 먼저 들어가는 것 이라고 생각하면 된다.

• 출입구가 하나인 박스에 요소를 쌓으며
  • push : 스택에 data 넣음.
  • pop : 스택 맨 위의 data 제거. -> 가장 마지막에 push 한 data가 가장 먼저 pop 된다.
  • peek : pop과 유사하게 맨 위의 data 반환 -> 스택에서 제거되지 않음.
  • top : 가장 마지막에 추가된 data의 위치 (가장 맨위)

큐

---

선입선출(FIFO / First-In-First-Out): 추가된 요소의 순서대로 제거 또한 먼저 추가된 요소가 먼저 제거된다. 이해하기 쉬운 예시로 일반적인 식당의 줄서기를 말할 수 있다.

• 출구와 입구가 다른 박스에 요소를 쌓으며
  • front : 큐의 맨 앞, 자료가 반환되는 곳
  • rear : 큐의 맨 뒤, 자료가 추가되는 곳
  • enqueue : 요소 삽입 함수
  • dequeue : 요소 제거 함수
  • peek : 맨 위의 data 반환 -> 제거되지 않음.
  • size : 큐가 저장할 수 있는 최대 개수 → size 넘으면 Overflow 발생

오버플로우 (Overflow)

---

• 자료가 스택 크기를 넘어 더 이상 push가 안될 때

언더플로우 (Underflow)

---

• 스택에 자료가 없어 더 이상 pop하지 못할 때 발생