4-1장 스택과 큐 - 스택 Stack

 

해당 내용은 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으로 한다.