공부를 하다보면 기본 개념이 정리가 되지 않아 헷갈리는 경우가 많습니다
스택과 큐는 사실 프로그램 개발할 때 적용하는 기본 원리인 것 같아요 아직 제대로 된 프로젝트를 혼자 구현해볼 수 있는 정도는 아니지만 그래도 기본 개념은 항상 머릿속에 적립해놔야할 것!
1. 스택(Stack)이란?
• 스택은 LIFO(Last In, First Out) 구조로, 마지막에 들어간 데이터가 가장 먼저 나옵니다.
• 비유: 접시 쌓기 → 가장 위에 있는 접시를 먼저 꺼냄.
스택의 동작
1. Push: 데이터를 스택에 추가.
2. Pop: 가장 위의 데이터를 제거.
3. Peek/Top: 가장 위의 데이터를 확인.
2. 스택의 활용 사례
1) 함수 호출 관리 (Call Stack)
• 설명: 함수 호출 정보를 스택에 저장하여 실행 순서를 관리.
• 예: 재귀 함수에서 호출된 함수가 종료될 때, 호출 순서대로 스택에서 제거됩니다.
2) 문자열의 괄호 검사
• 설명: 올바른 괄호(() {} [])인지 확인.
• 예: 소스 코드의 구문 오류 검사.
def is_valid_parentheses(string):
stack = []
for char in string:
if char in "({[":
stack.append(char)
elif char in ")}]":
if not stack:
return False
top = stack.pop()
if char == ")" and top != "(":
return False
if char == "}" and top != "{":
return False
if char == "]" and top != "[":
return False
return not stack
3) 웹 브라우저의 뒤로가기
• 설명: 방문한 웹페이지를 스택에 저장하여 뒤로가기를 구현.
• 예: 사용자가 페이지 A → B → C를 방문.
• “뒤로가기” 버튼을 누르면 가장 최근 페이지 C를 스택에서 제거하고 B로 이동.
4) 문서 편집기에서 실행 취소 (Undo)
• 설명: 편집 기록을 스택에 저장하여 실행 취소를 구현.
• 예: “실행 취소(Undo)”를 누르면 가장 최근 작업을 스택에서 제거하고 이전 상태로 복구.
5) 깊이 우선 탐색 (DFS)
• 설명: 그래프 탐색 알고리즘에서 DFS는 스택을 사용하여 경로를 추적.
• 예: 미로 탐색, 네트워크 경로 분석.
3. 큐(Queue)란?
• 큐는 FIFO(First In, First Out) 구조로, 먼저 들어간 데이터가 가장 먼저 나옵니다.
• 비유: 줄 서기 → 먼저 온 사람이 먼저 나감.
큐의 동작
1. Enqueue: 데이터를 큐에 추가.
2. Dequeue: 큐의 앞에서 데이터를 제거.
3. Peek/Front: 큐의 앞에 있는 데이터를 확인.
4. 큐의 활용 사례
1) 프로세스 관리 (CPU 스케줄링)
• 설명: 운영체제에서 작업을 처리할 때 대기열을 사용하여 작업 순서를 관리.
• 예: FCFS (First Come, First Serve) 방식으로 작업 처리.
2) 네트워크 패킷 처리
• 설명: 네트워크에서 들어온 데이터 패킷을 큐에 저장하고 순서대로 처리.
• 예: 라우터가 데이터 패킷을 수신 → 큐에 저장 → 순차적으로 처리.
3) 프린터 작업 관리
• 설명: 프린터에 여러 작업이 들어오면 작업 요청을 큐에 저장하고 순서대로 처리.
• 예: 사용자 A → B → C가 프린트를 요청하면 A 작업이 끝난 후 B, C 작업을 순서대로 처리.
4) BFS(너비 우선 탐색)
• 설명: 그래프 탐색에서 BFS는 큐를 사용하여 레벨 순으로 탐색.
• 예: 최단 경로 찾기.
5) 대기열 시스템
• 설명: 고객 서비스나 병원 접수 시스템에서 대기열 관리.
• 예: 고객 번호표 발급 시스템.
6) 캐시 구현 (FIFO 캐시)
• 설명: 제한된 메모리 내에서 오래된 데이터를 제거하고 새 데이터를 추가.
• 예: FIFO 알고리즘 기반 캐시 시스템.
6. 스택과 큐의 Python 구현 예시
스택 구현 (Python)
stack = []
# Push
stack.append(1)
stack.append(2)
# Pop
print(stack.pop()) # 출력: 2
print(stack.pop()) # 출력: 1
큐 구현 (Python, collections.deque 사용)
from collections import deque
queue = deque()
# Enqueue
queue.append(1)
queue.append(2)
# Dequeue
print(queue.popleft()) # 출력: 1
print(queue.popleft()) # 출력: 2
'컴퓨터과학' 카테고리의 다른 글
[우선순위 큐와 힙] 효율적인 데이터 처리의 핵심! (0) | 2025.01.07 |
---|---|
[트리 구조와 이진 트리] 자료구조의 기초를 배우자! (0) | 2025.01.07 |
[배열과 리스트의 차이] 꼭 알아야 할 기본 자료구조 차이점 (0) | 2025.01.07 |
[컴파일러 vs 인터프리터] 차이점 완벽 정리! (0) | 2025.01.07 |
[알고리즘이란 무엇인가?] 프로그래밍의 기본, 알고리즘 이해하기 (1) | 2025.01.07 |