[C++] 스택 구현

1. 이것은 무엇인가?

- STL에서 제공하는 스택을 이해하기 위해 직접 구현해보았다.

 

2. 스택이란 무엇인가?

- 스택은 가장 먼저 들어온 데이터가 가장 늦게 나가는 방식을 사용하는 자료구조이다. 이 방식을 선입후출, First in Last out, FILO라고도 한다. 

- 이런 특성을 살리기 위해 top이라는 인덱스가 필요하다. 이는 현 스택에 데이터의 마지막 혹은 스택의 꼭대기가 어디에 있는지 알려주기 위함이다.

- 이 top을 통해 데이터를 맨 앞부터 차곡차곡 쌓고 맨 뒤부터 다시 빼는 방식을 구현할 수 있다.

 

3. 요구 사항

- 스택의 데이터 추가

- 스택의 데이터 제거

- 스택의 데이터 유무 확인

- 스택의 포화 상태 확인

- 스택의 모든 데이터 출력

 

4. 함수 설명

- 스택에 대한 아래 코드들은 고정 배열 기반으로 만들었다.

 4-1. empty()

bool empty()
{
	bool result = true;
	for (int i = 0; i < m_top; i++)
	{
		if (m_stackArr[i])
		{
			result = false;
			break;
		}
	}
	return result;
}

- 배열이 비었는지 확인하는 함수이다.

- 가장 처음 인덱스부터 데이터가 들어와있는 top까지 순차적으로 접근하는데

- 만약 배열에 값이 있다면 false를 반환하는 함수이다.

- 생각해보니 딱히 for문을 돌리지 않고 top 값이 0이면 그 배열에 데이터가 없을텐데 더 간단한 구현 문제였다.

 

 4-2. full() 

bool full()
{
	bool result = true;
	for (int i = 0; i < MAX_SIZE; i++)
	{
		if (m_stackArr[i] == NULL)
		{
			result = false;
			break;
		}
	}
	return result;
}

- 배열이 가득 찼는지 확인하는 함수이다.

- 최대 배열의 크기까지 반복문을 수행하는데 수행하는 중에 배열에 데이터가 없다면 false를 반환한다.

- 이것도 비슷한 의문이 들었다. 그냥 top값이 최대 배열 크기랑 같으면 배열이 가득 찬 것인데 더 간단한 문제였다.

 

 4-3. push(int)

void push(int num)
{
	if (MAX_SIZE > m_top)
	{
		m_top++;
		m_stackArr[m_top] = num;
	}
}

- 스택에 값을 넣는 함수이다.

- 만약 최대 배열 크기가 top의 값보다 작으면 값을 넣는 것이다.

- 저 조건문의 구문이 full()에 응용해 간단하게 구현할 수 있는 좋은 예시인 것 같다.

 

 4-4. pop()

int pop()
{
	int result;
	if (m_top != -1)
	{
		result = m_stackArr[m_top];
		m_stackArr[m_top] = NULL;
		m_top--;
	}
	else
	{
		result = 0;
	}
	return result;
}

- 스택에서 데이터를 꺼내는 함수이다.

- 만약 top 값이 -1이라면 값을 반환할 변수에 가장 맨 위의 데이터를 저장한다.

- 그리고 가장 맨 위의 데이터에 NULL을 대입하고 top을 하나 줄인다.

- top이 왜 -1이 아니면 일까? 인덱스의 가장 처음은 1이 아니고 0이기 때문에, 스택의 데이터가 아예 없는 상태는 0이 아니라 -1이기 때문에 이렇게 했다.

- 만약 아무것도 없다면 반환값 저장 변수에 0을 넣는다.

 

 4-5. print()

void print()
{
	cout << "stack print()" << endl;
	for (int i = 0; i < m_top + 1; ++i)
	{
		cout << m_stackArr[i] << " ";
	}
	cout << endl;
}

- 스택의 데이터 값을 출력하는 함수이다.

- 0부터 top까지 인덱스를 증가시켜 스택에 있는 모든 데이터를 출력한다.

 

4. 코드

#pragma once
#include"Header.h"

const int MAX_SIZE = 10;
class Stack
{
private:
	int m_stackArr[MAX_SIZE];
	int m_top;
public:
	Stack() : m_top(-1)
	{
		for (int i = 0; i < MAX_SIZE; i++)
		{
			m_stackArr[i] = NULL;
		}
	}

	void push(int num)
	{
		if (MAX_SIZE > m_top + 1)
		{
			m_top++;
			m_stackArr[m_top] = num;
		}
	}

	int pop()
	{
		int result;
		if (m_top != -1)
		{
			result = m_stackArr[m_top];
			m_stackArr[m_top] = NULL;
			m_top--;
		}
		else
		{
			result = 0;
		}
		return result;
	}

	int top()
	{
		return m_stackArr[m_top];
	}

	bool empty()
	{
		bool result = true;
		for (int i = 0; i < m_top; i++)
		{
			if (m_stackArr[i])
			{
				result = false;
				break;
			}
		}
		return result;
	}

	bool full()
	{
		bool result = true;
		for (int i = 0; i < MAX_SIZE; i++)
		{
			if (m_stackArr[i] == NULL)
			{
				result = false;
				break;
			}
		}
		return result;
	}

	void print()
	{
		cout << "stack print()" << endl;
		for (int i = 0; i < m_top + 1; ++i)
		{
			cout << m_stackArr[i] << " ";
		}
		cout << endl;
	}
};