khon98 2020. 12. 9. 23:57

스택

- 스택(stack)은 한쪽으로 들어가서 한쪽으로 나오는 자료 구조(Data Structure)

- 이러한 특성 때문에 수식 계산 등의 알고리즘에서 다방면으로 활용됨

 

push : 스택에 데이터를 넣음

pop : 스택에서 데이터를 빼냄

 

push(7) - push(5) - push(4) - pop() - push(6) - pop()

7 5

 

스택의 구현

- 스택(stack)은 배열을 이용한 구현 방법과 연결 리스트를 이용한 구현 방법으로 나누어짐

- 가장 기본적인 형태의 자료구조로 구현 난이도는 낮은 편

 

배열을 이용한 스택 구현

* 스택의 선언

#define SIZE 10000 // 전체 스택의 크기
#define INF 99999999

int size[SIZE];
int top = -1; // 스택의 최 상단을 의미 하는 변수 top

 

* 스택 삽입 함수

- 오버플로우 : 데이터가 넘친다, 데이터가 들어갈 수 없을 만큼 스택이 가득 찼다

void push(int data) {
    if (top == SIZE - 1) { // 만약 top이 size -1이라면(9999라면)
        printf("스택 오버플로우 발생. \n");
        return;
    }
    stack[++top] = data;
}

 

* 스택 추출 함수

int pop() {
    if (top == -1) { // top이 -1이라면
        printf("스택 언더플로우 발생. \n");
        return -INF;
    }
    return stack[top--];
}

 

* 스택 전체 출력 함수

void show() {
    printf("--- 스택의 최상단 ---\n");
    for (int i = top; i >= 0; i--) {
        printf("%d\n", stack[i]);
    }
    printf("--- 스택의 최하단 ---\n");
}

 

* 완성된 스택 사용하기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10000 // 전체 스택의 크기
#define INF 99999999

int stack[SIZE];
int top = -1; // 스택의 최 상단을 의미 하는 변수 top

void push(int data) {
    if (top == SIZE - 1) { // 만약 top이 size -1이라면(9999라면)
        printf("스택 오버플로우 발생. \n");
        return;
    }
    stack[++top] = data;
}

int pop() {
    if (top == -1) { // top이 -1이라면
        printf("스택 언더플로우 발생. \n");
        return -INF;
    }
    return stack[top--];
}

void show() {
    printf("--- 스택의 최상단 ---\n");
    for (int i = top; i >= 0; i--) {
        printf("%d\n", stack[i]);
    }
    printf("--- 스택의 최하단 ---\n"); // 가장 먼저 들어온 값
}

int main(void) {
    push(7); // 가장 먼저 들어온 값
    push(5);
    push(4);
    pop();
    push(6);
    pop();
    show();
    system("pause");
    return 0;
}

 

연결 리스트를 이용한 스택 구현

* 스택의 선언

#define INF 99999999

typedef struct {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *top;
} Stack;

 

배열을 이용한 스택 구현

- 스택 삽입 과정

1. data next(Top) > data next(일반 노드) > data next(일반 노드) > null

2. data next(Top) > data next(일반 노드) > data next(일반 노드) > null

            data next(삽입할 노드)

3. data next(일반 노드) > data next(일반 노드) > data next(일반 노드) > null

            data next(Top)

 

* 스택 삽입 함수

void push(Stack *stack, int data) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->next = stack->top;
    stack->top = node;
}

 

- 스택 추출 과정

1. next(Top, 삭제할 노드) > data next(일반 노드) > data next(일반 노드) > null

2. next(삭제할 노드) > data next(Top, 일반 노드) > data next(일반 노드) > null

3. data next(Top, 일반 노드) > data next(일반 노드) > null

 

* 스택 추출 함수

void pop(Stack *stack) {
    if (stack->top == NULL) {
        printf("스택 언더플로우 발생.\n");
        return -INF;
    }
    Node *node = stack->top;
    int data = node->data;
    stack->top = node->next;
    free(node);
    return data;
}

 

* 스택 전체 출력 함수

void show(Stack *stack) {
    Node *cur = stack->top;
    printf("--- 스택의 최상단 ---\n");
    while (cur != NULL) {
        printf("%d\n", cur->data);
        cur = cur->next;
    }
    printf("--- 스택의 최하단 ---\n");
}

 

* 완성된 스택 사용하기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define INF 99999999

typedef struct {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *top;
} Stack;

void push(Stack *stack, int data) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->next = stack->top;
    stack->top = node;
}

void pop(Stack *stack) {
    if (stack->top == NULL) {
        printf("스택 언더플로우 발생.\n");
        return -INF;
    }
    Node *node = stack->top;
    int data = node->data;
    stack->top = node->next;
    free(node);
    return data;
}

void show(Stack *stack) {
    Node *cur = stack->top;
    printf("--- 스택의 최상단 ---\n");
    while (cur != NULL) {
        printf("%d\n", cur->data);
        cur = cur->next;
    }
    printf("--- 스택의 최하단 ---\n");
}

int main(void) {
    Stack stack;
    stack.top = NULL;
    show(&stack);
    push(&stack, 7);
    push(&stack, 5);
    push(&stack, 4);
    pop(&stack);
    push(&stack, 6);
    pop(&stack);
    show(&stack);
    system("pause");
    return 0;
}

 

 

- 스택은 배열 혹은 연결 리스트를 이용해서 구현할 수 있음