# Queue with two stacks

Implement queue with two stacks

template<class T> class StackNode { public: StackNode(T initVal) { value = initVal; next = NULL; } T value; StackNode* next; }; template<class T> class Stack { public: Stack() { top = NULL; } ~Stack() { StackNode<T> *node = top; while (node) { StackNode<T> *next = node->next; delete node; node = next; } } bool isEmpty() { return (top == NULL); } void push(T value) { StackNode<T> *node = new StackNode<T>(value); if (top) { node->next = top; } top = node; } T pop() { assert(top); T val = top->value; StackNode<T> *next = top->next; delete top; top = next; return val; } StackNode<T> *top; }; template<class T> class Queue { public: Queue() {} ~Queue() {} void add(T value) { inStack.push(value); } T remove() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.pop(); } Stack<T> inStack; Stack<T> outStack; };