240126_선형_자료구조_(Stack,Queue)

[hsilnam]

1. Stack과 Queue의 구조에 대해 설명해주세요

• 둘다 선형 자료구조의 일종 (참고: 트리는 비선형 자료구조, 계층적 관계 표현)
• Stack
  • LIFO(Last In First Out)구조를 갖는 자료구조
  • 가장 최신에 추가된 값이 가장 먼저 제거됨
  • push/pop
• Queue
  • FIFO(First In First Out)구조를 갖는 자료구조
  • 가장 오래된 데이터 값이 가장 먼저 제거됨
  • enqueue/dequeue

3. Stack과 Queue의 실사용 예를 들어 설명해주세요

• Stack: 웹 브라우저 뒤로가기, 재귀 알고리즘, DFS, 괄호 유효성 검사 등
• Queue: 대기열 관리, 작업 스케쥴링, BFS, 캐시 구현 등

4. 큐를 구현할 때 Array-Base와 List-Base의 차이가 무엇인가요

• Array-Base
  • 크기가 고정적
  • resize 할 시 오래걸림
  • Dequeue할때 O(n)이 걸림 (앞으로 땡겨야해서)
  • 데이터에 접근할 때 랜덤 엑세스로 O(1)의 시간이 걸림
• List-Base
  • 크기 유동적
  • 더 많은 메모리 사용
  • Enqueue, Dequeue할 때 O(1)이 걸려서 빠르게 수행할 수 있음
  • 데이터에 접근할 때 O(n)으로 오래걸림

5. 원형큐는 무슨 자료구조인가요?

• 원형으로 구성된 큐
• 큐의 끝에 도달하면 첫번째로 이동하여 빈공간 재활용하기 때문에, 효율적으로 활용가능
• Array-Base의 dequeue할 때 O(n)이 발생하는 것을 막기 위해서 사용. 결과적으로 O(1)이 됨

6. Queue와 Prioirity Queue의 차이는 무엇인가요?

• 둘다 FIFO의 특징을 가지고 있지만, Queue는 입력한 시간순으로, Prioirity Queue는 설정한 우선 순위에 따라 데이터를 저장합니다