1. 스택의 개념
1) 스택(Stack)
• 접시를 차곡차곡 쌓아 올리듯이 자료를 하나씩 쌓아 올린 형태의 자료구조.
• 가장 먼저 입력된 데이터는 맨 아래에 놓이고, 이후 입력된 데이터가 위로 쌓이는 구조.
• 스택의 맨 위에는 가장 최근에 입력된 데이터가 놓이며, 맨 위의 데이터만 입출력 가능.
• 중간에서는 데이터를 삽입하거나 삭제할 수 없음.
• 스택에서 입출력이 이루어지는 부분을 스택 상단(top), 바닥 부분을 **스택 하단(bottom)**이라고 함.
• 후입선출(LIFO: Last-In First-Out) 구조
- 마지막에 삽입(Last-In)된 데이터가 가장 먼저 삭제(First-Out)됨.
2) 스택의 구조
• 스택에 데이터가 A, B, C, D, E 순으로 삽입되면, 삭제 시에는 E, D, C, B, A 순으로 제거됨.
3) 스택의 연산
• push: 데이터를 삽입할 때 top의 값을 증가(top+1)시킴.
• pop: 데이터를 삭제할 때 top의 값을 감소(top-1)시킴.
4) 공백과 포화 상태
• 공백(empty) 상태: 스택에 데이터가 없는 경우.
• 포화(full) 상태: 더 이상 데이터를 삽입할 수 없는 경우.
5) 오버플로우와 언더플로우
• 오버플로우(overflow): 스택이 가득 찬 상태에서 추가 삽입이 발생하는 경우.
• 언더플로우(underflow): 스택이 비어 있는 상태에서 삭제 연산이 발생하는 경우.
6) 스택의 주요 동작
• push: 새로운 데이터를 top 위에 삽입.
• pop: top이 가리키는 데이터를 삭제.
• 스택이 비어 있는지 또는 가득 차 있는지를 확인하는 동작 필요.
2. 스택의 구현 방법
1) 스택 구현 방식
• 배열을 이용한 구현.
• 연결 리스트를 이용한 구현.
2) 배열로 구현한 스택
• 간단하게 구현 가능하지만 크기가 고정되어 있음.
• 사용 중 스택 크기 변경이 어려움.
• 메모리 효율성이 떨어질 수 있음.
• 스택의 top은 배열의 오른쪽 끝에 위치.
- 공백 상태: top = -1
- 포화 상태: top = n-1 (n은 배열의 크기)
3) 연결 리스트로 구현한 스택
• 크기 제한 없이 유연한 리스트 구현 가능.
• 삽입과 삭제 연산이 쉽게 이루어짐.
• 연결 리스트의 헤드 포인터를 top 포인터로 사용.
• 오버플로우 문제를 쉽게 해결 가능.
4) 시스템 스택
• 프로그램 실행 중 함수 호출과 복귀를 관리하기 위해 사용하는 스택.
• 함수 호출 시 필요한 정보를 스택 프레임에 저장하여 관리.
• 가장 마지막에 호출된 함수가 가장 먼저 실행을 마치고 복귀하는 후입선출 구조.
5) 함수 호출과 복귀 과정
(1) 프로그램 실행 시 main() 함수 실행.
(2) main() 함수의 실행 정보를 시스템 스택에 삽입.
(3) main() 함수 실행 중 F_1() 함수 호출 → **F_1()**의 정보를 스택에 삽입.
(4) F_1() 실행 중 F_2() 함수 호출 → **F_2()**의 정보를 스택에 삽입.
(5) F_2() 실행 종료 → **F_1()**으로 복귀.
(6) F_1() 실행 종료 → **main()**으로 복귀.
(7) main() 종료 시 스택이 공백 상태가 됨.
6) 함수 호출의 처리
• 시스템 스택은 함수 호출 시 필요한 정보를 저장하는 역할.
• 함수 호출 시 지역 변수, 매개변수, 복귀 주소 등을 스택 프레임에 저장.
7) 순환 호출의 처리
• 함수가 자기 자신을 호출하는 순환 호출도 스택을 통해 처리.
• 순환 호출 시마다 새로운 스택 프레임이 생성됨.
• 메모리 소모가 크므로 주의 필요.
3. 스택의 삽입과 삭제
1) 스택의 추상적 자료구조
• 스택에서 가장 중요한 연산은 push와 pop.
2) 스택의 추상 자료형
• 데이터: 후입선출(LIFO) 방식으로 접근하는 요소들의 집합.
• 연산
- init(): 스택 초기화.
- is_empty(): 스택이 비어 있으면 TRUE 반환.
- is_full(): 스택이 가득 차 있으면 TRUE 반환.
- size(): 스택 내 데이터 개수 반환.
- push(x): 데이터 x를 스택 top에 삽입.
- pop(): 스택 top 데이터를 삭제 후 반환.
- peek(): 스택 top 데이터를 삭제하지 않고 반환.
이 내용은 휴넷사회복지평생교육원의 자료구조 강의를 듣고 정리한 것입니다.
'CS > 자료구조' 카테고리의 다른 글
| [자료구조] 10. 큐 (0) | 2025.03.31 |
|---|---|
| [자료구조] 9. 스택의 응용 (0) | 2025.03.30 |
| [자료구조] 7. 이중 연결 리스트 (0) | 2025.03.18 |
| [자료구조] 6. 단순 연결 리스트 (0) | 2025.02.25 |
| [자료구조] 5. 연결 리스트 (0) | 2025.02.24 |
