[자료구조(C언어] 스택(Stack) 구현하기 2

※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다.

---

해결 1

스택이 동시에 2개 이상 필요한 경우,

하나의 함수를 여러 개의 스택에 공통으로 사용할 수 있도록 함수를 작성한다

→ 스택을 매개변수로 넘겨 처리한다

 

1) 배열로 구현

stackADT.h (헤더파일)

#ifndef STACKADT_H
#define STACKADT_H

#include <stdbool.h> /* C99 only */

typedef int Item;

typedef struct stack_type *Stack;

Stack create();
void destroy(Stack s);
void make_empty(Stack s);
bool is_empty(Stack s);
void push(Stack s, Item i);
Item pop(Stack s);
Item peek(Stack s);

#endif

typedef int Item;

만약 스택에 int가 아닌 다른 타입의 데이터를 저장하고 싶다면, 함수의 매개변수 타입, 리턴 타입 등을 일일히 바꾸는 대신에 위 선언만 수정해주면 된다. (→ 코드의 재사용성을 높임)

 

typedef struct stack_type *Stack;

struct stack_type의 포인터를 Stack이라고 부르기로 한다

 

stackADT.c (소스코드 파일)

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

#define INIT_CAPACITY 100

/* 스택 관련 변수들을 묶어서 구조체로 만들기 */
struct stack_type {
    // 배열 이름 contents, 배열 크기 size, 변수 top
    Item *contents;
    int top;
    int size;
}; 


/* 예외 상황 처리 */
static void terminate(const char *message) 
{
    printf("%s\n", message);
    exit(1);
}


/* 스택 생성 */
Stack create()
{
    Stack s = (Stack)malloc(sizeof(struct stack_type));
    if (s==NULL)
        terminate("Error in create: stack could not be created. ");
    s->contents = (Item *)malloc(INIT_CAPACITY*sizeof(Item));
    if (s->contents == NULL) {
        free(s);
        terminate("Error in create: stack could not be created. ");
    }
    s->top = -1;
    s->size = INIT_CAPACITY;
    return s;
}

void destroy(Stack s) 
{
    free(s->contents);
    free(s);
}

void make_empty(Stack s)
{
    s->top = -1;
}

bool is_empty(Stack s)
{
    return s->top == -1;
}

void push(Stack s, Item i)
{
    if (is_full(s))
        reallocate(s);
    s->top++;
    s->contents[s->top] = i;
}

Item pop(Stack s)
{
    if (is_empty(s))
        terminate("Error in pop: stack is empty.");
    s->top--;
    return s->contents[s->top+1];
}

Item peek(Stack s)
{
    if (is_empty(s))
        terminate("Error in pop: stack is empty.");
    return s->contents[s->top];
}

void reallocate(Stack s)
{
    Item *tmp = (Item *)malloc(2*s->size*sizeof(Item));
    if (tmp == NULL) {
        terminate("Error in create: stack could not be created.");
    }
    for (int i=0; i<s->size; i++)
        tmp[i] = s->contents[i];
    free(s->contents);
    s->contents = tmp;
    s->size *= 2;
}

 

사용 예 (main 함수)

int main()
{
	Stack s1 = create();
	Stack s2 = create();

	push(s1, 12);
	push(s2, 9);
	...
	pop(s1);

	destroy(s1);

}

 

 

2) 연결리스트로 구현

동일한 헤더파일 사용, 소스코드 파일만 연결리스트로 수정한다.

 

stackADT2.c

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

struct node {
    Item data;
    struct node *next;
};

struct stack_type {
    struct node *top;
};

static void terminate(const char *message)
{
    printf("%s\n", message);
    exit(EXIT_FAILURE);
}

Stack create()
{
    Stack s = malloc(sizeof(struct stack_type));
    if (s == NULL)
        terminate("Error in create: stack could not be created.");
    s->top = NULL;
    return s;
}

void destroy(Stack s)
{
    make_empty(s);
    free(s);
}

void make_empty(Stack s)
{
    while (!is_emptly(s))
        pop(s);
}

bool is_empty(Stack s)
{
    return s->top == NULL;
}

void push(Stack s, Item i)
{
    struct node *new_node = malloc(sizeof(struct node));
    if (new_node == NULL)
        terminate("Error in push: stack is full.");
    new_node->data = i;
    new_node->next = s->top;
    s->top = new_node;
}

Item pop(Stack s)
{
    struct node *old_top;
    Item i;

    if (is_empty(s))
        terminate("Error in pop: stack is empty.");
    
    old_top = s->top;
    i = old_top->data;
    s->top = old_top->next;
    free(old_top);
    return i;
}

Item peek(Stack s)
{
    if (is_empty(s))
        terminate("Error in peek: stack is empty.");
        
    return s->top->data;
}

 

해결 2

해결 1에서는 1가지 타입의 데이터만을 저장할 수 있고,

데이터 타입이 달라지면 Item 타입 정의를 수정해야하므로 서로 다른 타입의 데이터를 저장하는 2개의 스택을 만들 수도 없다.

 

이러한 문제는 Generic Programming으로 해결할 수 있지만, C언어에서는 한계점이 있다.

일반적으로는 C++이나 java 같은 객체지향 프로그램이 언어를 사용해 해결하는 것이 좋다.

 

* Generic Programming :

로직은 같지만 다루는 데이터 타입만 다를 때,

하나의 코드로 여러 데이터 타입을 다룰 수 있도록 구현하는 것

⇒ C언어에서는 void *타입을 이용해 generic한 스택을 구현할 수 있으나, 단점이 많아 권장할만한 방법은 아니다.