[자료구조][C] 스택(stack) (2)

먼저 스택을 전역변수(global variable)로 구현해보자. 여기서 전역변수란 중괄호 외부에 선언되는 변수다.

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef int element;
element stack[MAX_STACK_SIZE];
int top= -1;

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

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

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

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

element peek(void)
{
    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;
}

👩🏻‍💻 ❓

typedef int element;

c언어에서 'typedef' 키워드를 사용하면 기존의 데이터 타입에 새로운 이름을 부여할 수 있다. 'typedef'를 사용하는 이유는 크게 1) 코드의 가독성 2) 모듈화 증가 3) 데이터 타입의 변경을 쉽게 하기 위함이다.

 

위와 같은 경우 int 대신에 element를 사용함으로써 코드의 의미를 더 명확하게 표현할 수 있다. 예를 들어 element 라는 이름을 사용하면 해당 변수가 어떤 의미를 가지는지 더 쉽게 이해할 수 있다. 또한 typedef를 사용하여 복잡한 데이터 타입을 간소화하거나 추상화 할 수도 있다. 구조체나 포인터 타입 등을 typedef를 사용하여 간단한 이름으로 정의하면 코드가 더 간결해지며 가독성이 높아진다. 

 

그러나 스택을 전역변수로 만들게 되면 스택에 저장되는 값이 정수나 문자가 아니고 복잡한 구조를 갖는 요소일 경우(학번, 이름, 주소 등의 정보) 스택에 구조체를 저장하는 편이 용이하다. 

 

스택을 구조체로 정의해보도록 하자.

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
#define MAX_STRING 100

typedef struct {
    int student_no;
    char name[MAX_STRING];
    char address[MAX_STRING];
}element;

element stack[MAX_STACK_SIZE];
int top=-1;

int is_empty(void)
{
    return (top==-1);
}

int is_full(void)
{
    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--];
}

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

int main() {
    element ie={
        202135970,
        "배소현",
        "seongnam"
    };
    element oe;
    
    push(ie);
    oe=pop();
    
    printf("학번: %d\n",oe.student_no);
    printf("이름: %s\n",oe.name);
    printf("주소: %s\n",oe.address);
}

👩🏻‍💻 ❓

 

element oe;
push(ie);
oe = pop();

main 함수에서는 ie라는 구조체에 값을 넣고 push 함수를 호출하여 데이터를 저장한 다음, pop 함수를 호출하여 데이터를 가져와 oe 구조체에 저장하고 있다. 그 후에 printf 함수를 호출하여 oe 구조체의 멤버들을 호출하고 있다. 이로 인해 스택에 저장된 데이터가 스택 내에서 처리되고 oe 변수에 꺼내온 데이터가 저장된다. 

 

push(ie);
printf("학번: %d\n", ie.student_no);
printf("이름: %s\n", ie.name);
printf("주소: %s\n", ie.address);

위와 같은 코드는 push 함수를 호출하여 ie 데이터를 스택에 저장하고, 바로 이어서 ie의 멤버에 직접 접근하여 출력하는 경우이다. 이 경우 스택에 저장된 데이터를 꺼내어 처리하는 단계 없이 , ie 멤버들을 직접 접근하여 사용하는 것이다.

 

일반적으로 첫번째 방안이 더 많이 사용되는데 데이터를 스택에 저장하고 나중에 꺼내어 사용하는 과정을 더 명확하게 표현하고 있기 때문이다. 또한 스택에 저장하고 나중에 처리하는 방식은 스택 자료구조의 원래 목적과도 일치하므로 코드의 의도를 더 명확하게 전달할 수 있다. 

 

그러나 위와 같은 방안은 스택 배열과 top이 전역변수로 선언되기 때문에 하나의 프로그램에서 여러 개의 스택을 사용하지 못한다는 단점을 지닌다. 프로그램의 모듈화와 이름 충돌 때문인데 예를 들어 여러개의 스택을 동시에 사용하게 되면 각각의 스택은 각각의 목적과 데이터를 가지게 된다. 이때 스택의 배열과 top이 전역변수이기 때문에 어떠한 스택인지 구분할 수 없다. 따라서 top과 스택의 배열을 하나의 구조체로 결합시키고 구조체의 포인터를 함수로 전달하면 해결된다. 즉, stackType이라는 새로운 구조체 타입을 만들고 여기에 stack 배열과 top을 넣어준다. 

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
#define MAX_STRING 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)--];
}

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

int main(){
    
    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));
}

👩🏻‍💻 ❓

여기서 달라진 점은 StackType의 포인터 s 를 변수로 모두 전달해야한다는 것이다. 

왜냐하면 함수 내부에서 해당 스택을 조작하고 수정해야하기 때문이다. 함수가 호출될 때 매개변수로 전달된 스택을 참조하여 스택의 상태를 변경하거나 읽어올 수 있다. 함수 내부에서 s를 통해 스택의 멤버들에 접근 할 수 있어서 스택을 관리하고 사용할 수 있다.

 

c언어에서 함수에 매개변수를 전달할 때, 매개변수는 값에 의한 복사가 이루어지기 때문에 함수 내에서 매개변수에 대한 수정이 원본 변수에 영향을 미치지 않는다. 따라서 함수 내부에서 원본 스택을 조작하기 위해 포인터를 사용하여 전달해야 한다. 만약 매개변수로 값만 전달한다면 함수 내부에서 스택을 수정하는 작업이 원본 스택에 반영되지 않을 것이다. 

 

동적 메모리 할당을 이용하면 함수를 보다 자연스럽게 표현할 수 있다. 

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
#define MAX_STRING 100

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-1));
}

void push(StackType* s,element item){
    if(is_full(s)){
        s->capacity *= 2;
        s->data=(element*)realloc(s->data,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(){
    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));
    free(s.data);
    return 0;
}

👩🏻‍💻 ❓

동적할당을 사용하기 때문에 메모리 해지를 꼭꼭 해주어야한다. 

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

realloc 함수

push 함수가 가장 변화가 크다. 스택이 차 있는지 확인하고 차있을 경우 동적 배열의 크기를 늘려주는 부분을 추가한다. 스택의 용량을 동적으로 조정하여 스택의 크기를 늘릴 수 있게 된다. realloc 함수를 사용하여 메모리를 재할당하고 스택의 data 배열의 크기를 s-> capacity a만큼 늘려준다.