#algorithm# Implement queue by 2 stacks.

queue_by_stack.cpp

#include <stack>
#include <iostream>
#include <cassert>
#include <LazyTest.h> // my unittest framework

// use 2 stacks to implement a queue - first in first out
// push - pop - front - back - size - empty
// Imagine that 2 stack bend as a "U" shape, with each top as back and front
template <class T>
class queue
{
public:
	void push_back(const T& value) // push to back
	{
		s1.push(value);
	}
	
	void pop_front()				// pop the front
	{
		assert(!empty());
		ensure_s2();
		s2.pop();
	}
	
	T back()
	{
		assert(!empty());
		ensure_s1();  // you need to move elements from s2 to s1
		return s1.top();
	}
	
	T front()
	{
		assert(!empty());
		ensure_s2();
		return s2.top();
	}
	
	size_t size()
	{
		return s1.size() + s2.size();
	}
	
	bool empty()
	{
		return s1.empty() && s2.empty();
	}
	

private:
	void ensure_s2()
	{
		if(s2.empty())
		{
			while(!s1.empty()) 
			{
				s2.push(s1.top());
				s1.pop();
			}	
		}
	}

	void ensure_s1()
	{
		if(s1.empty())
		{
			while(!s2.empty()) 
			{
				s1.push(s2.top());
				s2.pop();
			}	
		}
	}

	
private:
	std::stack<T> s1;
	std::stack<T> s2;
};

TESTCASE(test_empty_queue)
{
	queue<int> q;
	ASSERT_TRUE(q.empty());
	ASSERT_TRUE(q.size() == 0);
}

TESTCASE(test_one_element_queue)
{
	queue<int> q;
	q.push(10);
	ASSERT_TRUE(q.size() == 1);
	
	ASSERT_TRUE(q.front() == 10);
	ASSERT_TRUE(q.back() == 10);

	q.pop();
	ASSERT_TRUE(q.empty());
}

TESTCASE(test_common_queue)
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

	ASSERT_TRUE(q.front() == 1);
	ASSERT_TRUE(q.back() == 4);

	q.pop();
	ASSERT_TRUE(q.front() == 2);

	q.pop();
	ASSERT_TRUE(q.size() == 2);

	q.push(5);
	q.push(6);

	ASSERT_TRUE(q.size() == 4);
	ASSERT_TRUE(q.back() == 6);
}

int main()
{
	RUN_ALL_CASES();
	return 0;
}