다섯 살도 알 수 있게 · 시스템SW
스택과 큐가 뭐예요?
스택·큐 같은 선형 자료구조를, 공구 상자를 쌓는 법과 차를 줄 세우는 법 이야기로 풀어봤어요.
상자 더미에서 필요한 B 상자만 콕 집어 꺼내야 해요.아무렇게나 쌓으면 원하는 상자를 바로 못 꺼내요.
규칙 없이 쌓고 꺼내면 순서가 매번 달라져요.'넣은 순서'와 '꺼내는 순서' 사이에 규칙이 있어야 해요.
선형 자료구조 = 물건을 쌓거나 줄 세우는 정해진 규칙이에요.스택과 큐는 꺼내는 쪽이 달라요 — 꼭대기냐, 맨 앞이냐.
push상자를 맨 위에 올려요
pop맨 위 상자부터 내려요
enqueue줄 맨 뒤에 가서 서요
dequeue줄 맨 앞부터 나가요
넣기와 꺼내기 동작마다 이름이 따로 있어요.배열처럼 '번호로 바로 찾는' 구조도 같이 알아두면 좋아요.
상자를 쌓다 보면 넘치고, 차 줄이 안 줄면 끝없이 길어져요.규칙은 단순해도, 스택과 큐 모두 정해진 크기를 넘기면 문제가 생겨요.
한 줄로
스택 = 상자를 위로 쌓고 위에서부터 꺼내는(LIFO) 규칙. 큐 = 차를 줄 세우고 앞에서부터 내보내는(FIFO) 규칙.
스택(Stack)은 후입선출(LIFO, Last-In-First-Out) 구조로 push(삽입)·pop(삭제)이 한쪽 끝에서만 일어나고, 함수 호출·되돌리기(undo) 등에 쓰여요. 큐(Queue)는 선입선출(FIFO, First-In-First-Out)로 enqueue(삽입)는 뒤에서, dequeue(삭제)는 앞에서 일어나며, 작업 대기열 등에 쓰여요. 배열(Array)은 인덱스로 바로 접근(O(1))하지만 크기 변경이 비싸고, 연결 리스트(Linked List)는 삽입·삭제가 쉽지만 순차 접근만 가능해요.
어른들은 이렇게 불러요
- 스택(LIFO)
Stack (LIFO) - 나중에 넣은 상자가 먼저 나옴. push·pop은 맨 위에서만 일어나요.
- 큐(FIFO)
Queue (FIFO) - 먼저 줄 선 차가 먼저 나감. enqueue는 뒤, dequeue는 앞이에요.
- 배열
Array - 번호가 매겨진 상자 선반. 번호로 바로 찾아요, 빠르지만 크기 변경이 비싸요.
- CPU 스케줄링(큐 활용)
CPU Scheduling (uses a queue) - 작업 순서판 자체가 큐예요. 그 순서판이 어떻게 쓰이는지는 여기서 봐요. → 리프트에 누가 먼저 올라갈까
- 기아현상(새치기하는 큐)
Starvation (a queue that lets cutting) - 급한 차가 계속 새치기하는 줄. 순서 규칙이 깨지면 큐가 불공평해져요. → 서로의 열쇠를 기다리며 멈춘 정비공장
- 이진트리
Binary Tree - 갈림길마다 왼쪽/오른쪽을 고르는 선반 지도. 한 줄이 아니라 갈라지는 구조는 여기서 다뤄요. → 갈림길에서 반씩 줄여가는 선반 지도
- 복잡도(Big-O)
Time Complexity - 자료가 늘 때 걸리는 시간을 재는 자. push/pop은 O(1), 중간 삽입은 더 느려요. → 차가 많아질 때 얼마나 느려질까
- 메시지 큐(다른 분야)
Message Queue (another field) - SRE 분야의 비슷한 '줄 세우기'. 서비스 사이에 작업을 주고받는 큐도 있어요. → SRE 분야의 메시지 큐
다음 이야기
오직 그 계산 하나만을 위한 전용 로봇팔 →