20260430 데이터구조와알고리즘 9주차
강의 핵심 요약 — 큐(Queue), 덱(Deque), 리스트(List), 연결 리스트(Linked List)
이번 강의는 크게 4파트였음.
- 큐(Queue)
- 원형 큐(Circular Queue)
- 덱(Deque)
- 리스트와 연결 리스트(Linked List)
1. 큐(Queue)
큐의 정의
큐는 먼저 들어온 데이터가 먼저 나가는 자료구조임.
즉:
FIFO(First In First Out)
예시:
- 은행 대기열
- 버스 줄
- 프린터 출력 대기열
스택과 큐 차이
스택(Stack)
LIFO
3
2
1
→ 3 먼저 나감
큐(Queue)
FIFO
1 2 3
→ 1 먼저 나감
이 차이 시험에 엄청 중요함.
2. 큐의 기본 연산 (ADT)
큐의 핵심 연산:
| 연산 | 의미 |
|---|---|
| create() | 큐 생성 |
| init() | 초기화 |
| is_empty() | 비었는지 검사 |
| is_full() | 꽉 찼는지 검사 |
| enqueue() | 데이터 삽입 |
| dequeue() | 데이터 삭제 |
| peek() | 맨 앞 데이터 보기 |
3. enqueue / dequeue
enqueue()
큐 뒤(rear)에 삽입
enqueue(&q, 10);
결과:
10
dequeue()
큐 앞(front)에서 삭제
dequeue(&q);
결과:
10 제거
4. 큐의 구조
큐는 두 개의 포인터 사용함.
| 변수 | 의미 |
|---|---|
| front | 삭제 위치 |
| rear | 삽입 위치 |
5. 선형 큐(Linear Queue)
특징
배열을 직선 형태로 사용함.
data[0] data[1] data[2]
삽입:
- rear 증가
삭제:
- front 증가
문제점
삭제 계속하면:
빈 공간 생김
예:
_ _ 30 40
앞이 비었는데도 rear가 끝이면:
포화 상태
라고 판단함.
즉:
실제로 공간 남았는데 못 씀.
이게 선형 큐의 치명적 문제.
6. 선형 큐 구현
구조체
typedef struct {
int front;
int rear;
element data[MAX_QUEUE_SIZE];
} QueueType;
초기 상태
front = -1;
rear = -1;
공백 상태
front == rear
포화 상태
rear == MAX_QUEUE_SIZE - 1
enqueue()
q->data[++(q->rear)] = item;
rear 증가 후 저장
dequeue()
item = q->data[++(q->front)];
front 증가 후 반환
7. 원형 큐(Circular Queue)
선형 큐 문제 해결 버전.
배열 끝까지 가면 다시 처음으로 돌아감.
0 1 2 3 4
↑ ↓
└───────┘
8. 원형 큐 핵심 개념
front
첫 번째 요소 "앞"
rear
마지막 요소 위치
9. 원형 큐 상태 조건
공백 상태
front == rear
포화 상태
(rear + 1) % MAX_QUEUE_SIZE == front
10. 왜 한 칸 비워두는가
교수 핵심 포인트.
원형 큐에서:
front == rear
이면 공백 상태인데
만약 꽉 차도 같아지면:
공백인지 포화인지 구분 불가능
그래서:
무조건 한 칸 비워둠.
이거 시험 단골임.
11. 원형 큐 구현 핵심
enqueue
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
배열 끝 가면 다시 0으로 돌아감.
dequeue
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
12. 큐 응용
실제 사용 사례
직접 응용
- 공항 대기열
- 은행 번호표
- 네트워크 패킷
- 프린터 버퍼
간접 응용
- 알고리즘
- 운영체제
- 시뮬레이션
13. 버퍼(Buffer)
큐 대표 응용.
입력 속도와 출력 속도 차이 조절.
예:
- 키보드 입력
- 프린터 출력
- 네트워크 패킷 저장
14. 덱(Deque)
정의
Double Ended Queue
양쪽에서 삽입/삭제 가능.
큐와 차이
일반 큐
삽입 → rear
삭제 → front
덱
앞뒤 모두 삽입/삭제 가능
15. 덱 핵심 연산
| 연산 | 의미 |
|---|---|
| add_front | 앞 삽입 |
| add_rear | 뒤 삽입 |
| delete_front | 앞 삭제 |
| delete_rear | 뒤 삭제 |
| get_front | 앞 조회 |
| get_rear | 뒤 조회 |
16. add_front 핵심
q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
음수 방지하려고:
+ MAX_QUEUE_SIZE
해주는 거 중요함.
17. 리스트(List)
개념
순서 있는 데이터 집합.
파이썬 리스트랑 거의 비슷하게 생각하면 됨.
리스트 기본 연산
| 연산 | 의미 |
|---|---|
| insert | 삽입 |
| delete | 삭제 |
| clear | 전체 삭제 |
| get_entry | 특정 위치 반환 |
| get_length | 길이 반환 |
18. 배열 기반 리스트(Array List)
특징
배열 사용.
A B C D
처럼 연속 메모리 사용.
장점
- 구현 쉬움
- 인덱스 접근 빠름
단점
중간 삽입
A B C D
중간에 X 넣으면:
A X B C D
B,C,D 전부 이동해야 함.
삭제도 동일
A B C D
B 삭제:
A C D
C,D 당겨야 함.
19. 연결 리스트(Linked List)
이번 강의 후반 핵심.
개념
데이터들을 포인터로 연결.
[10|*] → [20|*] → [30|null]
20. 노드(Node)
노드 구성:
| 필드 | 역할 |
|---|---|
| 데이터 필드 | 실제 값 |
| 링크 필드 | 다음 노드 주소 |
21. 배열 vs 연결 리스트
배열(Array)
장점:
- 빠른 접근
- 구현 쉬움
단점:
- 크기 제한
- 삽입/삭제 느림
연결 리스트
장점:
- 삽입/삭제 쉬움
- 크기 제한 적음
- 메모리 연속 필요 없음
단점:
- 구현 어려움
- 디버깅 어려움
- 포인터 실수 위험 큼
22. 연결 리스트 삽입
맨 앞 삽입
원래:
10 → 20
새 노드 5 삽입:
5 → 10 → 20
과정:
- 새 노드 생성
- 새 노드 링크 → 기존 head
- head → 새 노드
23. 중간 삽입
예:
20 → 30
사이에 35 삽입.
결과:
20 → 35 → 30
핵심:
- 새 노드 링크 먼저 연결
- 기존 링크 변경
순서 틀리면 링크 끊김.
24. 연결 리스트 삭제
예:
10 → 20 → 30
10 삭제:
20 → 30
과정:
- 삭제 노드 저장
- head 이동
- free()로 메모리 반납
25. 교수 강조 포인트
배열 기반 구조
- 구현 쉬움
- 이동 비용 큼
연결 리스트
- 삽입/삭제 효율 좋음
- 포인터 때문에 어렵고 디버깅 지옥
교수도 계속:
“그림으로는 쉬운데 코드 가면 어렵다”
강조함.
시험 관점 핵심
진짜 중요한 거:
큐
- FIFO
- front/rear 변화
- 원형 큐 modulo 계산
- 공백/포화 조건
덱
- 양방향 삽입 삭제
리스트
- 배열 삽입 시 이동 발생
연결 리스트
- 포인터 연결 순서
- 삽입/삭제 흐름
- free() 반드시 사용
특히 연결 리스트는:
p->link
head
free()
이 흐름 손으로 그릴 줄 알아야 함.