#include <iostream>
#include <stack>
using namespace std;
template<typename T>
class Queue2Stack
{
stack<T> in, out;
public:
void push( const T& what )
{
while( !out.empty() )
{
in.push( out.top() );
out.pop();
}
in.push( what );
}
T pop()
{
while( !in.empty() )
{
out.push( in.top() );
in.pop();
}
T result = out.top();
out.pop();
return result;
}
};
int main() {
Queue2Stack<int> st;
cout << "push 1, 2" << endl;
st.push(1);
st.push(2);
cout << "pop " << st.pop() << endl;
cout << "push 3, 4" << endl;
st.push(3);
st.push(4);
cout << "pop " << st.pop() << ", ";
cout << st.pop() << ", ";
cout << st.pop() << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RhY2s+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0ZW1wbGF0ZTx0eXBlbmFtZSBUPgpjbGFzcyBRdWV1ZTJTdGFjawp7CglzdGFjazxUPiBpbiwgb3V0OwoJcHVibGljOgoJdm9pZCBwdXNoKCBjb25zdCBUJiB3aGF0ICkKCXsKCQl3aGlsZSggIW91dC5lbXB0eSgpICkKCQl7CgkgICAgCWluLnB1c2goIG91dC50b3AoKSApOwoJICAgIAlvdXQucG9wKCk7CgkJfQoJCWluLnB1c2goIHdoYXQgKTsKCX0KCQoJVCBwb3AoKQoJewoJCXdoaWxlKCAhaW4uZW1wdHkoKSApCgkJewoJICAgIAlvdXQucHVzaCggaW4udG9wKCkgKTsKCSAgICAJaW4ucG9wKCk7CgkJfQoJCVQgcmVzdWx0ID0gb3V0LnRvcCgpOwoJCW91dC5wb3AoKTsKCQlyZXR1cm4gcmVzdWx0OwoJfQp9OwoKaW50IG1haW4oKSB7CglRdWV1ZTJTdGFjazxpbnQ+IHN0OwoJY291dCA8PCAicHVzaCAxLCAyIiA8PCBlbmRsOwoJc3QucHVzaCgxKTsKCXN0LnB1c2goMik7Cgljb3V0IDw8ICJwb3AgIiA8PCBzdC5wb3AoKSA8PCBlbmRsOwoJY291dCA8PCAicHVzaCAzLCA0IiA8PCBlbmRsOwoJc3QucHVzaCgzKTsKCXN0LnB1c2goNCk7Cgljb3V0IDw8ICJwb3AgIiA8PCBzdC5wb3AoKSA8PCAiLCAiOwoJY291dCA8PCBzdC5wb3AoKSA8PCAiLCAiOwoJY291dCA8PCBzdC5wb3AoKSA8PCBlbmRsOwoJCglyZXR1cm4gMDsKfQ==