본문 바로가기
[알고리즘 + 자료구조]

[자료구조] STACK

by Hevton 2020. 10. 14.
반응형

배열로 구현 예시 (요소는 int형)

 

 

[ IntStack.h ]

//
//  Intstack.h
//  helloC
//
//  Created by Hevton on 2020/10/14.
//

/* int형 스택 IntStack 헤더 */
#ifndef Intstack_h
#define Intstack_h

typedef struct {
    int max; // 스택의 최대 용량
    int ptr; // 새로운 데이터를 삽입할 인덱스를 가리키는 스택 포인터. 포인터 변수를 의미하지 않으며, '인덱스를 가리킨다'라는 의미로 그렇게 부름. 특별한 경우가 아닌 이상 스택에 쌓여 있는 데이터의 개수를 나타내기도 함.
    int *stk; // 스택으로 사용할 배열을 가리키는 포인터
} IntStack;

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

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

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

// 스택에서 데이터를 피크(top에 위치하는 요소 확인)
int Peek(const IntStack *s, int *x);

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

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

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

// 스택이 비어있나요?
int IsEmpty(const IntStack *s);

// 스택이 가득 찼나요?
int IsFull(const IntStack *s);

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

// 모든 데이터를 출력
void Print(const IntStack *s);

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


#endif /* Intstack_h */

 

[ IntStack.c ]

//
//  IntStack.c
//  helloC
//
//  Created by Hevton on 2020/10/14.
//
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"

// 스택 초기화
int Initialize(IntStack *s, int max)
{
    s->ptr = 0;
    if((s->stk = calloc(max, sizeof(int))) == NULL) {
        s->max = 0; // 배열의 생성에 실패
        return -1;
    }
    
    s->max = max;
    return 0;
}

// 스택에 데이터를 푸시
// 스택이 가득 차서 푸시할 수 없는 경우 -1 반환, 스택에 푸시 성공하면 0을 반환
int Push(IntStack *s, int x)
{
    // == 연산자를 사용해도 되나, 프로그램의 오류나 사용자의 의도적인 잘못된 값 입력 등의 이유로 ptr 값이 잘못 입력되어 max값을 초과하는 경우가 생길 우려를 으레 막아놓음으로써, 프로그램의 안정성을 높일 수 있다.
    if(s->ptr >= s->max) // 스택이 가득 참
        return -1;
    
    s->stk[s->ptr++] = x;
    return 0;
}

// 스택에서 데이터를 팝
// 스택이 비어 있어 팝 할수 없는 경우 -1 반환, 팝에 성공할 경우 0을 반환
int Pop(IntStack *s, int *x)
{
    if(s->ptr <=0) // 스택이 비어 있음
        return -1;
    
    *x = s->stk[--s->ptr];
    return 0;
}

// 스택에서 데이터를 피크(top에 위치하고 있는 데이터를 열람)
// 스택이 비어 있으면 -1 반환, 피크에 성공하면 0을 반환
int Peek(const IntStack *s, int *x)
{
    if(s->ptr<=0) // 스택이 비어있음
        return -1;
    
    *x = s->stk[s->ptr-1];
    return 0;
}

// 스택 비우기
// 배열 요소들을 변경할 필요 없음. ptr을 0으로.
void Clear(IntStack *s)
{
    s->ptr = 0;
}

// 스택 용량
// max의 값 반환
int Capacity(const IntStack *s)
{
    return s->max;
}

// 스택에 쌓여 있는 데이터의 수
// ptr의 값 반환
int Size(const IntStack *s)
{
    return s->ptr;
}

// 스택이 비어 있는가?
// 스택이 비어 있으면 1, 그렇지 않으면 0 반환
int IsEmpty(const IntStack *s)
{
    return s->ptr <= 0;
}

// 스택이 가득 찼는가?
// 스택이 가득 찼으면 1, 그렇지 않으면 0 반환
int IsFull(const IntStack *s)
{
    return s->ptr >= s->max;
}

// 스택에서 검색
// 검색에 성공하면 찾은 요소의 인덱스를 반환, 실패하면 -1을 반환
int Search(const IntStack *s, int x)
{
    int i;
    for(i = s->ptr-1; i>=0; i--) { // top -> bottom 방향으로 선형 검색
        if(s->stk[i] == x)
            return i; // 검색 성공
    }
    return -1; // 검색 실패
}

// 모든 데이터를 출력
void Print(const IntStack *s)
{
    int i;
    for(i = 0; i < s->ptr; i++) // bottom -> top 방향으로 출력
        printf("%d ", s->stk[i]);

    putchar('\n');
}

// 스택 종료
void Terminate(IntStack *s)
{
    if(s->stk!=NULL)
        free(s->stk); // 배열을 삭제
    
    s->max = s->ptr = 0;
}


 

[ main.c ]

#include <stdio.h>
#include "IntStack.h"

int main() {
    IntStack s;
    
    if(Initialize(&s, 64) == -1) {
        puts("스택 생성에 실패했습니다.");
        return 1;
    }
    
    while(1) {
        int menu, x;
        printf("현재 데이터 수 : %d / %d\n", Size(&s), Capacity(&s));
        printf("(1)푸시 (2)팝 (3)피크 (4)클리어 (5)최대 용량 (6)데이터 개수 (7)스택이 비어있는지 (8)스택이 가득 찼는지 (9)검색 (10)출력 (0)종료 : ");
        scanf("%d", &menu);
        
        if(menu == 0) break;
        switch(menu) {
            case 1: // 푸시
                printf("데이터 : ");
                scanf("%d", &x);
                
                if(Push(&s, x) == -1)
                    puts("\a오류 : 푸시에 실패했습니다.");
                break;
                
            case 2: // 팝
                if(Pop(&s, &x) == -1)
                    puts("\a오류 : 팝에 실패했습니다.");
                else
                    printf("팝 데이터는 %d입니다.\n", x);
                break;
                
            case 3: // 피크
                if(Peek(&s, &x) == -1)
                    puts("\a오류 : 피크에 실패했습니다.");
                else
                    printf("피크 데이터는 %d입니다\n", x);
                break;
                
            case 4: // 클리어
                Clear(&s);
                break;
                
            case 5: // 최대 용량
                printf("스택의 최대 용량은 %d입니다.\n", Capacity(&s));
                break;
                
            case 6: // 데이터 개수
                printf("현재 스택의 데이터 개수는 %d개 입니다.\n", Size(&s));
                break;
                
            case 7: // 스택이 비어있는지
                if(IsEmpty(&s))
                    puts("스택이 비어있습니다.");
                else
                    puts("스택이 비어있지 않습니다.");
                break;
                
            case 8: // 스택이 가득 찼는지
                if(IsFull(&s))
                    puts("스택이 가득 차 있습니다.");
                else
                    puts("스택이 가득 차 있지 않습니다.");
                break;
                
            case 9: // 검색
                printf("검색할 데이터 : ");
                scanf("%d", &x);
                int data = Search(&s, x);
                if(data!= -1)
                    printf("검색한 데이터는 s[%d]에 있습니다.\n", data);
                else
                    puts("데이터가 존재하지 않습니다.");
                break;
                
            case 10: // 출력
                Print(&s);
                break;
        }
    }
    Terminate(&s);
    return 0;
}
반응형

'[알고리즘 + 자료구조]' 카테고리의 다른 글

[자료구조] Queue  (0) 2020.10.15
[자료구조] 다중 STACK  (0) 2020.10.14
[알고리즘] 이진 검색  (0) 2020.10.11
[알고리즘] 선형 검색  (0) 2020.10.11
[알고리즘] Insert sort  (0) 2020.10.05