자료 구조: 스택·큐·리스트·그래프
쉽게 말하면
자료 구조는 데이터를 담는 그릇의 모양이에요. 한 줄로 늘어선 선형 구조(배열, 리스트, 스택, 큐)와 가지를 치거나 그물처럼 얽힌 비선형 구조(트리, 그래프)가 있어요. 스택은 접시 쌓기처럼 마지막에 넣은 것을 먼저 꺼내고(LIFO), 큐는 줄 서기처럼 먼저 온 것이 먼저 나가요(FIFO). 시험에는 넣고 빼는 순서를 따라가는 문제가 자주 나와요.
시험용 정의
자료 구조는 데이터를 효율적으로 저장하고 다루는 방법이다. 선형 구조: 배열(같은 형의 자료를 연속 저장, 인덱스로 바로 접근), 선형 리스트(연속 리스트, 연결 리스트), 스택(한쪽 끝 top에서만 삽입·삭제, LIFO), 큐(한쪽 rear에서 삽입, 반대쪽 front에서 삭제, FIFO), 데크(양쪽 끝 모두에서 삽입·삭제). 비선형 구조: 트리(계층 구조), 그래프(정점과 간선). 그래프에서 정점이 n개일 때 최대 간선 수는 무방향 n(n−1)/2, 방향 n(n−1)이다.
비유로 이해하기
스택은 식당의 접시 더미(맨 위부터 쓰고 맨 위에 올린다), 큐는 은행 번호표 줄, 데크는 앞뒤 문이 다 열리는 버스다. 트리는 회사 조직도, 그래프는 지하철 노선도다.
자세히
먼저 알아 둘 말
| 말 | 뜻 |
|---|---|
| push / pop | 스택에 넣기 / 스택에서 꺼내기 |
| top | 스택의 맨 위 위치 |
| front / rear | 큐의 앞(삭제하는 쪽) / 뒤(삽입하는 쪽) |
| 오버플로 / 언더플로 | 가득 찬 곳에 넣으려 할 때 / 빈 곳에서 꺼내려 할 때 |
| 노드 | 연결 리스트·트리·그래프를 이루는 한 칸 (데이터 + 링크) |
| 정점 / 간선 | 그래프의 점(노드) / 점을 잇는 선 |
선형 구조 비교
| 구조 | 삽입·삭제 | 특징·쓰임 |
|---|---|---|
| 배열 | 중간 삽입·삭제 시 자료 이동 필요 | 인덱스로 바로 접근. 크기 고정 |
| 연결 리스트 | 포인터만 바꾸면 됨 | 접근은 처음부터 따라가야 해서 느림. 링크 공간 필요 |
| 스택 | top 한쪽에서만 | LIFO. 함수 호출·복귀 주소, 후위 표기식 계산, 깊이 우선 탐색, 되돌리기 |
| 큐 | rear에 삽입, front에서 삭제 | FIFO. 운영체제 작업 스케줄링, 버퍼, 너비 우선 탐색 |
| 데크 | 양쪽 끝 모두 | 입력 제한 데크(스크롤), 출력 제한 데크(셸프) |
스택 순서 문제 푸는 법
입력 순서가 A, B, C, D로 정해져 있을 때 가능한 출력 순서를 묻는다. 넣고 빼기를 섞을 수 있지만 꺼낼 수 있는 건 늘 맨 위다.
- 가능: B A D C (A push, B push, B pop, A pop, C push, D push, D pop, C pop)
- 불가능: C A B D. C를 꺼내려면 A, B가 이미 쌓여 있어 다음에 나올 수 있는 건 B다. A가 먼저 나올 수 없다
그래프
| 구분 | 최대 간선 수 (정점 n) | 예 (n = 5) |
|---|---|---|
| 무방향 그래프 | n(n−1)/2 | 10 |
| 방향 그래프 | n(n−1) | 20 |
기출에서 더 나온 것
| 말 | 뜻 |
|---|---|
| 그래프의 최대 간선 수 | 정점이 n개면 무방향 그래프는 n(n-1)/2개, 방향 그래프는 n(n-1)개 |
시험에 이렇게 나와요
- 선형 구조 → 배열·리스트·스택·큐·데크 / 비선형 → 트리·그래프
- 스택 → 한쪽 끝에서만 넣고 빼는 LIFO. 포인터는 Top 하나 (Front·Rear 두 개는 큐)
- 스택 출력 순서 따지기 → push·pop 순서대로 그려 보면 불가능한 순서가 보인다
- 스택의 쓰임 → 서브루틴 호출·재귀·후위 표기 계산·깊이 우선 탐색 (선택 정렬은 아님)
- 무방향 그래프 최대 간선 수 → n(n-1)/2, 방향 그래프는 n(n-1)
- 스택에서 꺼낼 게 없을 때 → 언더플로, 꽉 찼는데 넣을 때 → 오버플로
확인 문제
Q1. 빈 스택에 A, B, C를 차례로 push한 뒤 pop을 두 번 하면 마지막으로 꺼낸 것은?
- A
- B
- 꺼낼 수 없다
- C
정답 보기
2번 B
스택은 LIFO(후입선출). 쌓인 순서 A(바닥) B C(맨 위). 첫 pop은 C, 두 번째 pop은 B다.
Q2. 입력이 A, B, C, D 순서일 때 스택으로 만들 수 없는 출력 순서는?
- D C B A
- A B C D
- B C D A
- C A B D
정답 보기
4번 C A B D
C를 꺼낸 순간 스택에는 A, B가 남아 있고 맨 위는 B라 A가 먼저 나올 수 없다.
Q3. 스택을 쓰는 경우가 아닌 것은?
- 후위 표기식 계산
- 서브루틴 호출과 복귀
- 운영체제의 작업 스케줄링
- 깊이 우선 탐색
정답 보기
3번 운영체제의 작업 스케줄링
운영체제의 작업 스케줄링은 먼저 온 것을 먼저 처리하는 큐를 쓴다. 서브루틴 호출과 복귀, 후위 표기식 계산, 깊이 우선 탐색은 스택(LIFO)을 쓴다.
Q4. 정점이 6개인 무방향 그래프가 가질 수 있는 최대 간선 수는?
- 12
- 15
- 30
- 36
정답 보기
2번 15
15개다. 무방향 그래프의 최대 간선 수는 n(n-1)/2 = 6 × 5 / 2다. 방향 그래프라면 n(n-1) = 30이다.
Q5. 삽입은 한쪽(rear), 삭제는 다른 쪽(front)에서 하는 자료 구조는?
- 배열
- 큐
- 스택
- 트리
정답 보기
2번 큐
큐다. 먼저 들어간 것이 먼저 나오는 FIFO 구조다. 스택은 한쪽에서 넣고 빼는 LIFO 구조다.
헷갈리기 쉬운 O·X
트리와 그래프는 선형 자료 구조다.
정답 보기
X 비선형 구조다.
연결 리스트는 배열보다 중간 삽입·삭제가 쉽지만 특정 위치 접근은 느리다.
정답 보기
O
큐는 LIFO 방식으로 동작한다.
정답 보기
X 큐는 FIFO, 스택이 LIFO.