[Algorithm] C - 스택(Stack)

요약

• 데이터를 일시적으로 저장히기 위해 사용하는 자료구조로 한 곳에서만 입출력이 일어남
• 먼저 들어간 데이터는 마지막에 나오는 FIFO 구조 (First In - Last Out)
• 마지막에 들어간 데이터는 먼저 나오는 LIFO 구조 (Last In - First Out)
• 데이터를 담는 행위를 Push, 데이터를 추출하는 행위를 Pop이라고 함
• 중요 구조체 멤버로 저장할 메모리 공간, 현재 가리키는 위치, 최대 사이즈 3가지가 필요

스택(Stack)이란

스택은 바닥에서 부터 데이터를 쌓아 올리는 자료구조의 일종이며, 스택의 입/출력은 오로지 꼭대기에서만 이루어진다.
가장 먼저 들어간 데이터는 가장 나중에 나오는 구조이고(FILO First In - Last Out), 가장 마지막에 들어간 데이터는 가장 먼저 나오는 구조이다(LIFO Last In - First Out),

C언어에서 변수를 선언한 후 수명주기가 끝나면 변수를 자동 제거하는 메모리도 스택으로 구현되어 있다.
그래서 지역 변수는 스택에 할당된다고도 표현한다.

스택의 가장 중요한 부분은 요소의 삽입과 삭제가 한쪽 끝에서만 이루어지는 것이다.

스택은 네트워크 프로토콜, 컴파일러의 분석기, 이미지 편집 프로그램의 되돌리기 등 중요한 자료구조이다.

스택의 핵심 기능은 요소는 삽입하는 Push와 제거하는 Pop 연산 기능이다.
아래 이미지 중 왼쪽 이미지는 스택 맨 위에 새로운 요소를 담고(Push), 오른쪽 이미지는 나중에 들어온 데이터가 나가는(Pop) 이미지이다.

 

스택의 구조체

스택의 구조체는 간단하게 배열을 이용해 구성할 수 있다.
배열을 이용할 경우 용량을 동적으로 변경할 때 비용이 크지만, 쉽게 구현할 수 있다는 장점이 있다.

배열 기반의 스택은 각 노드를 동적으로 생성하고, 제거하는 대신, 스택 생성 초기에 사용자가 부여한 용량을 한꺼번에 생성한다.
그리고 최상위 노드의 위치를 나타내는 변수를 두고 삽입과 제거 연산을 수행한다.

스택의 구조체는 크게 3가지의 데이터 구조가 필요하다.

• 용량
• 최상위 노드의 위치
• 저장할 메모리

typedef struct _Stack
{
    int capacity;
    int top;
    int *buf;
} Stack;

