[C++/STL] stack을 vector로 변환하기

STL에서 stack은 컨테이너에 대한 접근을 제어하는 목적으로 사용된다.

따라서 iterator를 제공해주지 않기 때문에 iterator을 사용해서 vector를 만들어낼 수 없다.

 

요소를 제거하면서 vector 생성

stack<int> st;
st.push(1);
st.push(2);
st.push(3);
        
vector<int> arr(st.size());
int index = arr.size() - 1;

// copy st to arr
while(!st.empty()){
   arr[index--] = st.top();
   st.pop();
}

stack에서는 top을 통해서만 요소를 가져올 수 있기 때문에 top을 이용해서 vector의 뒤에서부터 값을 채워준다.

단, 이 방법을 쓰면 기존 stack에는 요소가 더 이상 남아있지 않아서 더 이상 사용할 수 없을것이다.

 

Custom stack 만들기

template <typename _Ty>
class custom_stack : public stack<_Ty> {
public:
	auto begin() { return c.begin(); }
	auto end() { return c.end(); }
};

custom_stack st;
st.push(1);
st.push(2);
st.push(3);
        
vector<int> arr(st.size());
        
// copy st to arr
copy(st.begin(), st.end(), arr.begin());

stack 클래스를 상속받은 custom_stack을 만들고 begin, end 함수를 정의해줬다.

여기서 c.begin(), c.end()를 호출하는데 이게 무멋인지 알기 위해 stack 라이브러리를 한 번 까보자.

template<class _Ty,
	class _Container = deque<_Ty> >
	class stack
	{ 
    // ...
    
    protected:
	_Container c;	// the underlying container
};

 

코드를 보면 protected 접근권한자로 _Container 타입의 c 멤버변수가 있고 _Container 타입은 deque<_Ty>와 같다.

따라서, c 멤버변수로는 deque의 함수를 호출할 수 있고 stack을 상속받아 c 변수로 접근가능하다면 deque의 함수들을 사용할 수 있다.

위 코드는 이를 이용하여 stack을 vector로 변환시킨 방법이다.

---

deque 사용하기

앞서 stack 라이브러리를 살펴봤을 때, 내부적으로 c라는 deque 멤버변수를 이용하고 있다는 것을 확인할 수 있었다.

bool empty() const
{	// test if stack is empty
	return (c.empty());
}

size_type size() const
{	// test length of stack
	return (c.size());
}

reference top()
{	// return last element of mutable stack
	return (c.back());
}

void push(const value_type& _Val)
{	// insert element at end
	c.push_back(_Val);
}

void pop()
{	// erase last element
	c.pop_back();
}

 

라이브러리를 좀 더 살펴보면 위와 같이 empty, size, top, push, pop 등의 함수들도 내부적으로는 deque 함수를 호출해서 구현되어있었다.

 즉, stack은 deque로 구현할 수 있다는 의미이다.

 

stack	deque
top()	back()
push(x)	push_back(x)
pop()	pop_back()

실제로 deque 자료구조는 앞쪽과 뒤쪽 모두 push, back이 가능한 자료구조이기 때문에 stack 자료구조 대신 사용할수도 있다.

 

deque<int> st;
st.push_back(1);
st.push_back(2);
st.push_back(3);
        
vector<int> arr(st.size());
        
// copy st to arr
copy(st.begin(), st.end(), arr.begin());

 

다만, 초반에 언급했던 stack의 목적인 컨테이너 요소의 접근을 막지는 못하기 때문에,

개발자가 tc를 강화시킨다던가, 경각심을 길러 stack의 목적으로 사용하는 deque인 경우 push_front(), push_back() 같은 함수들은 사용하지 않게 주의해야 한다.

---

참고

www.quora.com/Can-you-copy-values-from-a-stack-to-a-vector-using-STL-in-C

www.cplusplus.com/reference/stack/stack/

www.cplusplus.com/reference/deque/deque/