[42서울] ft_containers[1] - 스택 구현

서론

스택이란 LIFO(last-in first-out 후입선출)로 동작하는 자료구조로, cpp module에서(그리고 조금 다르지만 푸시스왑에서) 이미 가볍게 다뤄봤듯이 컨테이너의 한쪽 끝에서만 입력하고 출력하는 자료구조이다.

 

다른 컨테이너를 가져와서 그 컨테이너 위에서 동작하도록(캡슐화) 되어 있는데, 이 과제에서는 내가 만든 벡터를 이용하여 구현해야 한다. 하지만 우선 std::vector를 사용하여 구현을 먼저 하고 나중에 내가 만든 ft::vector로 바꾼 다음 정상적으로 동작하는지를 확인하면 될 거라고 생각했다. 이게 가장 쉽기도 하지만 구현 내용 자체가 많지 않고, 서브젝트상 추가로 구현해야 하는 내용이 없어서 가장 마음 편하게 접근할 수 있을 거라고 생각한다.

 

아래 기능을 지원하는 컨테이너라면 어떤 컨테이너든 상관이 없다. 그래서 대부분의 컴파일러에서는 덱으로 구성되어있지만, 이 과제에서는 벡터를 사용해서 구현을 한다.

• empty
• size
• back
• push_back
• pop_back

 

들어가야하는 구성요소

타입

value_type - 어떤 자료형을 저장하느냐

container_type - 어떤 컨테이너에 저장하느냐

size_type - 사이즈의 자료형

 

멤버함수

(constructor) - c++98 까지는 컨테이너의 종류만 인자로 받았음.

소멸자 - 특별한 동작 없음

operator= - c++98 까지는 const stack 만 인자로 받았음.

empty - 사용한 컨테이너의 empty 함수를 사용해서 구현

size - 사용한 컨테이너의 size 함수를 사용해서 구현

top - 사용한 컨테이너의 back 함수를 사용해서 구현

push - 사용한 컨테이너의 push_back 함수를 사용해서 구현

pop - 사용한 컨테이너의 pop_back 함수를 사용해서 구현

 

비멤버함수(오버로드)

함수 안에서 friend 키워드를 사용해서 비 멤버함수의 오버로드를 쉽게 할 수 있다.

operator==

operator!=

operator<

operator<=

operator>

operator>=

 

테스트

#include <time.h>
#include <iostream>
#include "stack.hpp"
#include <stack>
#include <fstream>
#include <time.h>

static void stl_test(std::ofstream& stlFile) {
	clock_t g_start = clock();

	std::stack<int> st;
	for (int i = 0; i < 100000; i++) {
		st.push(i * 3);
	}
	stlFile << "Top element (st): " << st.top() << std::endl;
	stlFile << "stack size (st): " << (st.empty() ? "true" : "false")
						<< std::endl;

	std::stack<int> st2(st);
	stlFile << "Top element (st2): " << st2.top() << std::endl;
	stlFile << "stack size (st2): " << (st2.empty() ? "true" : "false")
						<< std::endl;
	stlFile << "stack empty (st2): " << (st2.empty() ? "true" : "false")
						<< std::endl;

	st2.push(99);
	st2.push(42);
	stlFile << "Top element (st2): " << st2.top() << std::endl;
	stlFile << "stack size (st2): " << (st2.empty() ? "true" : "false")
						<< std::endl;

	std::stack<int> st3 = st2;
	stlFile << "st2 == st3: " << (st2 == st3 ? "true" : "false") << std::endl;

	st3.pop();
	st3.pop();
	st3.pop();
	st3.pop();
	st3.pop();
	stlFile << "Top element (st3): " << st2.top() << std::endl;
	stlFile << "st2 == st3: " << (st2 == st3 ? "true" : "false") << std::endl;
	stlFile << "st2 != st3: " << (st2 != st3 ? "true" : "false") << std::endl;
	stlFile << "st2 < st3: " << (st2 < st3 ? "true" : "false") << std::endl;
	stlFile << "st2 >= st3: " << (st2 >= st3 ? "true" : "false") << std::endl;

	int count = 0;
	while (!st3.empty()) {
		count++;
		st3.pop();
	}
	stlFile << "Count of pop operations (st3): " << count << std::endl;
	stlFile << "stack empty (st3): " << (st3.empty() ? "true" : "false")
						<< std::endl;

	clock_t g_end = clock();
	stlFile << "stl_stack_Execution time (ms): " << (double)(g_end - g_start) / CLOCKS_PER_SEC * 1000 << "ms" << std::endl;
}

static void ft_test(std::ofstream& ftFile) {
	clock_t g_start = clock();
	ft::stack<int> st;
	for (int i = 0; i < 100000; i++) {
		st.push(i * 3);
	}
	ftFile << "Top element (st): " << st.top() << std::endl;
	ftFile << "stack size (st): " << (st.empty() ? "true" : "false")
						<< std::endl;

	ft::stack<int> st2(st);
	ftFile << "Top element (st2): " << st2.top() << std::endl;
	ftFile << "stack size (st2): " << (st2.empty() ? "true" : "false")
						<< std::endl;
	ftFile << "stack empty (st2): " << (st2.empty() ? "true" : "false")
						<< std::endl;

	st2.push(99);
	st2.push(42);
	ftFile << "Top element (st2): " << st2.top() << std::endl;
	ftFile << "stack size (st2): " << (st2.empty() ? "true" : "false")
						<< std::endl;

	ft::stack<int> st3 = st2;
	ftFile << "st2 == st3: " << (st2 == st3 ? "true" : "false") << std::endl;

	st3.pop();
	st3.pop();
	st3.pop();
	st3.pop();
	st3.pop();
	ftFile << "Top element (st3): " << st2.top() << std::endl;
	ftFile << "st2 == st3: " << (st2 == st3 ? "true" : "false") << std::endl;
	ftFile << "st2 != st3: " << (st2 != st3 ? "true" : "false") << std::endl;
	ftFile << "st2 < st3: " << (st2 < st3 ? "true" : "false") << std::endl;
	ftFile << "st2 >= st3: " << (st2 >= st3 ? "true" : "false") << std::endl;

	int count = 0;
	while (!st3.empty()) {
		count++;
		st3.pop();
	}
	ftFile << "Count of pop operations (st3): " << count << std::endl;
	ftFile << "stack empty (st3): " << (st3.empty() ? "true" : "false")
						<< std::endl;
	clock_t g_end = clock();
	ftFile << "ft_stack_Execution time (ms): " << (double)(g_end - g_start) / CLOCKS_PER_SEC * 1000 << "ms" << std::endl;
}


int main()
{
    std::ofstream stlFile("./stlFile.txt");
	if (stlFile.fail())
	{
		std::cerr << "Error!" << std::endl;
	}
    std::ofstream ftFile("./ftFile.txt");
	if (ftFile.fail())
	{
		std::cerr << "Error!" << std::endl;
	}

    ftFile << "\n***** STACK TEST *****\n" << std::endl;
	ft_test(ftFile);
	ftFile.close();

    stlFile << "\n***** STACK TEST *****\n" << std::endl;
	stl_test(stlFile);
	stlFile.close();

	system("diff ftFile.txt stlFile.txt");
}

평가 가서 본 테스트 파일을 얻어다가 스택만 돌아가도록 일부분을 바꿔서 사용했다.

 

무난하게 동작하는 것으로 보인다.