[스택과 큐] #2. 스택 함수

스택 구조체: IntStack

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

/*스택을 구현하는 구조체*/
typedef struct {
    int max; //스택용량
    int num; //스택 포인터
    int *stk;//스택의 첫 요소에 대한 포인터
}IntStack;

• 스택을 관리하는 구조체. 3개의 멤버로 구성된다.

stk	스택으로 사용할 배열을 가리키는 포인터 stk
	> 스택으로 푸시된 데이터를 저장할 용도의 배열을 가리키는 포인터 > 배열의 메모리 공간 할당은 Initialisze함수를 통해 생성된다.
max	스택의 최대 용량을 나타내는 멤버. 배열 stk의 요소 개수와 같다.
num	스택에 쌓여있는 데이터의 개수를 나타내는 멤버. 이 값을 스택 포인터라고 한다.
	> 가장 먼저 푸시된 바닥의 데이터는 stk[0], 가장 나중에 푸시된 꼭대기의 데이터는 stk[num-1]

이때 스택의 데이터 개수(num)와 스택의 최대 용량(max)은 엄연히 다르다.

스택의 데이터 개수는 현재 스택에 저장된 값들의 개수를 의미하여, 스택의 최대 용량은 스택이 최대로 가질 수 있는 데이터의 개수를 말한다. 따라서 스택의 최대 용량을 넘지 않는 한 스택의 데이터 개수는 증감이 가능하다.

스택 초기화: Initialisze

Initialisze 함수는 스택의 메모리 공간을 확보하는 등의 작업을 수행한다.

 

배열을 위한 메모리 공간을 만들 때 스택은 비어있어야한다.(스택의 데이터 개수는 0이어야 한다.) 따라서 스택 포인터 num의 값을 0으로, max인 배열 stk를 생성한다. 또한 매개 변수 max로 받은 값을 스택 최대 용량을 나타내는 구조체의 멤버인 max에 저장한다.

1. 스택 포인터(스택의 데이터 개수)를 0으로 초기화
2. 인자로 받은 스택의 최대 용량의 크기를 가진 배열 stk를 동적 할당하여 생성
3. 매개 변수 max로 받은 값을 동적 할당한 배열 stt가 가리키는 max에 저장한다.

/*스택 초기화*/
int Initialisze(IntStack *stt,int max){
    stt->num = 0;
    //동적할당 실패 시
    if((stt->stk = malloc(max*sizeof(int)))==NULL){
        stt->max = 0;
        return -1;
    }
    //동적할당 성공 시
    stt->max = max;
    return 0;
}

푸시 함수 Push

Push 함수는 스택에 데이터를 추가하는 함수로, 스택이 가득 차서 푸시를 할 수 없는 경우에는 -1을 반환한다.

스택이 가득 차지 않았다면 새로 추가할 데이터(data)를 배열의 요소 stk [num]에 저장하고 스택의 개수인(스택 포인터) num를 증가한다.

 

푸시 성공	새로 추가할 데이터(data)를 배열의 요소 stk[num]에 저장 후 0 반환
푸시 실패	-1 반환

/*스택에 데이터를 푸시*/
int Push(IntStack *stt,int data){
    if(stt->num >= stt->max) return -1;

    stt->stk[stt->num ++] = data;
    return 0;
}

IntStack.C 에서 제공하는 함수만 사용하여 스택 작업을 수행하면 스택 포인터 prt 값은 반드시 0 이상 max이하가 된다.

따라서 아래의 코드처럼 스택이 가득 찼는지에 대한 검사는 등가 연산을 이용해도 무방하다.

if(s->prt==s->max)

팝 함수 Pop

Pop 함수는 스택의 꼭대기에서 데이터를 제거하는 함수(연결 리스트의 delete와 유사하다).

 

팝 성공	스택의 개수(스택 포인터)를 1 감소하고 삭제한 값을 함수의 인자인 del이 가리키는 변수에 저장 후 0 반환
팝 실패	-1 반환

/*스택에 데이터를 팝 == 꺼냄*/
int Pop(IntStack *stt,int *del){
    if(stt->num <= 0) return -1;
    //스택에서 꺼낼 수 있는 수가 0보다 작거나 같으면 종료
    
    *del = stt->stk[stt->num --];
    //인자로 받은 배열이 가리키는 배열의 num 인덱스에 해당하는 데이터 값을 포인터 del의 참조값으로 저장
    //이후 인덱스를 감소하고 종료
    return 0;
}

