[알고리즘] Stack 구현하기

// 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

// IntStack.cpp

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

using namespace std;

int Initialize(IntStack* s, int max)		// 스택 초기화
{
	s-> ptr = 0;		// 배열을 위한 메모리 공간을 만들 때 스택은 비어 있어야 한다. 스택 포인터 ptr 값을 0으로 한다.
	s-> stk = new int[max];
	if (s->stk == NULL)
	{
		s->max = 0;		// 배열의 생성에 실패
		return -1;		
	}
	s-> max = max;	// 스택 최대 용량을 나타내는 구조체의 멤버 max에 저장
	return 0;		
}

int Push(IntStack* s, int x)	// 스택에 데이터 푸쉬
{

	if (s->ptr >= s->max)
	{
		return -1;		// 스택이 가득 차서 푸시할 수 없는 경우에는 -1을 반환
	}
	s->stk[s->ptr++] = x;	
	return 0;		// 푸시에 성공하면 0을 반환
}

int Pop(IntStack* s, int *x)		// 스택에서 데이터를 제거
{
	if (s->ptr <= 0)		// 스택이 비어 있음
	{
		return -1;		// 팝을 할 수 없는 경우에는 -1을 반환
	}
	*x = s->stk[--s->ptr];
	return 0;		// 팝에 성공할 경우에는 0을 반환
}

int Peek(const IntStack* s, int* x)		// Peek 한수는 스택 꼭대기의 데이터를 몰래 엿보는 함수이다.
{
	if (s->ptr <= 0)		// 스택이 비어 있음
		return -1;		// 스택이 비어 있어 피크할 수 없는 경우 -1을 반환
	*x = s->stk[s->ptr - 1];	// 스택이 비어 있지 않으면 꼭대기 요소 stk[ptr-1]의 값을 포인터 x가 가리키는 변수에 저장
		return 0;	// 피크에 성공하면 0을 반환
}

void Clear(IntStack* s)		// 스택의 모든 요소 삭제
{
	s->ptr = 0;		// 모든 요소의 삭제는 스택 포인터 ptr값을 0으로 하면 끝난다.
}

int Capacity(const IntStack* s)		// 스택 용량(멤버 max의 값) 반환
{
	return s->max;
}

int Size(const IntStack* s)		// 스택에 쌓여 있는 데이터 개수(멤버 ptr의 값)
{
	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)		// 스택에서 검색
{
	for (int i = s->ptr - 1; i >= 0; i--)		// 꼭대기(top) -> 바닥(bottom)으로 선형 검색
	{
		if (s->stk[i] == x)
		{
			return i;						// 검색 성공
		}
	}
	return -1;					// 검색 실패
}

void Print(const IntStack* s)		// 모든 데이터 출력, 스택에 쌓여 있는 ptr개의 모든 데이터 출력
{
	for (int i = 0; i < s->ptr; i++)
	{
		cout << s->stk[i] << endl;
	}
}

void Terminate(IntStack* s)		// Terminate 함수는 Initialize 함수로 확보한 스택을 해제하고 용량 max와 스택 포인터 ptr의 값을 0으로 한다.
{
	if (s->stk != NULL)
	{
		delete[] s->stk;
	}
	s->max = s->ptr = 0;
}

// IntStackTest.cpp

#include <iostream>
#include "IntStack.h"

using namespace std;

int main(void)
{
	IntStack s;
	if (Initialize(&s, 64) == -1)
	{
		cout << "스택 생성에 실패했습니다. ";
		return 1;
	}

	while (1)
	{
		int menu, x;
		cout << "현재 데이터 수: " << Size(&s) << " / " << Capacity(&s) << endl;
		cout << "(1)푸시 (2)팝 (3)피크 (4)출력 (5)삭제 (6)검색 (0)종료: ";
		cin >> menu;

		if (menu == 0)
		{
			break;
		}
		switch (menu)
		{
		case 1:		//푸시
			cout << "데이터: ";
			cin >> x;
			if (Push(&s, x) == -1)
			{
				cout << "\a오류: 푸시에 실패했습니다. ";
			}
			break;
		case 2:		// 팝
			if (Pop(&s, &x) == -1)
			{
				cout << "\a오류: 팝에 실패했습니다. ";
			}
			else
			{
				cout << "팝 데이터는 " << x << "입니다.\n";
			}
			break;
		case 3:		// 피크
			if (Peek(&s, &x) == -1)
			{
				cout << "\a오류: 피크에 실패했습니다. ";
			}
			else
			{
				cout << "피크 데이터는 " << x << "입니다. ";
			}
			break;

		case 4:		// 출력
			Print(&s);
			break;
		case 5:		// 클리어
			Clear(&s);
			break;
		case 6:		// 검색
			cout << "검색할 수: ";
			cin >> x;
			if (Search(&s, x) == -1)
			{
				cout << "\a오류: 검색에 실패했습니다. ";
			}
			else
			{
				cout <<x<<"(이)가 검색되었습니다. ";
			}
			break;
		}
	}
	Terminate(&s);
	return 0;
}