[6] 스택 ①

스택

데이터를 일시적으로 저장하기 위해 사용하는 자료 구조로 데이터의 입력과 출력 순서는 후입 선출이다. 

스택: 후입 선출(LIFO, Last In First Out)

 

· 푸시: 스택에 데이터를 넣는 작업

· 팝: 스택에서 데이터를 꺼내는 작업

 

스택은 테이블에 쌓은 접시처럼 데이터를 넣고, 꺼내는 작업 모두 위 쪽부터 수행하며 팝을 하는 위치를 꼭대기(top)이라고 하며 스택의 가장 아래 부분을 바닥(bottom)이라고 한다.

 

일반적으로 사용되는 스택의 함수의 종류는 아래 코드를 참조한다.

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

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

/*스택 초기화*/
int Initialisze(IntStack *s,int max);

/*스택에 데이터를 푸시*/
int Push(IntStack *s,int x);

/*스택에 데이터를 팝*/
int Pop(IntStack *s,int *x);

/*스택에서 데이터를 피크*/
int Peek(IntStack *s,int *x);

/*스택 비우기*/
int Clear(IntStack *s);

/*스택의 최대 용량*/
int Capacity(IntStack *s);

/*스택의 데이터 개수*/
int Size(IntStack *s);

/*스택이 비어있는지의 유무*/
int isEmpty(IntStack *s);

/*스택이 가득 찼는지의 유무*/
int isFull(IntStack *s);

/*스택에서의 검색*/
int Search(IntStack *s,int max);

/*스택의 모든 데이터 출력*/
int Print(IntStack *s);

/*스택 종료*/
void Terminate(IntStack *s);

int main() {
}

스택 구조체 (IntStack)

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

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

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

스택 함수

스택을 다루는 함수를 이번 과정에서 알아보고 스택을 구현할 헤더를 만들기 위해 C언어 파일 상단에 다음과 같이 스택 선언을 한다.

 

// #ifndef ___IntStack #define ___IntStack

이때 ifndef는 "If not defined"의 약자로서 "~을 정의(define) 하지 않았다면"이라는 뜻이며 #define은 값을 치환해 주는 것이다.

자세한 전처리기에 대한 설명은 아래 포스팅을 참조한다.

C언어 #define, #if , #ifdef , #ifndef란

헤더 파일을 사용하기 위해서는 헤더 파일을 참조하는 파일과 같은 경로 상에 있어야 하며 include 함수를 통해 선언해줘야 한다. 이때 헤더 파일을 불러오는 기호는 <>가 아닌 "" 큰따옴표를 이용한다.

#include"IntStack.h"

스택 초기화 [ Initialisze ]

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

 

배열을 위한 메모리 공간을 만들 때 스택은 비어있어야 한다.(스택의 데이터 개수는 0이어야 한다.) 

따라서 스택 포인터 pst의 값을 0으로, 요소의 개수는 max인 배열 stk를 생성한다. 또한 매개 변수 max로 받은 값을 스택 최대 용량을 나타내는 구조체의 멤버인 max에 저장한다.

 

스택 초기화의 기본 알고리즘은 아래와 같다.

 

① 스택 포인터(스택의 데이터 개수)를 0으로 초기화

② 인자로 받은 스택의 최대 용량의 크기를 가진 배열 stk를 동적 할당하여 생성

③ 매개 변수 max로 받은 값을 동적 할당한 배열 stt가 가리키는 max에 저장한다.

 

코드는 아래의 [더보기] 란을 확인한다.

/*스택 초기화*/
int Initialisze(IntStack *stt,int max){
    stt->pst = 0;
    if((stt->stk = (int*)malloc(sizeof(int)*max) )==NULL){
        stt->max = 0; printf("스택 초기화에 실패하였습니다.");
        return -1;
    }
    stt->max = max;// 스택 용량 저장
    return 0;
}

푸시 함수 [ Push ]

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

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

