4. 스택 - 스택의 구현 / 배열을 이용한 스택 구현 / 스택 추출함수/ 전체 출력 함수 / 연결 리스트를 이용한 스택 구현 / 스택 선언 / 스택 삽입 과정

스택(Stack)

스택 자료구조의 개념과 활용 방법에 대해서 이해한다. C언어를 이용해 스택 자료구조를 직접 구현해 본다.

스택은 수식계산, 다양한 알고리즘 분야 등에서 활용도가 높기 때문에, 반드시 숙지해야 후에 나오는 심화 과정에서 어려움이 없다.

스택은 한쪽으로 들어가서 한쪽으로 나오는 자료 구조이다. 이러한 특성 때문에 수식 계산 등의 알고리즘에서 다방면으로 활용 되므로 반드시 알고 있어야 하는 자료구조이다. 스택에 데이터를 넣는 push함수와 스택에서 데이터를 빼내는 pop 함수를 이용한다.

'리스트'의 형태를 가지기 때문에, 마치 배열처럼 표현 할 수 있다. 연결리스트 혹은 배열을 이용해 구현 가능하다.

 

스택의 구현

스택은 배열을 이용한 구현 방법과 연결 리스트를 이용한 구현 방법으로 나누어져있다. 가장 기본적인 형태의 자료구조로 구현 난이도는 낮은 편이다.

 

배열을 이용한 스택 구현

스택의 선언

#include<stdio.h>
#define Size 1000
#define INF 999999

int stack[Size];
int top = -1;

배열이므로, 전체 스택의 크기를 미리 정한다. 그후 무한대라고 표현할 수 있는 값을 정의해 준다. 크기에 맞는 스택 배열을 만들고, 스택의 최상단을 의미하는 변수 top을 전역변수로서 선언한다.

스택 삽입 함수

void push(int data){
    if (top == Size-1){
        printf("스택 오버플로우가 발생했습니다.\n");
        return;
    }
    stack[++top] = data;
}

더이상 원소가 들어갈 수 없는경우(미리 설정한 배열의 크기를 넘어가는 경우) 예외 처리를 한다(return을 해주는 이유는 오류 발생시 뒤의 코드가 실행되지 않기 위함이다.)

스택 추출 함수

void pop(){
    if (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(1);
    push(2);
    push(3);
    push(4);
    push(5);
    pop();
    push(6);
    show();
    system("pause");
    return 0;
}

---스택의 최상단---
6
4
3
2
1
---스택의 최하단---

 

 

#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;
}

int 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;
}

현재 스택이 비어있다면, 문제가 발생했음을 알릴 수 있는 예외처리를 한다. 그리고, 현재의 최상단 노드(top)를 잠깐 담을 수 있는 node를 만든다. node에 담긴 data를 int형 data를 정의해 추출해낸다. 2번째 노드가 최상단 노드가 되도록 하고, node를 할당해제한다. 이 pop함수는 int형 데이터를 리턴하는 함수이므로, pop함수를 정의할 때 int형으로 선언한 것을 볼 수 있다.

void show(Stack *stack){
    if(stack->top == NULL){
        printf("출력할 값이 없습니다\n");
        return -INF;
    }
    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;
    push(&stack,4);
    push(&stack,3);
    push(&stack,2);
    pop(&stack);
    push(&stack,1);
    show(&stack);
    system("pause");
    return 0;
}

---스택 최상단---
1
3
4
---스택 최하단---

스택변수를 만든 후, 반드시 top에 NULL값을 넣어야 한다. 이는 스택의 언더플로우나 show()함수에서 루프문을 체크하기 위함이다. 위의 함수들에선 stack을 모두 포인터로서 사용하여 정의하였는데,  메인 함수에서는 stack을 Stack형 변수로서 선언하였으므로, 함수에 인자로서 넣을 때 반드시 주소연산자 (&)를 넣어 사용한다.

 

요약

1. 스택은 배열 혹은 연결 리스트를 이용해 구현할 수 있다.
2. 수식계산, 다양한 알고리즘 분야등에서 활용도가 높기 때문에, 반드시 숙지해야한다.