중간과제 - 동적스택 구현(C++)

#include <iostream>

using namespace std;

template <typename T>
class Stack {
private:
	T* stack;             //스택 구현을 위한 포인터 변수
	T* temp;              //데이터를 임시로 보관하기 위한 포인터 변수 
	T  re;                //pop 함수에서 삭제되는 값을 임시로 저장하기 위한 변수
	int STACK_SIZE = 10;  //스택의 기본 크기(상수)
	int top;              //스택의 최상위 원소의 인덱스를 추적하는 변수
	int size_value;       //스택의 크기 조절을 위한 배수 값을 저장하는 변수
public:
	Stack() {
		cout << " ------------------------------";
		cout << " \n  [stack 메모리를 생성합니다.] \n";
		cout << " ------------------------------\n\n";
		stack = new T[STACK_SIZE];
		top = -1;
		size_value = 1;
	}
	~Stack() {
		cout << " \n\n ------------------------------";
		cout << "\n  [stack 메모리를 해제합니다.]\n";
		cout << " ------------------------------\n";
		delete[] stack;
	}
	int capacity();     //전체 용량 출력
	int size();         //삽입되어 있는 데이터의 개수 출력
	void printStack();  //스택 출력
	int isEmpty();      //스택 비어있는지 확인
	int isFull();       //스택이 포화상태인지 확인
	void sort();        //오름차순 정렬

	void push(T value);                        //배열 끝에 데이터 삽입
	void pushAt(int location, T value);        //원하는 인덱스에 데이터 삽입
	void push_range(T values[], int length);               //배열에 배열 삽입
	void push_range(int location, T values[], int length); //원하는 인덱스에 배열 삽입

	T pop();             //배열 끝에 있는 데이터 삭제
	T pop(int location); //입력받은 인덱스에 해당하는 데이터 삭제
};

template <typename T>
int Stack<T>::capacity() {  //전체 용량 리턴
	return STACK_SIZE * size_value;
}

template <typename T>
int Stack<T>::size() {     //삽입되어 있는 데이터 개수 리턴
	return top + 1;
}

template <typename T>
void Stack<T>::printStack() {  //현재 스택 상태 출력
	
	cout << " ========================================================\n";
	cout << "\n STACK SIZE [" << (STACK_SIZE * size_value) << "] \n";
	cout << "\n STACK [ ";

	for (int i = 0; i <= top; i++)
		cout << stack[i] << " ";
	cout << "] \n\n\n\n";
	cout << " 스택 전체 용량 : " << capacity() << endl;
	cout << "\n 데이터 개수 : " << size() << endl;
	cout << endl;
}

template <typename T>
int Stack<T>::isEmpty() {     //스택이 비어있는지 확인하기 위한 함수
	if (top == -1)
		return 1;
	else
		return 0;
}

template <typename T>
int Stack<T>::isFull() {       //스택이 풀인지 확인하기 위한 함수
	if (top % STACK_SIZE == 9) 
		return 1;
	else 
		return 0;
}

template <typename T>
void Stack<T>::sort() {    //오름차순 정렬하여 출력하는 함수
	
	int n = size();

	//버블정렬 사용
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - 1; j++)
		{
			if (stack[j] > stack[j + 1])
			{
				re = stack[j];
				stack[j] = stack[j + 1];
				stack[j + 1] = re;
			}
		}
	}
	cout << "\n sort 함수 실행결과 : ";
	for (int i = 0; i < n; ++i) {
		cout << stack[i] << " ";
	}
	cout << endl;
}

template <typename T>
void Stack<T>::push(T value) { //배열 끝에 데이터를 삽입하는 함수
	
	if (isFull()) {            //스택이 꽉 찬 상태
		cout << " ========================================================\n";
		cout << " Full STACK!!\n\n";
		temp = new T[STACK_SIZE * size_value];        //데이터를 임시 보관할 temp 메모리 할당

		for (int i = 0; i < (top + 1); i++)
			temp[i] = stack[i];                       //stack의 데이터를 temp에 임시보관
		delete[] stack;                               //stack 메모리 반환
		
		stack = new T[STACK_SIZE * (size_value + 1)]; //stack 사이즈 증가

		for (int i = 0; i < (top + 1); i++)
			stack[i] = temp[i];                       //임시보관한 데이터를 stack에 다시 삽입
		stack[++top] = value;  //top을 증가시킨 후 현재 stack[top]에 value 삽입
		size_value++;
		delete[] temp;
	}
	else {
		stack[++top] = value;  //top을 증가시킨 후 현재 stack[top]에 value 삽입
	}
}

