Implement Queue using Stack.
The complexity of this approach relies on the fact that queue is a LIFO structure (Last-In, First-Out), where stack is a FIFO (First-In, First-Out) structure.
In queue push adds element at the end of the queue, where pop takes element from front of the queue.
In stack push adds element at the front of the stack and pop takes element again from from of the stack.
In order to solve this problem you will need to use two stacks.
Because you are using stack there will be always some performance problem you need to take into consideration. You can either optimize this algorithm for push or pop.
// Queue implementaion using Stack // Optimized for push operation. // Note: This queue is not thread-safe. class Queue { public: void push(int elem) { m_stack.push(elem); } int pop() { if (m_stack.empty()) throw exception(); Stack helperStack; // find last element while (!m_stack.empty()) { helperStack.push(m_stack.pop()); } int elem = helperStack.pop(); // restore stack while (!helperStack.empty()) { m_stack.push(helperStack.pop()); } return elem; } bool empty() { return m_stack.empty(); } private: Stack m_stack; // by default empty };
// Queue implementaion using Stack // Optimized for series of pushes and series of pop operations. class Queue { public: void push(int elem) { // prepare Queue for push if (!m_stackForPop.empty()) reverse(m_stackForPop, m_stackForPush); m_stack.push(elem); } int pop() { // prepare Queue for push if (!m_stackForPush.empty()) reverse(m_stackForPush, m_stackForPop); if (m_stackForPop.empty()) throw exception(); return m_stackForPop.pop(); } bool empty() { return m_stackForPop.empty() && m_stackForPush.empty(); } private: void reverse(Stack &source, Stack &dest) { while (!source.empty()) { dest.push(source.pop()); } } Stack m_stackForPop; Stack m_stackForPush; };