💻 배열, 해시맵, 스택, 큐의 자료구조 기본 동작과 코드 구현

1. 배열 (Array)

• 정의:
  동일한 자료형의 데이터를 연속된 메모리 공간에 저장하는 자료구조
  인덱스를 사용하여 각 요소에 직접 접근 가능함

• 구조 및 특징:
  고정된 크기를 갖는 선형 구조
  인덱스를 통한 임의 접근(random access)이 가능하여 탐색이 빠름
  삽입과 삭제 시 요소 이동이 필요하여 비효율적일 수 있음

• 시간 복잡도:

  • 접근 (Access): O(1)
  • 탐색 (Search): O(n)
  • 삽입 (Insert): O(n)
  • 삭제 (Delete): O(n)

• 기본 동작:

  1. 요소 접근 → 인덱스를 통한 직접 접근
  2. 요소 탐색 → 전체 순회 후 값 비교
  3. 삽입 → 삽입 위치 이후 요소들을 한 칸 뒤로 이동
  4. 삭제 → 삭제 위치 이후 요소들을 한 칸 앞으로 이동

• 예시 코드 (Python):

  arr = [10, 20, 30, 40, 50]
  
  # 접근
  print(arr[2])  # 30
  
  # 삽입
  arr.insert(2, 25)  # [10, 20, 25, 30, 40, 50]
  
  # 삭제
  del arr[3]  # [10, 20, 25, 40, 50]

• 활용 예:
  이미지 처리에서 픽셀 행렬 표현
  테이블 기반 정적 데이터 저장 구조 등

---

2. 해시맵 (Hash Map)

• 정의:
  키(key)-값(value) 쌍으로 데이터를 저장하는 자료구조
  해시 함수를 통해 키를 고유한 인덱스로 변환하여 저장

• 구조 및 특징:
  배열과 해시 함수를 조합하여 구현됨
  충돌 처리 방식으로 체이닝(Chaining) 또는 개방 주소법(Open Addressing) 사용함
  키를 이용한 빠른 접근 가능함

• 시간 복잡도:

  • 평균 접근/탐색/삽입/삭제: O(1)
  • 최악의 경우 (충돌 발생 시): O(n)

• 기본 동작:

  1. 저장 → 해시 함수로 인덱스 생성 후 해당 위치에 저장
  2. 탐색 → 키를 해시화하여 대응 인덱스에 접근
  3. 삭제 → 키로 위치를 찾고 삭제 처리

• 예시 코드 (Python):

  hashmap = {}
  hashmap['apple'] = 10
  hashmap['banana'] = 20
  
  # 접근
  print(hashmap['apple'])  # 10
  
  # 삭제
  del hashmap['banana']

• 활용 예:
  데이터베이스 인덱싱
  캐시(Cache) 시스템
  키-값 기반 설정 저장 구조 등

---

3. 스택 (Stack)

• 정의:
  후입선출(LIFO, Last In First Out) 구조를 따르는 자료구조
  마지막에 들어간 데이터가 가장 먼저 나오는 구조

• 구조 및 특징:
  리스트, 연결 리스트로 구현 가능함
  한쪽 끝(top)에서만 삽입(push)과 삭제(pop) 가능
  함수 호출 시 호출 스택 등 시스템적 활용도 높음

• 시간 복잡도:

  • 접근: 제한적 (보통 top만 접근)
  • 삽입: O(1)
  • 삭제: O(1)

• 기본 동작:

  1. push → 스택 top에 요소 추가
  2. pop → 스택 top 요소 제거 및 반환
  3. peek → 현재 top 요소 확인 (삭제하지 않음)
  4. isEmpty → 스택이 비어있는지 확인

• 예시 코드 (Python):

  stack = []
  
  # push
  stack.append(1)
  stack.append(2)
  
  # peek
  top = stack[-1]  # 2
  
  # pop
  item = stack.pop()  # 2

• 활용 예:
  재귀 함수 처리 구조
  괄호 검사 알고리즘
  웹 브라우저 뒤로가기 기능 등

---

4. 큐 (Queue)

• 정의:
  선입선출(FIFO, First In First Out) 구조를 따르는 자료구조
  먼저 들어간 데이터가 먼저 나오는 구조

• 구조 및 특징:
  양쪽 끝(front, rear)에서 삽입과 삭제가 이루어짐
  일반 큐, 원형 큐, 우선순위 큐 등 다양한 변형 존재
  배열, 연결 리스트, deque 등을 통해 구현 가능

• 시간 복잡도:

  • 접근: 제한적 (보통 front만 접근)
  • 삽입: O(1)
  • 삭제: O(1)

• 기본 동작:

  1. enqueue → rear에 요소 추가
  2. dequeue → front에서 요소 제거 및 반환
  3. peek → 현재 front 요소 확인
  4. isEmpty → 큐가 비어있는지 확인

• 예시 코드 (Python):

  from collections import deque
  
  queue = deque()
  
  # enqueue
  queue.append(1)
  queue.append(2)
  
  # peek
  front = queue[0]  # 1
  
  # dequeue
  item = queue.popleft()  # 1

• 활용 예:
  프로세스 스케줄링
  너비 우선 탐색 (BFS) 알고리즘
  프린터 대기열 시스템 등

---

정리 비교 표

자료구조	특징	접근	삽입	삭제	응용
배열	인덱스 기반, 고정 크기	O(1)	O(n)	O(n)	행렬, 고정 데이터
해시맵	키-값 구조, 빠른 검색	O(1)	O(1)	O(1)	캐시, 설정 저장
스택	LIFO 구조, top 접근	제한	O(1)	O(1)	재귀, 괄호 검사
큐	FIFO 구조, front/rear 접근	제한	O(1)	O(1)	BFS, 스케줄링

---

결론

• 각 자료구조는 데이터의 삽입 및 삭제 방식과 구조적 특성에 따라 다른 성능 특성과 활용처를 가짐
• 배열은 빠른 접근이 장점이나 삽입/삭제에 부적합함
• 해시맵은 키를 통한 빠른 접근이 가능하나 충돌 관리가 중요함
• 스택과 큐는 삽입 및 삭제 위치가 제한적이지만 알고리즘 구현에서 핵심적 역할을 수행함
• 다양한 응용 분야에서 자료구조의 특성에 맞는 선택이 중요함

---