[3] 스택

스택 자료구조에 대해 알아보고, 이를 직접 구현하며 자세히 알아보겠습니다.

 

스택은 자료구조의 한 종류로, 나중에 입력한 정보를 가장 먼저 꺼낼 수 있는 구조를 갖는 자료구조입니다. 이러한 구조를 LIFO (Last In First Out) 라고 합니다. 

 

항상 넣은 순서의 반대로 꺼낼 수 있게 한쪽 방향이 막혀있습니다. 

Stack의 의미를 생각해보면, 무언가가 쌓여있는 것을 생각하게 되는데,

쌓여있는 것의 맨 마지막 것 부터 뺄 수 없는것과 같은 이치입니다. 

 

스택을 구현한다는 것은, 한쪽으로만 꺼낼 수 있는 구조를 만들어 주는 것이라고 볼 수 있겠습니다. 

 

구현

구현은 Array로 해도 되고 Linked List로 해도 되지만, 이 글에선 Linked List를 이용하여 구현합니다. 

typedef struct node_t { // node 구조체 정의
    int val;
    struct node_t * next;
} node;

typedef struct stack_t { // Stack 구조체 정의
    struct node_t * front;
    int size;
} Stack;

우선 node와 Stack 타입을 정의해줍니다. 

node는 저장할 값과 다음 node로의 포인터를 저장합니다.

Stack은 스택의 가장 맨 위에 있는 node를 가리키는 front와 스택의 사이즈를 저장합니다. 

 

Stack * CreateStack(){ 
    // Stack을 생성하고, 그 포인터를 리턴

    Stack * newStack = (Stack *)malloc(sizeof(Stack));

    if(newStack==NULL){
        printf("Fail when creating Stack pointer");
        return NULL;
    }

    newStack->front = NULL;
    newStack->size = 0;

    return newStack;
}

스택을 생성하는 함수를 만듭니다. 스택의 크기에 해당하는 메모리를 할당한 후 

front와 size 값을 초기화 한 후 포인터를 리턴합니다. 

 

node * CreateNode(int val){
    // node를 생성하고, 그 포인터를 리턴

    node * newNode = (node *)malloc(sizeof(node));
    if(newNode == NULL){
        printf("Fail when creating new node pointer");
        return NULL;
    }
    newNode->val = val;
    newNode->next = NULL;

    return newNode;
}

노드를 생성하는 함수를 만듭니다. 값을 넣으면 node에 해당하는 메모리를 동적 할당하여 리턴합니다. 

 

void stackPush(Stack * stack, int val){
    // stack과 값을 넣으면 해당 stack에 값을 넣어줌

    node * newNode = CreateNode(val);
    if(newNode == NULL) return;

    if(stack->front == NULL) stack->front = newNode;
    else{
        newNode->next = stack->front;
        stack->front = newNode;
    }

    stack->size++;
}

스택에 Push 합니다. 스택과 넣을 값을 입력하면

함수 내에서 node를 생성하고, 현재 front에 있는 node를 생성한 node가 가르키게 하고,

생성한 node를 front로 지정합니다. 

그 후 스택의 사이즈를 증가시킵니다. 

 

int stackPop(Stack *stack){
    int ret = stack->front->val;
    node * del = stack->front;

    stack->front = stack->front->next;
    free(del);
    stack->size--;
    return ret;
}

스택에 Pop 합니다. 스택을 입력하면

스택의 맨 첫번쨰 요소를 꺼내서 리턴하고 스택에서 제거해야 합니다. 

스택의 "맨 위"에있는 요소가 가르키는 요소를 "맨 위"로 올려주고

기존에 "맨 위"였던 요소를 제거해줍시다.

물론 값은 반환해야 합니다. 

 

void PrintStackState(Stack *stack){
    node * nodePtr = stack->front;
    int i = stack->size;
    printf("Stack's total size : %d\n", i);
    while(nodePtr != NULL){
        printf("Stack's %dth floor value : %d\n", i, nodePtr->val);
        nodePtr = nodePtr->next;
        i--;
    }
}

스택에 있는 모든 요소를 탐색하고 싶다면

각 node가 가리키고 있는 요소들을 하나씩 탐색해주면 됩니다. 

 

자료구조의 가장 기초가 되는 스택에 대해 알아보았습니다 :)