큐와 스택은 프로그래밍에서 중요한 역할을 하는 자료 구조입니다. 큐(Queue): 선입선출(FIFO) 방식으로 동작하며, 대기열 관리, 네트워크 패킷 처리, BFS 알고리즘 등에 활용됩니다. 스택(Stack): 후입선출(LIFO) 방식으로 동작하며, 함수 호출 스택, 괄호 검사, 문자열 역순 변환 등에 사용됩니다.이러한 자료 구조들은 데이터 처리의 효율성을 높이는 데 필수적인 역할을 합니다.



큐(Queue)

큐는 먼저 들어온 데이터가 먼저 처리되는 선입선출(FIFO: First-In, First-Out) 구조입니다.

BFS 탐색, 캐시 구현, 멀티 스레딩 환경의 작업 큐 등에서 활용됩니다.

큐는 배열(Array) 또는 연결 리스트(Linked List) 를 사용하여 구현할 수 있습니다.

  1. 연결 리스트 기반 큐
    • head와 tail 포인터를 사용하여 구현합니다.
    • head에서 데이터를 제거(Dequeue), tail에서 데이터를 추가(Enqueue)합니다.
    • Peek 연산은 head를 조회하면 됩니다.
    • Java의 LinkedList 클래스는 Queue 인터페이스를 상속하여 큐 기능을 제공합니다.
  2. 배열 기반 큐
    • 일반적인 배열을 사용하면 Dequeue 시 데이터를 한 칸씩 이동해야 하므로 비효율적입니다.
    • 원형 큐(Circular Queue) 를 사용하면 이러한 문제를 해결할 수 있습니다.
    • front와 rear 인덱스를 두고 (index % size) 연산을 통해 원형으로 처리합니다.
    • 더미 인덱스(dummy index) 를 활용하면 더욱 쉽게 구현할 수 있습니다.

우선순위 큐(Priority Queue)

우선순위 큐는 일반적인 큐와 달리 우선순위가 높은 요소가 먼저 처리됩니다.

  • 다익스트라 알고리즘, 크루스칼 알고리즘 등에 활용됩니다.
  • 일반적으로 힙(Heap) 자료구조 를 사용하여 구현합니다.
  • 힙은 완전 이진 트리의 형태를 가지며, 부모와 자식 간의 우선순위 관계를 유지합니다.


스택(Stack)

스택은 후입선출(LIFO: Last-In, First-Out) 구조를 가지며, 가장 최근에 추가된 데이터가 먼저 제거됩니다.

  • 함수 호출 스택, 괄호 검사, 재귀 호출, 문자열 역순 변환 등에 활용됩니다.

스택은 배열(Array) 또는 연결 리스트(Linked List) 를 사용하여 구현할 수 있습니다.

  1. 배열 기반 스택
    • Top 포인터를 사용하여 데이터 추가(Push)와 제거(Pop)를 수행합니다.
    • 배열을 이동할 필요가 없으므로 큐보다 효율적입니다.
    • 단, 크기가 고정 되어 있어 배열 크기를 초과하면 재할당이 필요합니다.
  2. 연결 리스트 기반 스택
    • 동적으로 크기가 변하므로 배열보다 유연성이 높습니다.
    • 하지만 포인터 관리 비용 때문에 배열보다 느릴 수 있습니다.


맵(Map)

맵(Map)은 키-값(Key-Value) 쌍을 저장하는 자료 구조로, 다양한 방식으로 구현됩니다.

1. Hash Map

  • 빠른 삽입, 삭제, 조회: O(1)
  • 내부적으로 해시 함수(Hash Function) 를 사용하여 데이터 저장 위치를 결정합니다.
  • Cache 친화적이지 않음: 메모리 내에서 분산 저장되므로 Cache Miss가 발생할 가능성이 높습니다.
  • 해시 함수에 따라 성능이 달라지며, 해시 충돌(Hash Collision) 처리를 위한 체이닝(Chaining) 또는 오픈 어드레싱(Open Addressing) 기법이 필요합니다.

2. Sorted Map (배열 기반, 이진 삽입 정렬)

  • 정렬된 상태를 유지하는 맵
  • 삽입, 삭제: O(N) (배열을 이동해야 함)
  • 조회: O(logN) (이진 탐색 사용)
  • Cache 친화적: 데이터가 연속적으로 저장되므로 CPU Cache Hit 확률이 높음

3. Sparse Set

  • Hash Map + Sorted Map의 장점 결합
  • Map을 사용하여 삽입, 삭제, 조회 속도를 빠르게 하고, 실제 데이터는 Array에 저장
  • Dense한 형태로 데이터 저장 → Cache 친화적
  • 단점:
    • 데이터 저장 순서가 보장되지 않음
    • Map과 Array를 모두 사용하므로 메모리 사용량 증가

4. Sorted Map (Binary Tree 기반)

  • 이진 탐색 트리(Binary Search Tree, BST)를 사용하여 정렬된 상태 유지
  • 삽입, 삭제, 조회: O(logN)
  • Cache 친화적이지 않음: 데이터가 메모리 상에 흩어져 저장됨