[자료구조] Stack (feat. C 언어)

 

정의

 

스택(stack)은 자료 구조 중 선형 구조에 해당되며 한쪽 끝에서 자료의 삽입, 삭제가 모두 일어나는 후입선출(LIFO : Last In Fisrt Out) 방식으로 이루어져 있다. 자료를 삽입할 때는 push라고 하며 반대로 삭제할 때는 pop이라고 한다. 

 

 

후입선출(LIFO : Last In Fisrt Out) 방식

 

 

특징

 

• 선형 구조
• 후입선출(LIFO : Last In Fisrt Out)
• 삽입 - push, 삭제 - pop
• 함수 호출의 순서 제어, 인터럽트의 처리, 수식 계산 및 수식 표기법 등

 

연산

 

스택의 구조

 

• push 연산 : 스택이 비어있는 경우 추가되는 데이터는 바로 top이 되며 포인터는 null값을 가진다. 스택에 데이터가 추가될 때 추가되는 노드가 가리키는 포인터는 현 스택 top의 주소이며 이후 top은 자기 자신이 된다.

 

push 연산

 

• pop 연산 : 데이터를 삭제 할 시 삭제되는 노드가 가리키는 주소의 노드가 top이 되며 삭제되는 노드는 free 함수를 통해 메모리를 해제한다.

 

pop 연산

 

 

구현

 

• init_stack 함수 : 스택 초기화

 

void init_stack(struct Stack* stack) // stack 이니셜라이징
{
    stack->top = NULL;
}
 

• push 함수 : 스택에 데이터 삽입

 

void push(struct Stack* stack, int data) // data를 stack에 넣어주는 함수, 이 때 주체는 top
{
    struct Node_stack* node = (struct Node_stack*)malloc(sizeof(struct Node_stack));
 
    if (stack->top != NULL) // stack에 data가 있는 경우
    {
        node->next = stack->top;
    }
    
    node->data = data;
    stack->top = node;
}

 

• pop 함수 : 스택에서 데이터 삭제 후 데이터 값 반환

 

int pop(struct Stack* stack) // data를 stack에서 제거해주는 함수, data는 LIFO 형식(Last In First Out) : 맨 나중에 들어온 data가 맨 첫번째로 제거 된다.
{
    if (stack->top == NULL) // stack이 비어있는 경우
    {
        printf("남은 data가 없습니다.\n");
        return 0;
    }
 
    struct Node_stack* node = stack->top;
    int data = node->data;
    stack->top = node->next;
    free(node);
    return data;
}

 

• get_top : 스택의 top 위치에 있는 데이터 값 반환

 

int get_top(struct Stack* stack) // top에 위치해있는 data 얻는 함수
{
    struct Node_stack* node = stack->top;
    return node->data;
}

 

• 전체 구조

 

struct Node_stack {
 
    int data;
    struct Node_stack* next;
};
 
 
struct Stack {
 
    struct Node_stack* top;
};
 
 
void push(struct Stack* stack, int data);
int pop(struct Stack* stack);
int get_top(struct Stack* stack);
void init_stack(struct Stack* stack);
 
 
void init_stack(struct Stack* stack) // stack 이니셜라이징
{
    stack->top = NULL;
}
 
 
void push(struct Stack* stack, int data) // data를 stack에 넣어주는 함수, 이 때 주체는 top
{
    struct Node_stack* node = (struct Node*)malloc(sizeof(struct Node_stack));
    node->data = data;
    node->next = stack->top;
    stack->top = node;
}
 
 
int pop(struct Stack* stack) // data를 stack에서 제거해주는 함수, data는 LIFO 형식(Last In First Out) : 맨 나중에 들어온 data가 맨 첫번째로 제거 된다.
{
    if (stack->top == NULL) // stack이 비어있는 경우
    {
        printf("남은 data가 없습니다.\n");
        return 0;
    }
 
    struct Node_stack* node = stack->top;
    int data = node->data;
    stack->top = node->next;
    free(node);
    return data;
}
 
 
int get_top(struct Stack* stack) // top에 위치해있는 data 얻는 함수
{
    struct Node_stack* node = stack->top;
    return node->data;
}