[자료구조] 4. 스택(Stack)

4. 스택(Stack)

스택의 구조

 

정의

• LIFO(Last In First Out) 구조를 가진 자료구조
• 마지막에 삽입된 데이터가 가장 먼저 삭제되는 방식

 

종류

1. 배열 기반 스택 (Array-based Stack)
2. 연결 리스트 기반 스택 (Linked-based Stack)
3. 순환 스택 (Circular Stack)

 

기본 구조

1. 요소
2. 스택 포인터 (Top) : 스택의 맨 위 요소를 가리키는 포인터

 

특징

1. LIFO(Last In First Out) 구조
2. 제한된 접근 방식 : 삽입과 삭제는 항상 스택의 맨 위에서 이루어짐
3. 크기 : 배열로 구현한 스택은 고정 크기, 연결 리스트로 구현한 스택은 가변 크기를 가짐
4. 재귀적 문제 해결에 유리

 

활용 예시

1. 함수 호출 스택 : 프로그래밍 언어에서 함수 호출 시 각 함수의 지역 변수와 실행 상태가 스택에 저장되고, 함수가 종료될 때 호출한 함수로 되돌아갈 수 있음
2. 경로 탐색 및 되돌아가기 기능 : 웹 브라우저의 뒤로 가기 기능이나 파일 탐색기에서의 경로 탐색
3. 문자열 뒤집기 : ABCD → DCBA

 

장단점

 

장점

1. 간단한 구현과 효율적인 연산 : Push, Pop 등의 기본 연산이 간단하고 효율적
2. LIFO 구조의 활용 : 재귀적 문제 해결과 함수 호출 관리에 적합
3. 메모리 관리 유리 : 데이터 추가 시 포인터가 이동하므로 데이터를 덮어쓰지 않으므로 메모리 관리가 단순함
4. 안전한 데이터 처리 : 예상치 않은 데이터 접근 방지

 

단점

1. 유연하지 않은 데이터 접근 : 스택은 맨 위에서만 데이터를 삽입 및 삭제할 수 있음
2. 오버플로우(Overflow) 발생 가능성 : 메모리 사이즈를 초과할 경우 오버플로우 발생할 수 있음

 

연산과 시간 복잡도

연산	설명	연산 절차	시간 복잡도
Push	스택에 데이터 추가	스택의 Top 위치에 데이터 삽입	O(1)
Pop	스택의 맨 위 데이터 제거	Top 위치의 데이터 제거 후 Top 감소	O(1)
Peek	스택의 맨 위 데이터 확인	Top 위치의 데이터 반환	O(1)
isEmpty	스택이 비었는지 확인	Top 위치가 초기 값인지 확인	O(1)
isFull	(배열 기반 스택) 스택이 가득 찼는지 확인	Top 위치가 배열 최대 인덱스인지 확인	O(1)