자료구조 파트 공부를 시작하면서 자료구조에 대한 분류를 놓쳤던 것이 생각나서 정리한다.
Chapter1 . 자료 구조
자료구조 : 효율적인 프로그램을 작성하기 위해 데이터를 컴퓨터 메모리 내 저장하고 조직화 하는 논리적/물리적 방법
자료구조의 핵심은 '데이터 간의 관계' 와 '연산' 이다.
즉, 어떤 데이터를 저장할 때 그 데이터들끼리 어떤 관계(순서,계층 등)를 맺고 있으며, 그 데이터를 어떻게 찾고 수정하고 삭제할 것인지를 결정하는 규칙의 집합인 것이다.
자료구조는 크게 선형 구조와 비선형 구조로 나눠서 볼 수 있다.
선형 구조 (Linear Structure)
: 데이터가 '연속적(1:1관계)' 으로 나열된 구조 = 일렬로 저장 / 한방향 탐색
- 배열 (Array) : 동일한 자료형의 데이터들이 연속된 메모리 공간에 저장
- 연결 리스트 (Linked List) : 노드(데이터 + 포인터)들이 포인터로 연결된 구조 -> 삽입/삭제가 유연
- 스택 (Stack) : 한쪽 끝에서만 데이터의 삽입/삭제가 일어남 -> LIFO
- 큐 (Queue) : 한쪽(Rear)에서는 삽입, 다른 한쪽(Front)에서는 삭제가 일어남 -> FIFO
- 데크 (Deque) : 양쪽 끝 모두에서 삽입/삭제가 가능한 구조
| 선형 구조 (Linear Structure) | ||||
| 자료구조 | 주요 특징 | 장점 | 단점 | 관련 핵심 키워드 |
| 배열 | 연속 메모리 공간 | 인덱스 접근이 매우 빠름 (O(1)) | - 크기 변경 불가 - 삽입/삭제 시 데이터 이동(Shift) 필요 |
순차 리스트, 고정 크기 |
| 연결 리스트 | 노드와 포인터 연결 | 삽입/삭제가 자유롭고 동적 크기 조절 가능 | - 접근 속도가 느림 - 포인터를 위한 추가 메모리 필요 |
노드, 포인터, 링크 |
| 스택 | LIFO (후입선출) | 구현이 간단하고 데이터 관리가 명확함 | - 데이터 접근이 제한적이며 크기 제한 시 오버플로우 | 복귀 주소, 후위 표기법 |
| 큐 | FIFO (선입선출) | 데이터 입력 순서를 정확히 보장함 | - 중간 데이터 접근 불가 - 삭제 시 빈 공간 관리 필요 |
스케줄링, 대기열 |
비선형 구조 (Non-Linear Structure)
: 데이터가 '계층적이거나 망형(1:N 또는 N:M 관계)'으로 구성된 구조 = 여러 방향 탐색
- 트리 (Tree) : 노드들이 부모-자식 관계의 계층 구조를 가진다. -> 사이클이 없는 그래프의 일종
- 그래프 (Graph) : 정점(Vertax)과 간선(Edge)으로 연결된 망형 구조를 가진다. -> 방향/무방향성 존재
| 비선형 구조 (Non-Linear Structure) | ||||
| 자료구조 | 주요 특징 | 장점 | 단점 | 관련 핵심 키워드 |
| 트리 | 계층형 구조 (1:N) | 데이터 탐색 및 계층 관계 표현에 효율적 | - 구조가 복잡함 - 삽입/삭제 시 균형 관리가 필요함 |
이진 트리, 순회 방식 |
| 그래프 | 망형 구조 (N:M) | 복합적인 관계(지도, 네트워크) 표현에 최적 | - 알고리즘 구현이 어렵고 탐색 시 무한 루프 위험 | 정점, 간선, DFS/BFS |
Chapter 2. 스택 (Stack) vs 큐 (Queue)
스택과 큐는 작동 방식이 정반대 이기 때문에 완전히 다른 것 처럼 보이지만 사실 아주 중요한 공통 분모도 가지고 있다.
둘의 공통점을 간단하게 정리하자면,
1. 1:1 선형 자료구조 (Linear Data Structure)
2. 특정 지점에서만 삽입/삭제가 허용되는 '제한된 리스트'
3. 정적 구현과 동적 구현 가능
4. 논리적 모델 : 데이터가 실제로 '어떻게 저장'되는지(물리적)보다, '어떤 연산'이 일어나는지(논리적)에 집중.
총 4개의 공통점이 있다.
시험 Tip ↓
1. 정보처리기사 시험 문제에서 "삽입과 삭제가 제한된 선형 리스트"라는 표현이 나오면, 선택지에서 스택, 큐, 데크(Deque) 중 하나를 고르라는 신호이다.
2. 만약 문제에서 "리스트의 한쪽 끝이나 양쪽 끝에서만 삽입과 삭제가 이루어지는 자료구조들을 통칭하는 말은?" 이라고 묻는다면, 정답 후보는 선형 구조 중에서도 ①스택(Stack), ②큐(Queue), ③데크(Deque) 이 3가지 이다.
3. "오버플로우(Overflow)"와 "언더플로우(Underflow)"는 스택과 큐에서 공통적으로 발생하는 상태 이상 현상이다
- 언더플로우: 자료구조가 비어 있는데 데이터를 꺼내려고 할 때 (Pop/Dequeue 시 발생)
- 오버플로우: 자료구조가 꽉 찼는데 데이터를 더 넣으려고 할 때 (Push/Enqueue 시 발생)
스택 (Stack) :
한쪽 끝에서만 자료의 삽입과 삭제가 이루어지는 LIFO(Last-In, First-Out, 후입선출) 방식
스택은 현재 작업을 잠시 멈추고 다른 작업을 한 뒤, 다시 가장 최근의 상태로 돌아가야 하는 상황에서 독보적인 효율을 보여준다.
ex) 함수 호출, 뒤로 가기 등
- 특징 : LIFO (Last-In, First-Out): 가장 마지막에 들어온 데이터가 가장 먼저 나가는 '후입선출' 구조
- 단방향 입출력 : 데이터의 삽입(Push)과 삭제(Pop)가 오직 한쪽 끝(Top)에서만 이루어진다.
- 포인터 관리 : Top이라는 포인터가 항상 가장 최근에 삽입된 자료의 위치를 가리키고 있다.
- 장점 : 구현이 단순하고 삽입과 삭제가 항상 일정한 시간(O(1)) 내에 이루어져 빠르다.
- 단점 : 데이터를 꺼내려면 무조건 위에서부터 다 치워야하기 때문에 TOP 이외의 중간이나 바닥에 있는 데이터에 직접 접근할 수 없어서 유연성이 부족하다.
시험 Tip ↓
1. 시험 문제에서 "다음 중 스택을 사용하는 사례로 옳은/옳지 않은 것은?" 이라는 문제가 나오면 아래 키워드를 찾으면 된다.
① 함수 호출(Function Call)
② 재귀(Recursion)
③ 수식 계산( 중위 표기법(Infix)을 후위 표기법(Postfix)으로 변환하거나 계산할 때)
④ 역순 출력
⑤ 인터럽트(Interrupt) 처리
⑥ 실행 취소(Undo)
2. [실기 단답형 유형] Q. 크기가 5인 빈 스택에 다음과 같은 연산을 순서대로 수행했을 때, 마지막에 스택의 TOP이 가리키는 값은?
연산: PUSH(A) → PUSH(B) → POP() → PUSH(C) → PUSH(D)
정답: D (A삽입, B삽입, B삭제, C삽입, D삽입 순이므로 스택에는 [A, C, D]가 남고 TOP은 D를 가리킴)
스택의 연산
| 연산 명칭 | 동작 설명 | TOP 포인터 변화 | 비고 (시험 포인트) |
| PUSH | 스택의 가장 윗부분에 데이터를 삽입 | TOP = TOP + 1 | 삽입 전 Overflow 상태 확인 필요 |
| POP | 최상단 데이터를 제거하고 값을 반환 | TOP = TOP - 1 | 삭제 전 Underflow 상태 확인 필요 |
| PEEK / TOP | 최상단 데이터를 삭제하지 않고 확인만 함 | 변화 없음 | 데이터를 꺼내지 않고 읽기만 할 때 사용 |
| isEmpty | 스택이 비어있는지 여부를 확인 | 변화 없음 | TOP == -1 또는 TOP == 0 인지 체크 |
| isFull | 스택이 가득 찼는지 여부를 확인 | 변화 없음 | 스택의 최대 크기와 TOP을 비교 |
- 순서가 중요: PUSH는 포인터를 먼저 증가시킨 후 데이터를 넣고, POP은 데이터를 먼저 꺼낸 후 포인터를 감소시킨다. (구현 방식에 따라 다를 수 있으나 표준적인 흐름)
- 반환값의 유무: POP은 데이터를 삭제함과 동시에 그 값을 불러오지만, PEEK은 포인터를 건드리지 않고 값만 살짝 엿보는 것이다.
>> 리스트를 사용한 Pop과 Push 연산 코드 구현
# 1. 스택 초기화 (빈 리스트)
stack = []
max_size = 5
# 2. PUSH 연산: 데이터를 삽입
def push(data):
# Overflow 체크
if len(stack) >= max_size:
print("Overflow 발생!")
else:
stack.append(data) # 리스트의 맨 뒤에 데이터 추가
print(f"PUSH: {data}, 현재 스택: {stack}")
# 3. POP 연산: 데이터를 삭제 및 반환
def pop():
# Underflow 체크
if len(stack) == 0:
print("Underflow 발생!")
return None
else:
data = stack.pop() # 리스트의 맨 뒤(TOP) 데이터를 제거하고 반환
print(f"POP: {data}, 현재 스택: {stack}")
return data
# --- 테스트 코드 ---
push("A")
push("B")
push("C")
pop() # C가 나옴 (LIFO)
push("D")
# stack[-1]: 스택의 PEEK 연산
# len(stack): 스택에 쌓인 데이터의 개수를 확인
# ( -> 0이면 Underflow, max_size와 같으면 Overflow를 판단하는 기준)
# append(data): 스택의 PUSH와 같음. 리스트의 가장 마지막 인덱스에 데이터를 추가큐 (Queue) :
리스트의 한쪽 끝(Rear)에서는 삽입이, 다른 한쪽 끝(Front)에서는 삭제가 이루어지는 FIFO(First-In, First-Out, 선입선출) 방식
큐는 주로 순서를 기다려야 하는 모든 상황에 쓰인다.
ex) OS 스케줄링 , 프린터 출력 대기열, 버퍼(Buffer), 그래프의 너비 우선 탐색(BFS)
- 특징 : FIFO (First-In, First-Out): 먼저 들어온 데이터가 먼저 나가는 '선입선출' 구조
- 양방향 입출력 : 삽입과 삭제의 통로가 분리되어 있어 데이터의 흐름이 한 방향으로 흐릅
- 비동기 처리: 데이터가 들어오는 속도와 나가는 속도가 다를 때 이를 조절하는 완충 지대 역할
- 장점 : 순서가 보장되어있고 효율적인 스케줄링을 할 수 있다.
- 단점 : 스택과 마찬가지로 중간에 있는 데이터를 임의로 수정하거나 꺼낼 수 없고, 일반 큐는 빈 공간 재사용이 어렵다.
시험 Tip ↓
- Front (프런트): 가장 먼저 들어온 데이터의 위치이자, 삭제(Dequeue)가 일어나는 지점
- Rear (리어): 가장 마지막에 들어온 데이터의 위치이자, 삽입(Enqueue)이 일어나는 지점
- Enqueue (인큐): 큐의 Rear에 데이터를 추가하는 연산
- Dequeue (디큐): 큐의 Front에서 데이터를 꺼내고 삭제하는 연산
- 원형 큐 (Circular Queue): 일반 큐의 단점인 '앞부분 공간 낭비'를 해결하기 위해 처음과 끝을 연결한 구조
1. 큐는 "순서대로 처리해야 하는 대기열"과 관련된 키워드를 기억하는 것이 핵심이다.
① OS 스케줄링: 프로세스 처리 순서를 관리하는 Ready Queue.
② 스풀(Spool) / 버퍼(Buffer)
③ 데이터 통신
④ 그래프 탐색
⑤ 비동기 데이터 전송
2. 큐에서 데이터가 하나도 없을 때 Front와 Rear는 같은 지점(보통 0이나 -1)을 가리킨다.
3. [실기 단답형 유형] Q. 리스트의 한쪽 끝에서는 삽입(Rear) 작업이 이루어지고, 반대쪽 끝에서는 삭제(Front) 작업이 이루어지는 선형 자료구조의 명칭은?
정답: 큐 (또는 Queue)
큐의 연산
큐(Queue)는 스택과 달리 입구(Rear)와 출구(Front)가 따로 존재하기 때문에, 두 개의 포인터가 어떻게 움직이는지 이해하는 것이 핵심.
| 연산 명칭 | 동작 설명 | 포인터 변화 | 비고 (시험 포인트) |
| Enqueue | 큐의 가장 뒤(Rear)에 데이터를 삽입 | Rear = Rear + 1 | 삽입 전 Overflow 체크 필요 |
| Dequeue | 큐의 가장 앞(Front) 데이터를 제거 및 반환 | Front = Front + 1 | 삭제 전 Underflow 체크 필요 |
| Peek | Front에 있는 데이터를 삭제 없이 확인만 함 | 변화 없음 | 다음에 나올 데이터가 무엇인지 확인 |
| isEmpty | 큐가 비어있는지 확인 | 변화 없음 | Front == Rear 인 경우 비어있음 |
| isFull | 큐가 가득 찼는지 확인 | 변화 없음 | Rear가 큐의 마지막 인덱스인 경우 |
- 포인터의 이동: 데이터가 들어올 때는 Rear가 움직이고, 나갈 때는 Front가 움직인다. (두 포인터 모두 증가하는 방향으로 이동)
- 선형 큐의 한계: 일반적인 선형 큐는 데이터를 삭제해도 Front가 뒤로 밀려나기 때문에, 앞부분에 빈 공간이 생겨도 데이터를 다시 넣을 수 없는 단점이 있다. (이 문제를 해결하는 것이 원형 큐)
>> 파이썬 큐 핵심 연산 코드
from collections import deque
# 1. 큐 초기화
queue = deque()
max_size = 5
# 2. Enqueue 연산: 데이터를 삽입 (Rear에 추가)
def enqueue(data):
if len(queue) >= max_size:
print("Overflow 발생!")
else:
queue.append(data) # 오른쪽(뒤)으로 삽입
print(f"Enqueue: {data}, 현재 큐: {list(queue)}")
# 3. Dequeue 연산: 데이터를 삭제 및 반환 (Front에서 추출)
def dequeue():
if len(queue) == 0:
print("Underflow 발생!")
return None
else:
data = queue.popleft() # 왼쪽(앞)에서 데이터 제거 및 반환
print(f"Dequeue: {data}, 현재 큐: {list(queue)}")
return data
# --- 테스트 코드 ---
enqueue("손님1")
enqueue("손님2")
enqueue("손님3")
dequeue() # "손님1"이 나옴 (FIFO: 선입선출)
enqueue("손님4")
# append(data): 큐의 Enqueue 역할/큐의 가장 뒤(Rear)에 데이터를 넣는다.
# popleft(): 큐의 Dequeue 역할/가장 먼저 들어온 앞쪽(Front) 데이터를 제거하며 반환
# queue[0]: 큐의 Peek 연산/다음에 나갈 데이터(Front)가 무엇인지 확인만 할 때 사용.
# len(queue) == 0: 큐가 비어있는지(Underflow) 확인하는 조건
댓글