해당 내용은 Do it! 자료구조와 함께 배우는 알고리즘 입문 C 언어 편 (전면 개정판)을 기반으로 작성되었습니다.
4-1장 스택과 큐 - 스택 Stack
스택 LIFO(Last In First Out)
- LIFO(Last In First Out) 구조를 가진 자료구조
스택 만들 때 작성해야하는 파일
- IntStack.h
- IntStack.c
- IntStackTest.c
스택 구조체 IntStack
- 스택을 관리하는 구조체
- IntStack은 3개의 멤버로 구성된다.
1. 스택으로 사용할 배열을 가리키는 포인터 stk
- 스택으로 푸시된 데이터를 저장할 용도의 배열을 가리키는 포인터
- 배열의 메모리 공간 할당은 Initialize 함수로 생성된다.
2. 스택의 최대 용량 max
- 스택의 최대 용량을 나타내는 int형 멤버
3. 스택 포인터 ptr
- 스택에 쌓여 있는 데이터의 개수를 나타내는 멤버
- 이 값을 스택 포인터(stack pointer)라 한다.
- 스택이 비어 있으면 ptr의 값은 0이고 가득 차 있으면 max이다.
스택 만들기
1. 초기화 함수 Initialize
- 스택의 메모리 공간(배열)을 확보하는 등의 준비 작업을 수행한다.
2. 푸시 함수 Push
- 스택에 데이터를 추가하는 함수
3. 팝 함수 Pop
- 스택의 꼭대기에서 데이터를 제거하는 함수
- 팝에 성공 시, 0 반환
- 스택에 비어있는 팝을 할 수 없는 경우 -1 반환
4. 피크 함수 Peek
- 스택 꼭대기의 데이터를 '몰래 엿보는' 함수
- 피크에 성공 시, 0 반환
- 스택이 비어 있어 피크할 수 없는 경우, -1 반환
5. 스택의 모든 요소를 삭제하는 함수 Clear
- 스택에 쌓여 있는 모든 데이터를 삭제하는 함수
6. 용량 확인 함수 Capacity
- 스택의 용향(멤버 max의 값)을 반환하는 함수
7. 데이터의 개수를 확인하는 함수 Size
- 현재 스택에 쌓여 있는 데이터의 개수(멤버 ptr의 값)를 반환하는 함수
8. 스택이 비어 있는지 검사하는 함수 IsEmpty
- 스택이 비어있는지 검사하는 함수
- 스택이 비어 있으면 1, 그렇지 않으면 0을 반환
9. 스택이 가득 찼는지 검사하는 함수 IsFull
- 스택이 가득 찼는지 검사하는 함수
- 스택이 가득 찼으면 1, 그렇지 않으면 0을 반환한다.
10. 임의의 값을 검색하는 함수 Search
- 임의의 값 x의 데이터가 스택의 어느 위치에 쌓여 잇는지 검사하는 함수
- 검색은 꼭대기에서 바닥으로 선형 검색을 수행한다.
- 꼭대기부터 검색하는 이유는 '먼저 팝되는 데이터'를 찾기 위함이다.
- 검색에 성공하면 찾은 요소의 인덱스를 반환, 실패하면 -1을 반환한다.
11. 모든 데이터를 출력하는 함수 Print
- 스택의 모든 데이터를 출력하는 함수
- 스택에 쌓여 있는 ptr개의 모든 데이터를 바닥부터 순서대로 출력한다.
12. 종료 함수 Terminate
- 뒤처리를 담당하는 함수
- Initialize 함수로 확보한 스택을 해제하고 용량 max와 스택 포인터 ptr의 값을 0으로 한다.
'SCHOOL > 알고리즘' 카테고리의 다른 글
3-3장 검색 알고리즘 - 복잡도 (3/5) (0) | 2024.04.30 |
---|---|
4-1장 스택과 큐 - 큐 Queue (ing) (1) | 2024.04.15 |
3-3장 검색 알고리즘 - 천장함수 (2/5) (0) | 2024.04.15 |
3-3장 검색 알고리즘 - 이진검색 (1/5) (1) | 2024.04.15 |
3-2장 검색 알고리즘 - 선형(순차)검색 | 보초법 검색 (5) | 2024.04.15 |