스택 포인터가 최대 용량 값과 같다면 스택에는 더 이상 푸시할 수 없다.

 

코드는 아래의 [더보기] 란을 확인한다.

/*스택에 데이터를 푸시*/
int Push(IntStack *stt,int data){
    if(stt->pst >= stt->max) {printf("스택 푸시에 실패하였습니다.");return -1;}
    //스택의 현재 데이터 개수이 최대 용량 보다 큰 경우 종료
    stt->stk[stt->pst ++] = data;
    return 0;
}

팝 함수 [ Pop ]

Pop 함수는 스택의 꼭대기에서 데이터를 가져오는 함수이다. 제거하고 생각하지 말고 "가져온다"라고 생각하자.

팝에 성공할 경우 0을 반환하고 스택이 비어 팝을 할 수 없는 경우 -1을 반환한다.

 

Pop 함수는 구조체와 팝(값을 꺼낼) 꼭대기의 위치값이 주어진다. 팝 함수는 스택의 꼭대기 값을 가져오는 것이므로 get 포인터는 가장 윗 값을 저장하는 변수를 가리키며, *get에 저장 후에는 '저장 처리된' 값은 pst를 줄여 제거한다.

 

코드는 아래의 [더보기] 란을 확인한다.

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

피크 함수 [ Peek ]

Peek 함수는 스택의 꼭대기의 데이터를 확인하는 함수이다. 이는 꼭대기 값을 저장 후 삭제하지 않는 Pop 함수와 구조가 같다.

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

 

코드는 아래의 [더보기] 란을 확인한다.

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

서치 함수 [ Search ]

Search 함수는 임의의 값의 데이터가 스택의 어느 위치에 쌓여있는지 검사하는 함수이다. 검색에 성공하면 찾은 요소의 인덱스를 반환하고 실패하면 -1을 반환한다. 검색은 꼭대기의 데이터부터 바닥의 데이터로 후입 선출의 순서로 선형으로 진행한다.

 

코드는 아래의 [더보기] 란을 확인한다.

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

용량 함수 [ IsEmpty / IsFull ]

각각 스택이 비어있으면(데이터 개수가 0 이하) 1을 반환, 스택이 가득 찼으면 1, 아니면 0을 반환한다.

코드는 아래의 [더보기] 란을 확인한다.

/*스택이 비어있는지의 유무*/
int isEmpty(IntStack *stt){
    return (stt->pst <= 0);
    /*스택이 비어있으면(데이터 개수가 0 이하) 1을 반환*/
}

/*스택이 가득 차 있는지의 유무*/
int isFull(IntStack *stt){
    return (stt->pst >= stt->max);
    /*스탹이 가득 찼으면 1, 아니면 0을 반환*/
}

멤버 관리 함수 [ Capacity / Size ]

Capacity 함수는 스택의 최대 용량을 확인하며 Size 함수는 현재 스택에 쌓여있는 데이터의 개수를 반환하는 함수이다.

코드는 아래의 [더보기] 란을 확인한다.

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

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

출력 함수 [ Print ]

Print 함수는 스택의 모든 데이터를 출력하는 함수로 모든 데이터를 바닥부터 순서대로 출력한다.

코드는 아래의 [더보기] 란을 확인한다.

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

 

클리어 함수 [ clear ]

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

스택에 대한 처리는 스택 포인터인 pst를 바탕으로 이루어지므로, 스택의 배열 요솟값을 변경할 필요가 없으며 pst의 값을 0으로 하면 된다.

 

⭐️⭐️⭐️⭐️⭐️

물론 pst가 0이 아닌 값에 대한 배열 요솟값은 살아있으나 푸시 함수에서 새로운 값으로 대체되거나 스택 처리함수는 스택 개수인 pst를 바탕으로 처리되므로 스택의 배열 요솟값을 일일이 변경할 필요가 없다.

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

종료 함수 [ Terminate ]

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

코드는 아래의 [더보기] 란을 확인한다.

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

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