[자료구조] 연결리스트로 구현한 스택(stack)

1. 연결된 스택(Linked Stack)

스택은 First In First Out (FIFO) 형태의 자료구조이다. 

연결된 스택은 스택을 배열이 아닌 연결리스트로 구현한 것이다.

겉으로 보기에는 배열로 구현한 것과 별 차이가 없지만

연결리스트로 구현할 경우 동적 메모리 할당을 하기 때문에 메모리 크기에 제한받지 않는다.

다만 구현이 조금 까다롭다(라고 보통 말하던데 까다로운가..? 잘 모르겠다..)

 

2. 삽입 연산(push)

삽입을 할 경우 새로 만든 노드의 링크는 현재 스택의 top이 가리키는 링크가 되게 하고

그리고 새로 만든 노드가 top이 되게 하면

새로 만든 노드가 가장 위에 있는 스택 구조가 된다.

void push(LinkedStackType *s){
    int data;
    StackNode* new_node;
    
    printf("push data : ");
    scanf("%d", &data);
    
    //새로운 노드 만들기
    new_node = (StackNode*)malloc(sizeof(StackNode));
    new_node->data = data;
    
    //새로운 노드 연결하기
    new_node->link = s->top; //새로운 노드의 link가 현재 top이 가리키는 노드를 연결한다.
    s->top = new_node; //새로운 노드가 top이 된다.
}

 

3. 삭제 연산(pop)

삭제 연산의 경우 top이 가리키는 노드의 다음 링크가 top이 되게 구현하면 된다.

//공백 상태인지 확인하는 함수
int is_empty(LinkedStackType *s){
    return s->top == NULL; //top이 NULL인지 확인
}

//삭제하는 함수
void pop(LinkedStackType *s){
    StackNode *temp = s->top;
    
    if(!is_empty(s)){
        printf("pop data : %d\n", temp->data);
        s->top = s->top->link;
        free(temp);
    }else{
        printf("no data\n");
    }
}

(1. 내가 만든 코드는 현재 top이 가리키는 노드의 데이터를 peek하고 delete하는 형태로 만들었다.)

2. 스택을 연결리스트로 구현했으니 메모리의 제한을 받지 않으므로

배열로 구현했을 때처럼 is_full과 같은 함수가 없는데 반면

삭제 연산은 현재 top이 NULL인지를 확인하는 is_empty 함수를 같이 구현했다.)

 

<<전체 코드>>

//이중 연결 리스트
#include <stdio.h>
#include <stdlib.h>

//스택 노드 타입 선언
typedef struct stackNode{
    int data;
    struct stackNode* link;
}StackNode;

typedef struct{
    StackNode *top;
}LinkedStackType;

//공백 상태 확인 함수
int is_empty(LinkedStackType *s){
    return s->top == NULL;
}

//스택 삽입
void push(LinkedStackType *s){
    int data;
    StackNode* new_node;
    
    printf("push data : ");
    scanf("%d", &data);
    
    new_node = (StackNode*)malloc(sizeof(StackNode));
    new_node->data = data;
    
    new_node->link = s->top;
    s->top = new_node;
}

//스택 삭제
void pop(LinkedStackType *s){
    StackNode *temp = s->top;
    
    if(!is_empty(s)){
        printf("pop data : %d\n", temp->data);
        s->top = s->top->link;
        free(temp);
    }else{
        printf("no data\n");
    }
}

//스택 출력
void print_stack(LinkedStackType *s){
    StackNode *temp;
    
    for(temp=s->top; temp != NULL; temp=temp->link){
        printf("%d ", temp->data);
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    int menu;
    
    LinkedStackType s;
    s.top = NULL;
    
    do{
        printf("========================\n");
        printf("1.push 2.pop 3.print 4.end\n");
        printf("========================\n");
        printf("menu : ");
        scanf("%d", &menu);
        
        if(menu == 1){
            push(&s);
        }else if(menu == 2){
            pop(&s);
        }else if(menu == 3){
            print_stack(&s);
        }
    }while(menu != 4);
}