[자료구조] 연결리스트를 통한 스택(Stack) 구현 - C

스택(Stack)

 

 

 

 스택은 위 그림과 같이 겹겹이 쌓이는 구조를 뜻한다.

 

각 함수에 대해서 간략하게 설명하겠다.

 

 

isEmpty()

스택이 비어있는지 확인하는 함수

• 비어있다면 1을 반환
• 비어있지 않다면 0을 반환

 

isFull()

스택이 가득 차있는지 확인하는 함수

• 연결리스트를 활용한 스택 구현에서는 필요 X
• 연결리스트는 계속해서 연결이 가능하기 때문

 

Push()

값을 삽입하는 함수

• 새로운 노드를 생성하여 값을 저장하고, 기존 연결리스트에 연결한다.

 

Pop()

값을 삭제, 반환하는 함수

• 마지막 노드의 값을 임시로 저장해두고, 삭제한 후에 임시로 저장한 값을 반환한다.

 

printData()

연결리스트에 연결된 값들을 차례로 출력하는 함수

 

 

 

구현한 코드

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

typedef struct _stack {
    int data;
    struct _stack *link;
} Stack;

int isEmpty(Stack* head) {
    return (head == NULL);
}

void Push(Stack** head, int data) {
    Stack *newnode = (Stack *)malloc(sizeof(Stack));
    newnode->data = data;
    newnode->link = *head;
    *head = newnode;
}

int Pop(Stack **head) {
    if (isEmpty(*head)) {
        printf("스택이 비어있습니다.\n");
        exit(1);
    }
    Stack *temp = *head;
    int return_data = temp->data;
    *head = (*head)->link;
    free(temp);
    return return_data;
}

void printData(Stack* head) {
    Stack *cur = head;
    while (cur != NULL) {
        printf("%d -> ", cur->data);
        cur = cur->link;
    }
    printf("\n");
}

int main(void) {
    Stack *stack = NULL; 

    printData(stack);
    Push(&stack, 1);
    Push(&stack, 2);
    Push(&stack, 3);
    printData(stack);

    printf("Popped: %d\n", Pop(&stack));
    printData(stack);

    printf("Popped: %d\n", Pop(&stack));
    printData(stack);

    printf("Popped: %d\n", Pop(&stack));
    printData(stack);

    return 0;
}

 

 

 

실행 결과

 

 

 

 

 

 

 

 

 

 

스택 이미지 출처 - https://www.google.com/url?sa=i&url=https%3A%2F%2Fhong-devbox.tistory.com%2F4&psig=AOvVaw0jT9wNLIy8hAakmi6aHWWj&ust=1722474577682000&source=images&cd=vfe&opi=89978449&ved=0CBQQjhxqFwoTCIi47fyL0IcDFQAAAAAdAAAAABAE

리디렉션 알림