Wednesday 19 October 2016

A Tale of Two Stacks (CTCI)

Problem: A Tale of Two Stacks
Implement Queue with Stacks

class MyQueue {
  
    public:
        stack<int> stack_newest_on_top, stack_oldest_on_top;   
        void push(int x) {
            stack_newest_on_top.push(x);
        }

        void pop() {
            if(!stack_oldest_on_top.empty())
                stack_oldest_on_top.pop();
            else 
            {
                while(!stack_newest_on_top.empty())
                {
                    stack_oldest_on_top.push(stack_newest_on_top.top());
                    stack_newest_on_top.pop();
                }
                stack_oldest_on_top.pop();
            }
        }

        int front() {
            if(!stack_oldest_on_top.empty())
                return stack_oldest_on_top.top();
            else 
            {
                while(!stack_newest_on_top.empty())
                {
                    stack_oldest_on_top.push(stack_newest_on_top.top());
                    stack_newest_on_top.pop();
                }
                return stack_oldest_on_top.top();
            }
        }
};

No comments:

Post a Comment