[자료구조 C 언어] C 프로그래밍 자료구조 - 7 : 연결리스트를 사용한 스택 (Stack)

이전 게시물 중에 배열을 사용하여 스택과 큐를 구현 했던 것을 기억하실 겁니다.

 

이번 시간에는 연결리스트를 사용하여 스택과 큐를 구현 해보겠습니다.

 

개념은 이전 자료를 참조해 주시고

 

이전 게시물 링크 => 2020/03/04 - [공부/c언어 자료구조] - [자료구조 C 언어] C 프로그래밍 자료구조 - 4 : 배열을 사용한 스택 (Stack)

 

 

바로 코드를 보면서 연결리스트를 사용하여 구현한 스택을 확인해 보겠습니다.

 

이번엔 바로 전체 코드와 함께하겠습니다.

 

1. 연결리스트를 사용한 스택 구현

 

이 색상의 주석은 게시물을 작성하며 추가한 주석입니다.

 

 

typedef struct NODE{ // 기본 노드 구조체는 연결리스트와 동일합니다.

    struct NODE *next;

    int data;

} Node;

 

typedef struct STACK{ // 스택의 맨 위 데이터(가장 최근에 들어온 데이터)를 가리키는 

                         top과 스택 내의 data 갯수를 저장하는 size를 포함하는 구조체입니다.

    Node *top; 

    int size;

} Stack;

 

Stack *InitStack(void){ // STACK 구조체 포인터를 선언하고, 반환해줍니다.

    Stack *stack = (Stack *)malloc(sizeof(Stack)); // STACK 구조체 포인터를 선언합니다.

    

    stack->top = NULL;    // 처음 top은 NULL로 저장되어있습니다.

    stack->size = 0;

    

    return stack;

}

 

void ResetStack(Stack *stack){ // 스택에 할당된 모든 메모리를 해제하고, 스택을 초기화 해줍니다.

    Node *tmp;

    Node *cur;

    

    cur = stack->top; // cur은 top과 동일합니다. 즉, 스택의 제일 윗 데이터입니다.

    

    while(cur != NULL){

        tmp = cur->next; // tmp에 cur 다음 노드를 저장합니다.

        free(cur);       // cur을 해제합니다.

        cur = tmp;       // cur에 cur 다음 노드를 저장합니다.

                         

    stack->top = NULL;  // top을 초기화 했을 때와 마찬가지로 NULL로 저장해줍니다.

    stack->size = 0;

 

}

 

 

void Push(Stack *stack, int data){ // 원하는 데이터를 스텍의 맨 위에 쌓아줍니다.

    Node *tmp = (Node *)malloc(sizeof(Node));

    

    tmp->data = data; // tmp(B라고 하겠습니다.)에 데이터를 저장합니다.

    tmp->next = stack->top; // tmp는 top(A라고 하겠습니다.)을 가리킵니다.

    

    stack->top = tmp; // top은 tmp가 되고, 새로운 top(B)은 이전 top(A)을 가리킵니다.

    

    ++stack->size;

}

 

void Pop(Stack *stack, int num){ // 원하는 갯수만큼 저장된 스택을 출력합니다.

    Node *tmp;

    Node *cur;

    

    cur = stack->top; // cur에 스택의 가장 윗 노드를 저장합니다.

    

    while(num--){  // num == n 일 때 반복문은 n번 시행됩니다.

        if(cur == NULL){

            puts("Stack is empty.\n");

            break;

        }

        else{

            printf("Stack(%d) data = %d\n", stack->size--, cur->data); // 데이터를 하나 뺏으므로 size를 하나 줄여준다.

 

            tmp = cur->next; // 데이터를 반환한 노드를 해제시키는 부분은 이전 ResetStack 함수와 동일합니다.

            free(cur);

            cur = tmp;

        }

    }

    

    stack->top = cur;

 

}

 

void PrintStack(Stack *stack){ // 스택의 모든 데이터를 출력합니다.

    Node *tmp = (Node *)malloc(sizeof(Node));

    

    tmp = stack->top;

    

    int size = stack->size;

    puts("\nPrinting stack starts.");

    while(tmp != NULL){

        printf("Stack (%d) data = %d\n", size--, tmp->data);

        tmp = tmp->next;

    }

    puts("Printing stack is complete.\n ");

}

 

int main(int argc, const char * argv[]) {

    

    Stack *stack = InitStack();

    

    Push(stack, 11);

    Push(stack, 12);

    Push(stack, 13);

    

    PrintStack(stack);

    

    Pop(stack, 1);

    Pop(stack, 2);

    //  세번째까지 잘 빠짐

    

    Pop(stack, 1);

    //  빈 stack 알림

    

    Push(stack, 11);

    Push(stack, 12);

    

    Pop(stack, 3);

    //  두번째까지 빠지고 다시 빈 stack 알림

    

    ResetStack(stack);

    

    Pop(stack, 3);

    

    Push(stack, 11);

    Push(stack, 12);

    

    Pop(stack, 3);

    return 0;

 

}

 

 

 

2. 프로그램 실행 결과

 

 

다음 게시물에선 연결리스트를 사용한 큐의 구현에 대해 설명드리겠습니다.