capacity : 스택의 최대 용량을 나타내는 변수
top : 스택에 쌓여 있는 데이터를 나타내며, 비어 있을 경우 0(buf[0]), 가득 차 있을 경우 capacity(buf[top - 1]의 값과 같다.
buf : 스택으로 푸시된 데이터를 저장할 용도의 배열을 가리키는 변수로, Create 함수로 메모리 공간 할당을 한다.

스택의 함수

void Create(Stack* s, int capacity);        // 메모리 공간 초기화
int Push(Stack* s, int x);                 // 스택에 데이터 푸쉬
int Pop(Stack* s, int* x);                  // 스택에 데이터 팝
int Peek(const Stack* s, int* x);           // 스택 최상위 메모리 확인
void Clear(Stack* s);                       // 스택에 있는 모든 데이터 삭제
int Capacity(const Stack* s);               // 스택 용량 확인
int Size(const Stack* s);                   // 스택에 있는 데이터 수
int IsEmpty(const Stack* s);                // 스택이 비어 있는지 확인
int IsFull(const Stack* s);                 // 스택이 가득 찼는지 확인
int Search(const Stack* s, int x);          // 스택에서 데이터 검색
void Print(const Stack* s);                 // 스택 데이터 출력
void Terminate(Stack* s);                   // 스택 메모리 삭제

 

예제 코드

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

typedef struct _Stack
{
    int capacity;
    int top;
    int *buf;
} Stack;


int Create(Stack* s, int capacity);
int Push(Stack* s, int x);
int Pop(Stack* s, int* x);
int Peek(const Stack* s, int* x);
void Clear(Stack* s);
int Capacity(const Stack* s);
int Size(const Stack* s);
int IsEmpty(const Stack* s);
int IsFull(const Stack* s);
int Search(const Stack* s, int x);
void Print(const Stack* s);
void Terminate(Stack* s);

int main() 
{
    Stack s;
    int n;
    
    printf("생성할 메모리 사이즈 : ");
    scanf("%d", &n);
    
    if(Create(&s, n) == -1) {
        printf("스택 생성 실패\n");
        return 1;
    }
    
    while(1) {
        int menu, x;
        printf("현재 데이터 수 : [%d] / [%d]\n", Size(&s), Capacity(&s));
        
        printf("(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : ");
        scanf("%d", &menu);
        
        if(menu == 0) {
            printf("종료합니다.\n");
            break;
        }
        
        switch(menu) {
            // 푸쉬
            case 1:
            printf("데이터 : ");
            scanf("%d", &x);
            if(Push(&s, x) == -1) {
                printf("푸쉬에 실패하였습니다.\n");
            }
            break;
            
            // 팝
            case 2:
            if(Pop(&s, &x) == 1) {
                printf("팝에 실패하였습니다.\n");
            }
            else {
                printf("팝 데이터는 %d입니다.\n", x);
            }
            break;
            
            // 피크
            case 3:
            if(Peek(&s, &x) == 1) {
                printf("피크에 실패하였습니다.\n");
            }
            else {
                printf("피크 데이터는 %d입니다.\n", x);
            }
            break;
            
            // 출력
            case 4:
            Print(&s);
            break;
            
            default:
            printf("다시 입력해주세요.\n");
            break;
        }
    }
    
    Terminate(&s);

    return 0;
}

int Create(Stack* s, int capacity)
{
    //s->buf = calloc(capacity, sizeof(int));
    s->buf = malloc(sizeof(Stack) * capacity);
    s->top = 0;
    s->capacity = capacity;
}

int Push(Stack* s, int x)
{
    // 스택이 가득 차 있는지 확인
    if(s->top >= s->capacity) {
        printf("스택이 가득 찼습니다.\n");
        return -1;
    }
    
    // 스택에 푸쉬하여 데이터 증가
    s->buf[s->top++] = x;
    
    return 0;
}

int Pop(Stack* s, int* x)
{
    // 스택이 비어 있는지 확인
    if(s->top <= 0) {
        printf("스택이 비어 있습니다.\n");
        return -1;
    }
    
    // 스택에서 팝하여 데이터 감소
    *x = s->buf[s->top--];
    
    return 0;
}

int Peek(const Stack* s, int* x) 
{
    // 스택이 비어 있는지 확인
    if(s->top <= 0) {
        printf("스택이 비어 있습니다.\n");
        return -1;
    }
    
    // 최상위 데이터 확인
    *x = s->buf[s->top - 1];
    
    return 0;
}

void Clear(Stack* s)
{
    // 현재 가리키고 있는 top을 0으로 초기화
    s->top = 0;
}

int Capacity(const Stack* s)
{
    // 스택 최대 사이즈 
    return s->capacity;
}

int Size(const Stack* s)
{
    // 스택에 쌓여 있는 데이터 수
    return s->top;
}

int IsEmpty(const Stack* s)
{
    // 현재 가리키는 값이 최대 0보다 낮은지 확인
    return s->top <= 0;
}

int IsFull(const Stack* s)
{
    // 현재 가리키는 값이 최대 사이즈보다 높은지 확인
    return s->top >= s->capacity;
}

void Print(const Stack* s)
{
    int i;
    for(i = 0; i < s->top; i++) {
        printf("출력 데이터 [%d] %d\n: ", i, s->buf[i]);
    }
}

void Terminate(Stack* s)
{
    // 메모리가 비어 있지 않을 경우 소멸
    if(s->buf != NULL) {
        free(s->buf);
    }
    s->capacity = 0;
    s->top = 0;
}

 

실행 결과

생성할 메모리 사이즈 : 32
현재 데이터 수 : [0] / [32]
(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : 1
데이터 : 7
현재 데이터 수 : [1] / [32]
(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : 3
피크 데이터는 7입니다.
현재 데이터 수 : [1] / [32]
(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : 4
출력 데이터 [0] 7
: 현재 데이터 수 : [1] / [32]
(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : 2
팝 데이터는 0입니다.
현재 데이터 수 : [0] / [32]
(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : 0
종료합니다.

https://github.com/JeHeeYu/Algorithm/blob/main/Stack/stack.c

GitHub - JeHeeYu/Algorithm: 알고리즘 문제 풀이

 

출처 : 이것이 자료구조+알고리즘이다 with c 언어