#자료구조와 함께 배우는 알고리즘 입문 C언어편 - 4

4장 스택과 큐

 

04-1 스택

스택이란?

데이터를 일시적으로 저장하기 위해 사용하는 자료구조

데이터 입력과 출력 순서는 후입선출 (가장 나중에 넣은 데이터를 가장 먼저 꺼냄)

푸시 (push) : 데이터를 넣는 작업

팝 (pop) : 데이터를 꺼내는 작업

// 스택 만들기
// IntStack.h
#ifndef ___IntStack
#define ___IntStack

typedef struct
{
	int max; // 최대 용량
	int ptr; // 포인터
	int* stk; // 스택 배열을 가리키는 포인터
} IntStack; // 스택을 구현하는 구조체

int Initialize(IntStack* s, int max); //초기화

int Push(IntStack* s, int x); // 데이터 넣기

int Pop(IntStack* s, int* x); // 데이터 꺼내기

int Peek(const IntStack* s, int* x); // 데이터 피크

void Clear(IntStack* s); // 비우기

int Capacity(const IntStack* s); // 최대 용량

int Size(const IntStack* s); // 데이터 개수

int IsEmpty(const IntStack* s); // 비어 있는지?

int IsFull(const IntStack* s); // 가득 찼는지?

int Search(const IntStack* s, int x); // 검색

void Print(const IntStack* s); // 출력

void Terminate(IntStack* s); // 종료

#endif

초기화 함수 Initialize

스택의 메모리 공간을 확보와 준비 작업을 수행, 초기화 함수

int Initialize(IntStack* s, int max)
{
	s->ptr = 0;
	if ((s->stk = (int*)calloc(max, sizeof(int))) == NULL)
	{
		s->max = 0;
		return -1;
	}
	s->max = max;
	return 0;
}

푸시 함수 Push

스택에 데이터를 추가하는 함수

스택이 가득차서 푸시할 수 없는 경우 -1 반환 / 성공할 경우 0 반환

int Push(IntStack* s, int x)
{
	if (s->ptr >= s->max)
	{
		return - 1;
	}
	s->stk[s->ptr++] = x;
	return 0;
}

팝 함수 Pop

스택의 꼭대기에서 데이터를 꺼내는 함수

스택이 비어있어 팝을 할 수 없는 경우 -1 반환 / 성골할 경우 0 반환

int Pop(IntStack* s, int* x)
{
	if (s->ptr <= 0)
	{
		return -1;
	}
	*x = s->stk[--s->ptr];
	return 0;
}

피크 함수 Peek

스택 꼭대기의 데이터를 몰래 엿보는 함수

스택이 비어있어 피크를 할 수 없는 경우 -1 반환 / 성골할 경우 0 반환

int Peek(const IntStack* s, int* x)
{
	if (s->ptr <= 0)
	{
		return -1;
	}
	*x = s->stk[s->ptr -1];
	return 0;
}

스택의 모든 요소를 삭제하는 함수 Clear

스택에 쌓여 있는 모든 데이터를 삭제하는 함수

void Clear(IntStack* s)
{
	s->ptr = 0;
}

용량을 확인하는 함수 Capacity

스택의 용량(max의 값)을 반환하는 함수

int Capacity(const IntStack* s)
{
	return s->max;
}

데이터의 개수를 확인하는 함수 Size

스택에 쌓여 있는 데이터 개수(ptr의 값)를 반환하는 함수

int Size(const IntStack* s)
{
	return s->ptr;
}

스택이 비어 있는지 검사하는 함수 IsEmpty

스택이 비어 있는지 검사하는 함수

비어 있으면 1을 반환 / 비어 있지않으면 0을 반환

int IsEmpty(const IntStack* s)
{
	return s->ptr <= 0;
}

스택이 가득 찼는지 검사하는 함수 IsFull

스택이 가득 찼는지 검사하는 함수

가득 찼으면 1을 반환 / 가득 안찼으면 0을 반환

int IsFull(const IntStack* s)
{
	return s->ptr >= s->max;
}

임의 값을 검색하는 함수 Search

임의 값의 데이터가 스택의 어느 위치에 쌓여 있는지 검사하는 함수

검색은 꼭대기에서 바닥으로 선형 검색을 수행 (배열 인덱스가 큰 쪽에서 작은 쪽으로 스캔)

검색이 성공할 경우 찾은 요소의 인덱스를 반환 / 실패할 경우 -1을 반환

int Search(const IntStack* s, int x)
{
	int i;
	for (i = s->ptr - 1; i >= 0; i--)
	{
		if (s->stk[i] == x)
		{
			return i;
		}
	}
	return -1;
}

모든 데이터를 출력하는 함수 Print

스택의 모든 데이터를 출력하는 함수

스택에 쌓여 있는 ptr개의 모든 데이터를 바닥부터 순서대로 출력

void Print(const IntStack* s)
{
	int i;
	for (i = 0; i < s->ptr; i++)
	{
		printf("%d", s->stk[i]);
	}
	putchar('\n');
}

종료 함수 Terminate

뒤처리를 담당하는 함수

Initialize 함수로 확보한 스택을 해제하고 max와 ptr의 값을 0으로 초기화

void Terminate(IntStack* s)
{
	if (s->stk != NULL)
	{
		free(s->stk);
	}
	s->max = s->ptr = 0;
}

스택을 사용하는 프로그램

int main(void)
{
	IntStack s;
	if (Initialize(&s, 64) == -1)
	{
		puts("스택 생성에 실패하였습니다.");
		return -1;
	}
	while (1)
	{
		int menu, x;
		printf("현재 데이터 수 : %d / %d\n", Size(&s), Capacity(&s));
		printf("(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : ");
		scanf_s("%d", &menu);

		if (menu == 0) break;
		switch (menu)
		{
		case 1:
			printf("데이터 : ");
			scanf_s("%d", &x);
			if (Push(&s, x) == -1)
			{
				puts("\a오류 : 푸스 실패");
			}
			break;

		case 2:
			if (Pop(&s, &x) == -1)
			{
				puts("\a오류 : 팝 실패");
			}
			else
			{
				printf("팝 데이터는 %d 입니다.\n", x);
			}
			break;
			
		case 3:
			if (Peek(&s, &x) == -1)
			{
				puts("\a오류 : 피크 실패");

			}
			else
			{
				printf("피크 데이터는 %d 입니다.\n", x);
			}
			break;

		case 4:
			Print(&s);
			break;
		}
	}
	Terminate(&s);
	return 0;
}