python_#7

⚙️ Stack vs Queue vs Hash Table

🧠 1️⃣ 기본 개념 요약

자료구조	뜻	구조적 특징	대표적인 동작	비유
Stack (스택)	‘쌓아 올린 구조’	LIFO (Last In, First Out) → 나중에 넣은 게 먼저 나옴	push(), pop()	접시를 차곡차곡 쌓아놓은 더미
Queue (큐)	‘줄 서 있는 구조’	FIFO (First In, First Out) → 먼저 넣은 게 먼저 나옴	enqueue(), dequeue()	버스 정류장 줄 서기
Hash Table (해시 테이블)	‘키(key)-값(value) 쌍으로 저장하는 구조’	해시 함수로 빠르게 접근	insert(key, value), get(key)	사전(dictionary)처럼 단어-뜻 저장

⚙️ 2️⃣ 동작 원리 간단히 보기

🔸 Stack

let stack = [];
stack.push(1);   // [1]
stack.push(2);   // [1, 2]
stack.pop();     // 2 제거 → [1]

-> 나중에 들어온 게 먼저 나감 (LIFO)

🔸 Queue

let queue = [];
queue.push(1);    // [1]
queue.push(2);    // [1, 2]
queue.shift();    // 1 제거 → [2]

-> 먼저 들어온 게 먼저 나감 (FIFO)

🔸 Hash Table

let hashTable = new Map();
hashTable.set("name", "Minnie");
hashTable.get("name"); // "Minnie"

-> key(“name”)로 value를 바로 찾음 — 빠름 🔥

⚖️ 3️⃣ 비교 정리

항목	Stack	Queue	Hash Table
저장 방식	순차적 (위에서 쌓음)	순차적 (앞뒤로 나감)	key-value 쌍
접근 순서	LIFO	FIFO	key로 직접 접근
사용 예시	함수 호출(콜스택), 되돌리기(undo)	대기열, 프린터 작업	데이터베이스, 캐시
속도	빠름 (O(1))	빠름 (O(1))	매우 빠름 (평균 O(1))
언어에서 예	JS의 Array, Python의 list	JS의 Array, Python deque	JS Map/Object, Python dict

💡 4️⃣ 예시로 쉽게 이해하기

상황	어떤 구조?	이유
웹 브라우저 ‘뒤로 가기’	Stack	가장 최근 페이지부터 꺼냄
은행 대기표	Queue	먼저 온 사람부터 처리
주민등록번호로 이름 찾기	Hash Table	고유 키로 바로 찾음

🧠 1️⃣ 기본 개념 요약

자료구조	뜻	구조적 특징	데이터 저장 방식	비유
Array (배열)	연속된 공간에 데이터를 차례로 저장	한 덩어리로 연결되어 있음	메모리 상에서 연속적으로 저장	옆 칸과 붙어있는 아파트
Linked List (연결 리스트)	노드(node) 단위로 연결된 구조	각각의 노드가 다음 노드의 주소를 가짐	메모리 상에서 흩어져 있지만 링크로 연결	체인 목걸이처럼 고리로 연결된 구슬

⚙️ 2️⃣ 구조 차이 쉽게 보기

🔸 Array (배열)

[10] [20] [30] [40]
 ↑    ↑    ↑    ↑
연속된 공간

🔸 Linked List (연결 리스트)

[10 | next] → [20 | next] → [30 | next] → null
   (다음 노드의 주소를 가리킴)

⚖️ 3️⃣ 비교 정리 표

항목	Array (배열)	Linked List (연결 리스트)
저장 방식	연속된 메모리	흩어진 노드들을 포인터로 연결
메모리 효율	고정 크기(초기 지정 필요)	유동적 크기(필요할 때마다 확장 가능)
삽입/삭제 속도	느림 😢 (O(n)) — 중간 삽입 시 이동 필요	빠름 😀 (O(1)) — 링크만 수정
검색 속도	빠름 (O(1)) — 인덱스로 바로 접근	느림 (O(n)) — 처음부터 탐색
메모리 사용량	적음 (데이터만 저장)	많음 (포인터도 저장)
대표 사용 예시	배열, 리스트, 이미지 픽셀 데이터	스택, 큐, 그래프 노드 연결 등

💡 4️⃣ 상황별 선택 기준

상황	어떤 걸 쓰면 좋을까	이유
데이터 개수가 고정되어 있고, 인덱스로 자주 접근해야 함	✅ Array	인덱스 접근이 빠름
데이터 삽입/삭제가 자주 일어남	✅ Linked List	링크만 바꾸면 돼서 효율적
메모리를 미리 확보해도 괜찮음	Array	고정 크기라 안정적
메모리를 효율적으로 쓰고 싶음	Linked List	필요한 만큼만 할당

🧩 5️⃣ 예시 코드로 비교 (JavaScript 기준)

🔸 Array

let arr = [10, 20, 30];
arr.push(40);   // [10, 20, 30, 40]
console.log(arr[2]); // 30 (인덱스로 바로 접근 가능)

🔸 Linked List (간단 구현 예)

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

let first = new Node(10);
let second = new Node(20);
first.next = second;  // 10 → 20

->Array는 인덱스로 접근하지만,
LinkedList는 “다음(next)”을 따라가며 탐색해야 함.

🎯 정리 요약 한 줄

📦 Array: 빠른 접근, 느린 삽입
🔗 Linked List: 느린 접근, 빠른 삽입