template <typename T>
void Stack<T>::pushAt(int location, T value) {  //원하는 인덱스에 데이터 삽입하는 함수

	if (location < 0 || location > top + 1) {   //location이 stack 메모리의 인덱스를 벗어나는 경우
		cout << " PUSH INDEX ERROR\n";
		return;
	}
	if (isFull()) {          //스택이 꽉 찬 상태
		cout << " ========================================================\n";
		cout << " Full STACK!!\n\n";
		temp = new T[STACK_SIZE * size_value];        //데이터를 임시 보관할 temp 메모리 할당

		for (int i = 0; i < (top + 1); i++)
			temp[i] = stack[i];                       //stack의 데이터를 temp에 임시보관
		delete[] stack;                               //stack 메모리 반환

		stack = new T[STACK_SIZE * (size_value + 1)]; //stack 사이즈 증가하여 메모리 할당

		for (int i = 0; i < (top + 1); i++)
			stack[i] = temp[i];                       //임시보관한 데이터를 stack에 다시 삽입

		if (location > top)  //맨 끝에 삽입하는 경우
			stack[location] = value;
		else {               //맨 처음 또는 중간에 삽입하는 경우
			for (int i = top; i >= location; i--)
				stack[i + 1] = stack[i];
			stack[location] = value;
		}
		top++;
		size_value++;
		delete[] temp;
	}
	else {
		if (location > top)           //맨 끝에 삽입하는 경우
			stack[location] = value;  //삽입하려는 인덱스(location)에 value 삽입
		else {                        //맨 처음 또는 중간에 삽입하는 경우
			for (int i = top; i >= location; i--)
				stack[i + 1] = stack[i];
			stack[location] = value;
		}
		top++;
	}
}

template <typename T>
void Stack<T>::push_range(T values[], int arrSize) {
	/*stack이 이미 꽉찬 상태이거나(기존에 있던 데이터개수 + 삽입하려는 배열의 길이)이
	스택 사이즈를 오버하는 경우*/
	if (isFull() || top + arrSize >= STACK_SIZE * size_value) {  
		cout << " ========================================================\n";
		cout << " Full STACK!!\n\n";
		cout << " \n 삽입되는 values[] 사이즈 : " << arrSize << endl;
		cout << " \n Total 사이즈 : " << size() + arrSize << endl;
		
		temp = new T[STACK_SIZE * size_value];      //데이터를 임시 보관할 temp 메모리 할당
		for (int i = 0; i < (top + 1); i++)
			temp[i] = stack[i];                     //stack의 데이터를 temp에 임시보관
		delete[] stack;                             //stack 메모리 반환
		
		//삽입되는 values[] 크기만큼 메모리 사이즈 증가
		size_value += (top + arrSize) / (STACK_SIZE * size_value) 
			+ (((top + arrSize) % (STACK_SIZE * size_value)) / STACK_SIZE);
		
		cout << " \n 변경되는 STACK 사이즈 : " << STACK_SIZE * size_value << endl;
		
		stack = new T[STACK_SIZE * size_value];    //stack 사이즈 증가하여 메모리 할당
		for (int i = 0; i < (top + 1); i++)
			stack[i] = temp[i];                    //임시보관한 데이터를 stack에 다시 삽입

		for (int a = 0; a < arrSize; a++) {
			stack[++top] = values[a];         //스택 끝에 top 증가시키면서 배열 원소 순서대로 삽입
		}
		delete[] temp;
	}
	else {
		for (int a = 0; a < arrSize; a++) {
			stack[++top] = values[a];         //스택 끝에 top 증가시키면서 배열 원소 순서대로 삽입
		}
	}
}