피크 함수 Peek

Peek 함수는 스택의 꼭대기의 데이터를 확인하는 함수이다.

스택이 비어있지 않으면 꼭대기 요소(stk [num-1])를 인자로 받은 pek이 가리키는 변수에 저장한다.

 

이때, 꼭대기 요소가 stk [num]이 아닌 stk [num-1]인 이유는 num이 0부터 이기 때문이다.(C언어의 배열을 따른다.)

 

피크 성공	0 반환
피크 실패	-1 반환

/*스택에서 데이터를 피크*/
int Peek(IntStack *stt,int *pek){
    if(stt->num <= 0) return -1;
    //스택에서 꺼낼 수 있는 수(== 확인할 데이터 값)가 0보다 작거나 같으면 종료
    *pek = stt->stk[stt->num -1];
    //인자로 받은 배열이 가리키는 배열의 (num-1) 인덱스에 해당하는 값을 포인터 pek의 참조값을 저장
    return 0;
}

초기화 함수 Clear

clear 함수는 인자로 받은 스택에 쌓여 있는 모든 데이터를 삭제한다.

/*스택 비우기*/
int Clear(IntStack *stt){
    stt->num = 0;
    //스택의 개수를 0으로 초기화 -> 검사할 수 있는 스택이 0이 됨.
    //이때 스택의 개수와 스택의 최대 용량은 다르다!
}

스택 최대 용량 확인 함수 Capacity

Capacity 함수는 스택의 용량(max)을 확인하고 max의 값을 반환한다.

/*스택의 최대 용량*/
int Capacity(IntStack *stt){return stt->max;}
//스택의 최대 용량을 반환

데이터의 개수 확인 함수 Size

Size 함수는 현재 스택에 저장된 데이터의 개수(num)를 반환한다.

/*스택의 데이터 개수*/
int Size(IntStack *stt){return (stt->num);}

스택의 저장 상태 확인 함수 IsEmpty

IsEmpty 함수는 스택이 비어있는지 검사하는 함수이다. 

 

스택이 비어있는 경우	1 반환(스택이 비어있는지 검사하므로 비어있다면 1)
스택이 차 있는 경우	0 반환

/*스택이 비어있는지의 유무*/
int isEmpty(IntStack *stt){
    return (stt->num <= 0);
    //스택의 데이터 개수가 0보다 작거나 같으면 1
    //스택의 데이터 개수가 0보다 크면 1

    //스택이 비어있으면(데이터 개수가 0 이하) 1을 반환
}

스택의 과저장 유무 확인 함수 IsFull 

IsFull 함수는 스택이 가득 찼는지 검사하는 함수이다.

 

스택이 가득 차 있는 경우	1 반환
스택이 가득 차 있지 않은 경우	0 반환

스택 데이터를 검사하는 함수 Search

Search 함수는 임의의 값의 데이터가 스택의 어느 위치에 쌓여있는지 검사하는 함수이다.

검색은 꼭대기의 데이터부터 바닥의 데이터로 후입 선출의 순서로 선형으로 진행한다.

/*스택에서의 검색*/
int Search(IntStack *stt,int key){
    //스택의 개수만큼 꼭대기에서 부터 선형 검색
    for(int i=(stt->num)-1;i>=0;i--){
        if(key == stt->stk[i]) return i;
        /**
        인자로 받은 검색값과 일치하는 
        stt가 가리키는 배열의 데이터가 있을 시 해당 인덱스 반환
         */
    }
    return - 1;
}

데이터 출력 함수 Print

/*스택의 모든 데이터 출력*/
int Print(IntStack *stt){
    for(int i=0;i<stt->num;i++) printf("%d ",stt->stk[i]);
    //스택의 데이터 수 만큼 반복하여 스택의 데이터를 출력
    printf("\n");
}

스택 종료 함수 Terminate

Terminate 함수는 스택을 해제하고 스택의 용량과 데이터 개수를 0으로 초기화한다.

/*스택 종료*/
void Terminate(IntStack *stt){
    if(stt->stk != NULL) free(stt->stk);
    //스택의 배열이 NULL이 아닌 경우 스택의 동적할당된 배열을 해제

    stt->max = stt->num = 0 ;
    //스택의 최대 용량과 스택의 데이터 수를 0으로 초기화
}

스택_프로그램.c

0.00MB

IntStack.h

0.00MB