자료구조 제 13-3 강 (스택의 구현 2)

static

• 지역변수에 사용할 경우: 프로그램 종료 시까지 메모리 공간이 남아있음
• 전역변수에 사용할 경우: 다른 파일에서 해당 변수에 접근하는 것을 막아줌

 

stackADT.c

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

#define INIT_CAPACITY 100

struct stack_type {
	Item* contents;		/* 배열 */
	int top;
	int size;			// 배열의 크기
};

static void terminate(const char* message)	// 예외 사항이 발생했을 때, 그에 관한 메세지 출력 후 exit
{
	printf("%s\n", message);
	exit(1);
}

Stack create()	// Stack* craete()가 아닌 이유: Stack 자체를 struct stack_type* 로 정의했기 때문
{
	Stack s = (Stack)malloc(sizeof(struct stack_type));
	if (s == NULL)	// 동적할당 (malloc)이 실패했다는 뜻
		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 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;
}

 

stackADT.h

#ifndef STACKADT_H
#define STACKADT_H

#include <stdbool.h>

typedef int Item;		// int 데이터 타입에 Item이라는 별명을 만들어줌
// 만약 나중에 실수를 저장하는 스택들로 바꾸어야 할 때, 변경하기 쉽도록 하기 위함 (코드의 재사용)

typedef struct stack_type* Stack;	// struct stack_type* 를 Stack으로 renaming해줌

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

 

linkedADT.c

/* 연결리스트로 구현한 stackADT.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_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);
	return i;
}

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

 

 

• 만약 스택이 동시에 2개 이상 필요하다면?  ->  create를 두 번 해주고 각각의 스택을 매개변수로 넣으면 됨
• 서로 다른 타입의 데이터를 저장할 스택이 필요하다면?  ->  generic programming : c언어에 적합한 프로그래밍은 아님

 

Generic ADTs

 

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

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

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

- 객체지향 프로그래밍 언어