template <typename T>
void Stack<T>::push_range(int location, T values[], int arrSize) {
	if (location < 0 || location > top + 1) {
		cout << " 인덱스 위치를 잘 못 입력하셨습니다.\n";
		return;
	}
	//배열 공간이 이미 꽉 차있는 경우 또는 삽입하려는 배열의 크기가 기존 공간을 초과하는 경우  
	if (isFull() || top + arrSize >= STACK_SIZE * size_value) { 
		cout << " ========================================================\n";
		cout << " Full STACK!!\n\n";
		cout <<	" \n 삽입되는 values[] 사이즈 : "  << arrSize << endl;
		cout << " \n Total 사이즈 : " << size() + arrSize << endl;
		

		temp = new T[STACK_SIZE * size_value];  //데이터를 임시 보관할 temp 배열 선언 
		for (int i = 0; i < (top + 1); i++)
			temp[i] = stack[i];                 //temp에 데이터 삽입(임시보관)
		delete[] stack;                         //기존 stack 배열 메모리 반환
		
		//삽입되는 values[] 크기만큼 메모리 사이즈 증가
		size_value += (top + arrSize) / (STACK_SIZE * size_value) + 
			(((top + arrSize) % (STACK_SIZE * size_value))/STACK_SIZE);

		cout << " \n 변경되는 STACK 사이즈 : " << STACK_SIZE * size_value << endl;
	
		stack = new T[STACK_SIZE * size_value]; //공간 넓힌 stack 배열 선언 
		for (int i = 0; i < (top + 1); i++)
			stack[i] = temp[i];                 // temp 배열에 있는 데이터를 stack에 복사

		if (location > top) {                   //기존에 있던 배열 뒤에 삽입하는 경우
			for (int a = 0; a < arrSize; a++) {
				stack[location++] = values[a];
			}
		}
		else {                                  //맨 처음 또는 중간에 삽입하는 경우
			for (int i = top; i >= location; i--)
				stack[i + arrSize] = stack[i];
			for(int i = 0 ; i < arrSize;i++)
				stack[location+i] = values[i];
		}
		top += arrSize;
		delete[] temp;

	}
	//기존 배열에 배열을 삽입해도 공간이 남는 경우
	else {   
		if (location > top) { //기존에 있던 배열 끝에 삽입하는 경우
			for (int a = 0; a < arrSize; a++) {
				stack[location++] = values[a];
			}
		}
		else {                //맨 처음 또는 중간에 삽입하는 경우
			for (int i = top; i >= location; i--) 
				stack[i + arrSize] = stack[i];
				
			for (int i = 0; i < arrSize; i++)
				stack[location + i] = values[i];
		}
		top += arrSize;
	}
}


template <typename T>
T Stack<T>::pop() {
	if (isEmpty()) {	// 스택이 공백 상태인 경우
		cout << "\n\n Stack is Empty!!\n";
		return 0;
	}
	else                
	{
		cout << " pop() 함수 실행\n" << endl;
		if (top % 10 == 0) 
		{
			cout << " CHANGE STACK\n";
			re = stack[top];     //re 변수에 맨 끝에 있는 값 저장

			temp = new T[STACK_SIZE * (size_value-1)];
			for (int i = 0; i < top; i++) 
				temp[i] = stack[i];
			delete[] stack;

			stack = new T[STACK_SIZE * (size_value - 1)];//공간 줄인 stack 배열 선언
			
			for (int i = 0; i < top; i++) 
				stack[i] = temp[i];                      // temp 배열에 있는 데이터를 stack에 복사
			delete[] temp;
			top--;
			size_value--;
			return re;
		}
		else	
			return stack[top--];	      // 현재 top의 원소를 삭제한 후 top 감소
	}
}

template <typename T>
T Stack<T>::pop(int location) {
	if (isEmpty()) {	// 스택이 공백 상태인 경우
		cout << "\n\n Stack is Empty!!\n";
		return 0;
	}
	else                
	{
		if (location < 0 || location > top) {   //인덱스 값을 잘 못 입력한 경우
			cout << " 인덱스 위치를 잘 못 입력하셨습니다.\n";
			return 0;
		}
		else {
			cout << " pop(" << location << ")함수 실행\n" << endl;
			if (top % 10 == 0)
			{
				cout << " CHANGE STACK\n";
				re = stack[location];   //re 변수에 입력된 인덱스 값 저장
				for (int i = location; i < top; i++) 
					stack[i] = stack[i + 1];
			
				temp = new T[STACK_SIZE * (size_value - 1)];//공간 줄인 temp 배열 선언
				for (int i = 0; i < top; i++) 
					temp[i] = stack[i];
				delete[] stack;

				stack = new T[STACK_SIZE * (size_value - 1)];//공간 줄인 stack 배열 선언
				for (int i = 0; i < top; i++) 
					stack[i] = temp[i];
				delete[] temp;
				top--;
				size_value--;
				return re;
			}
			else {
				re = stack[location];
				for (int i = location; i < top; i++) 
					stack[i] = stack[i + 1];
				top--;
				return re;	      // 현재 top의 원소를 삭제한 후 top 감소
			}
		}	
	}
}


int main() {
	
	Stack<string> s;

	string str[] = { "hello", "world", "stack", "c++" };
	s.push("BBB");
	s.push("AAA");
	s.push("CCC");
	s.printStack();
	
	s.push_range(str, sizeof(str) / sizeof(string));
	s.printStack();

	s.pop();
	s.printStack();

	s.sort();

	return 0;
}