Data-Structure - Stack

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
#define MAX_STACK_SIZE 100
#define ERROR_KEY -100
 
#define MALLOC(p, s)                            \
    if (!((p) = malloc(s)))                     \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }
 
#define REALLOC(p, s)                           \
    if (!((p) = realloc(p, s)))                 \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }
 
typedef struct
{
    int key;
} element;
 
int top = -1;
int capacity = 1;
 
element *stack;
 
void stackFull()
{
    REALLOC(stack, 2 * capacity * sizeof(*stack));
    capacity *= 2;
}
 
element stackEmpty()
{
    element errorElement;
    errorElement.key = ERROR_KEY;
    fprintf(stderr, "Stack is empty, cannot pop element\n");
    return errorElement;
}
 
/* add an item to the global stack */
void push(element item)
{
    if (top >= MAX_STACK_SIZE - 1)
        stackFull();
 
    stack[++top] = item;
}
 
/* delete and return the top element from the stack */
element pop()
{
    if (top == -1)
        return stackEmpty();
    return stack[top--];
}
 
void popAndprint(element item)
{
    int key = pop().key;
    if (key != ERROR_KEY)
    {
        printf("%d\n", key);
        return;
    }
    return;
}
 
int main(void)
{
    MALLOC(stack, sizeof(*stack));
    element newElement = {1};
    push(newElement);
    newElement.key = 3;
    push(newElement);
    newElement.key = 2;
    push(newElement);
 
    printf("\n============================\n");
 
    popAndprint(newElement);
    popAndprint(newElement);
    popAndprint(newElement);
    popAndprint(newElement);
 
    return 0;
}

간단하기 c언어를 통해서 스택을 구현하였습니다.

메모리의 효율성을 위하여 초기 스택의 용량을 1로 설정하였습니다.

그리고 만약 스택의 top값이 MAX_STACK_SIZE - 1값에 도달하면 꽉찼다는 의미이므로 capacity를 2배로 올려주고 realloc을 통해서 메모리를 재할당 해 주었습니다. 위의 main함수 결괏값은 아래와 같습니다.

정상적으로 LIFO의 정책이 성립함을 알 수 있습니다.