자료구조 한번에 정리

📑 자료구조란?

데이터를 효율적으로 저장하고, 꺼내고, 조작하기 위한 구조이다.

---

📦 기본 자료구조 총정리

자료구조	구조 특징	꺼내는 순서	사용 예시
배열 (Array / List)	선형구조, 순서가 있다	인덱스로 접근	리스트, 순회
스택 (Stack)	한 쪽 끝에만 넣고 꺼냄	LIFO (나중에 넣은게 먼저 나옴) = 프링글스 통	되돌리기(Undo), 괄호 검사
큐 (Queue)	한 쪽에 넣고 다른쪽에서 꺼냄	FIFO (먼저 넣은게 먼저 나옴 / 선입선출) = 파이프	BFS, 대기열
덱 (Deque)	양 쪽 끝에서 넣고 꺼내기 가능	양방향 가능	슬라이딩 윈도우, 양쪽 탐색
힙 (Heap)	완전 이진트리, 우선순위 기반	우선순위 높은 값 먼저	다익스트라, 스케줄링
트리 (Tree)	계층구조, 부모-자식 관계	순회 법에 따라 다름	폴더 구조, 트리 탐색
그래프 (Graph)	정점과 간선 관계	DFS, BFS, 다익스트라 등	경로 탐색
해시 (HashMap / Dictionary)	key → value	key로 접근	딕셔너리, 카운팅

---

🥞 스택(Stack) - 늦게 들어간거 먼저나옴

stack = []

# 값 추가 (push)
stack.append(1)
stack.append(2)

# 값 제거 (pop)
print(stack.pop())  # ➜ 2
print(stack.pop())  # ➜ 1

🪈큐(Queue) - 선입선출

뒤에서 넣고, 앞에서 꺼낸다. / 파이프, 줄서기 등

from collections import deque

queue = deque()

# 값 추가 (enqueue)
queue.append(1)
queue.append(2)

# 값 제거 (dequeue)
print(queue.popleft())  # ➜ 1
print(queue.popleft())  # ➜ 2

👑 힙(Heap) — 우선순위 높은거 먼저

기본은 최소힙

import heapq

heap = []

# 값 추가 (자동 정렬됨)
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)

# 최솟값 꺼내기
print(heapq.heappop(heap))  # ➜ 1
print(heapq.heappop(heap))  # ➜ 2
print(heapq.heappop(heap))  # ➜ 3

🌳 트리(Tree) — 계층적 구조

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

# 트리 생성
root = Node(1)
child1 = Node(2)
child2 = Node(3)

root.children.append(child1)
root.children.append(child2)

# 순회 예시 (DFS)
def dfs(node):
    print(node.value)
    for child in node.children:
        dfs(child)

dfs(root)

+) 트리와 그래프의 차이는?

	트리 (Tree)	그래프 (Graph)
정의	사이클 없는 연결 그래프 (일종의 그래프)	**정점(노드)과 간선(연결)**으로 이루어진 자료구조
방향성	보통 방향 있음 (부모 → 자식)	방향 그래프 / 무방향 그래프 모두 가능
루트	반드시 1개의 루트 노드(root) 있음	루트 없음 (모든 노드가 대등할 수 있음)
사이클	❌ 없음 (순환 불가)	✅ 있을 수 있음 (예: A → B → A)
경로 수	두 노드 사이 경로는 1개뿐	두 노드 사이에 여러 경로 가능
예시	폴더 구조, 이진 탐색 트리	지하철 노선도, SNS 친구 관계

 

스택, 큐, 힙, 트리 정리

구조	삽입	꺼내기	순서
스택	위에 넣음	위에서 꺼냄	LIFO
큐	뒤에 넣음	앞에서 꺼냄	FIFO
힙	아무데나 넣음	우선순위대로 꺼냄	값 기준
트리	부모 → 자식 연결	탐색 방식 따라 다름	계층 구조