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

출처 | DO IT C언어 자료구조 입문편

이번 시간에는 스택(검색..종료) / 스택을 사용한 프로그램을 구현해보자.

Stack 검색-종료 과정

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

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

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

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

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

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

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

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

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

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

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

void Print(const IntStack *s)
{
	int i;

	for (i = 0; i < s->ptr; i++)		
		printf("%d ", s->stk[i]);
	putchar('\n');
}

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

다음 예제는 스택을 사용하는 프로그램을 구현했다.

스택을 사용하는 프로그램.c(main)

#include "IntStack.h"

int main()
{
	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)출력 (5)종료  : ");
		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오류 : 팝에 실패했습니다.\n");
			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;
}

IntStack.c

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

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

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

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

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

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

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

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

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

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

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

void Print(const IntStack *s)
{
	int i;

	for (i = 0; i < s->ptr; i++)		
		printf("%d ", s->stk[i]);
	putchar('\n');
}

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

IntStack.h

#ifndef ___IntStack
#define ___IntStack
#include <stdio.h>

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

<결과>

• 이번 예제는 파일분할, 스택 관련 공부가 필수적이다.
• 이번 시간에 공부한 내용을 요약하면,

1. Stack의 검색 -> 종료 과정 함수 구현
2. 스택을 사용하는 프로그램 구현 (스택1 & 스택2)