C언어 자료구조 스택의 개념과 구현(3) stack

이번 시간은 배열과 

연결리스트를 통해 스택을 구현하는 시간입니다. 

 



Q1.만약 스택이 동시에 2개이상 필요하다면? //타입이 Item인 create함수를 이용한다. 

Q2서로 다른 타입의 데이터를 저장할 스택이 필요하다면? //하지만 여전히 문제가 있다. 

 

Generic Programming

:1가지 타입의 데이터만 저장할 수 있음.

  데이터 타입이 달라지면 Item타입 정의를 수정해야함

  서로 다른 타입의 데이터를 저장하는 2개의 스택을 만들 수 없다.



void *타입을 이용하여 generic한 스택을 구현할 수 있으나 단점이 있다.

객체지향프로그래밍에서 방법을 찾을 수 있을 것이다. 

 

  

#ifndef STACKADT_H

#define STACKADT_H



#include <stdbool.h> 





1.배열로 구현 



// 실수를 저장한다면 함수 타입을 전부 바꿔야 해서 int라 한게 아니라 

//Item타입으로 했다.  =재사용성을 위해 



typedef int Item; //저장되는 타입이 Item이다.  



typedef struct stack_type *Stack;   //스택이 가리키는 그주소의 타입이 stack_type이다. 





struct stack_type {

 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;

}



// 이런 예로 쓰게 된다

int main() 

{

 Stack s1 = create();

 Stack s2 = create();

 

 push(s1, 12);

 push(s2, 9);

 ...

}

 



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 peek: 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;

 

}



-------------------------------------------------------------------

2.연결리스트로 구현 

//top하나만 있으면 구현가능하다. 배열과는 다른점이다. 

 

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_empty(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);//삭제할 노드 주소 저장해뒀으니 free한다. 

 return i;

 

}



Item peek(Stack s)

{

 if(is_empty(s))

  terminate("Error in peek: stack is empty.");

 return s->top->data;

}