학교/데이터구조응용
중간과제 - 동적스택 구현(C++)
공부 기록장
2024. 6. 9. 19:49
#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;
}