[자료구조] 스택(stack) 이란?

스택

---

스택(stack) - 쌓아놓은 더미, 한쪽 끝에서 자료를 넣거나 뺄 수 있는 선형 자료구조, 후입선출(Last-In First-Out)구조로 가장 최근에 들어온 데이터가 가장 먼저 나간다. 

• push - 스택에 데이터 추가
• pop - 스택에서 데이터 삭제 

 

● 스택의 연산

• create() - 스택 생성

• is_full(s) - 스택이 포화상태인지 검사

• is_empty(s) - 스택이 공백상태인지 검사

• push() - 스택에 데이터 추가

• pop() - 스택에서 데이터 삭제 

• peek(s) - 요소를 스택에서 제거하지 않고 보기만 하는 연산

 

● 배열을 이용한 스택 구현

배열을 이용해 스택을 구현해 봅시다 ㅎㅎ

1차원 배열을 이용해 스택을 구현할 거고, 위에 적은 연산을 각각 함수로 구현할 겁니다!

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

#define Max_STACK_SIZE 100 // 스택 최대 크기 100
typedef int element;
element stack[Max_STACK_SIZE]; // 1차원 배열로 크기100인 스택 만들기
int top = - 1;

// 공백 상태 검출 함수
int is_empty() {
    return (top == -1);
}

// 포화 상태 검출 함수
int is_full() {
    return (top == (Max_STACK_SIZE - 1));
}

// 삽입 함수
void push(element item) {
    if (is_full()) {
        fprintf(stderr, "스택 포화 에러 \n");
        return;
    } else {
        stack[++top] = item;
    }
}

element pop(){
    if (is_empty()) {
        fprintf(stderr, "스택 공백 에러 \n");
        exit(1);
    } else {
        return stack[top--];
    }
}

int main(void){
    push(1);
    push(2);
    push(3);
    printf("%d\n", pop());
    printf("%d\n", pop());
    printf("%d\n", pop());
    return 0;
}

출력 결과: 3, 2. 1 

 

만약 앞서 배운 구조체를 사용한다면 다음과 같이 작성할 수 있습니다. 

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

#define MAX_STACK_SIZE 100
typedef int element;

typedef struct {
    element data[MAX_STACK_SIZE];
    int top;
} StackType;

void init_stack(StackType *s){
    s -> top = -1;
}

int is_empty(StackType *s) {
    return (s -> top == -1);
}

int is_full(StackType *s) {
    return (s -> top == MAX_STACK_SIZE -1);
}

void push(StackType *s, element item) {
    if (is_full(s)) {
        fprintf(stderr, "스택 포화 에러 \n");
        return;
    }else {
        s -> data[++(s->top)] = item;
    }
}

element pop(StackType *s){
    if(is_empty(s)){
        fprintf(stderr, "스택 공백 에러 \n");
        exit(1);
    }else {
        return s -> data[(s -> top)--];
    }
}

int main(void) {
    StackType s;
    
    init_stack(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
}

출력 결과: 3, 2. 1 

 

● 동적 배열 스택

기존에는 일정한 공간의 스택을 미리 만들어 놓고 사용했습니다. 만약 스택에 공간 100을 할당했는데 실제로 사용은 10~20만 사용한다면 메모리 낭비가 너무 심하죠? 그래서 이번에는 스택 메모리 공간이 꽉 찼을 때 새로 메모리를 할당하는 동적 배열 스택을 구성하여 메모리 관리 효율성을 높여보려 합니다.

malloc은 메모리를 할당할 때, realloc은 이미 할당한 메모리 공간을 바꿀 때 사용합니다.

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

typedef int element;

typedef struct {
    element *data;
    int capacity;
    int top;
} StackType;

void init_stack(StackType *s){
    s -> top = -1;
    s -> capacity = 1;
    s -> data = (element *)malloc((s -> capacity)*sizeof(element));
}

int is_empty(StackType *s) {
    return (s -> top == -1);
}

int is_full(StackType *s) {
    return (s -> top == s -> capacity);
}

void push(StackType *s, element item) {
    if (is_full(s)) {
        s -> capacity *= 2;
        s -> data = (element *)realloc(s -> data, sizeof(s -> capacity*sizeof(element)));
    }
    
    s -> data[++(s->top)] = item;
    
}

element pop(StackType *s){
    if(is_empty(s)){
        fprintf(stderr, "스택 공백 에러 \n");
        exit(1);
    }else {
        return s -> data[(s -> top)--];
    }
}

int main(void) {
    StackType s;
    
    init_stack(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
}

출력 결과: 3, 2. 1 

스택에 대한 개념 설명과 구현 방법은 이것으로 마치고, 다음 포스팅에서 스택의 응용에 대해 다뤄 보겠습니다.

읽어주셔서 감사합니다 :)