본문 바로가기

Datastructure/[Algorithm]

[자료구조] 스택의 활용: 배열

728x90
반응형

스택 함수의 기능

함수 이름 함수 설명
Initialisze 스택의 메모리 공간을 확보하는 등의 작업을 수행한다.
Push 스택에 데이터를 추가하는 함수이다..
스택이 가득 차지 않았다면 새로 추가할 데이터(data)를 배열의 요소 stk [num]에 저장하고 스택의 개수인(스택 포인터) num를 증가한다.
Pop 스택의 꼭대기에서 데이터를 제거하는 함수이다.
Peek 스택의 꼭대기의 데이터를 확인하는 함수이다.
스택이 비어있지 않으면 꼭대기 요소(stk [num-1])를 인자로 받은 pek이 가리키는 변수에 저장한다.
clear 인자로 받은 스택에 쌓여 있는 모든 데이터를 삭제한다.
Capacity 스택의 용량(max)을 확인하고 max의 값을 반환한다
Size 현재 스택에 저장된 데이터의 개수(num)를 반환한다.
IsEmpty 스택이 비어있는지 검사하는 함수이다. 
IsFull 스택이 가득 찼는지 검사하는 함수이다.
Search 임의의 값의 데이터가 스택의 어느 위치에 쌓여있는지 검사하는 함수이다.
Print 스택의 데이터를 모두 출력한다.
Terminate 스택을 해제하고 스택의 용량과 데이터 개수를 0으로 초기화한다.

스택 사용 프로그램

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

/*스택을 구현하는 구조체*/
typedef struct {
    int max; //스택용량
    int num; //스택에 쌓여있는 데이터의 개수(스택 포인터)
    int *stk;//스택의 첫 요소에 대한 포인터
}IntStack;

/*스택 초기화*/
int Initialisze(IntStack *stt,int max){
    stt->num = 0;
    stt->stk = malloc(max*sizeof(int));
    /*
    인자로 받은 스택 용량 만큼,
    인자로 받은 배열이 가리키는 스택의 첫 요소에 대한 포인터를 동적할당한다.
    */

    //동적할당 실패 시
    if((stt->stk)==NULL){stt->max = 0;return -1;}

    //동적할당 성공 시
    stt->max = max;
    return 0;
}

/*스택에 데이터를 푸시*/
int Push(IntStack *stt,int data){
    if(stt->num >= stt->max) return -1;
    //인자로 받은 배열의 스택에 쌓여있는 데이터의 개수가 용량보다 크거나 같으면 종료

    stt->stk[stt->num ++] = data;
    //인자로 받은 배열이 가리키는 배열의 num인덱스에 해당하는 공간에 데이터를 저장
    //이후 인덱스를 증가시킴
    return 0;
}

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

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

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

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

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

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

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

/*스택이 가득 찼는지의 유무*/
int isFull(IntStack *stt){
    return( stt-> num >= stt->max);
    //스택의 데이터 개수가 스택의 최대 용량보다 많으면 1 반환
    //스택의 데이터 개수가 스택의 최대 용량보다 적으면 0 반환
}

/*스택에서의 검색*/
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;
}

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

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

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

int main() {

}
728x90
반응형
댓글