Monday, July 6, 2015

LeetCode OJ - Implement Queue using Stacks

Problem:

Please find the problem here.

Solution:

As we are required to use stack, there is no other way to store an element, so we simply save them in a stack (call it A). so that is push().

Now we need to peek()/pop(), we have to access the bottom of the stack to achieve first in first out, so we have to pop() them all to get to the end of it.

But what to do with the elements, we have the save them somewhere, right? So just save them in another stack (call it B).

Turn out that pop from one stack, push to another stack solution reverse the order, so next time if we need to pop from stack B, we just pick one from that stack.

Further push()? Nothing else need to be done, just push to stack A.

The following cartoon show how it works (stack top on the left)

queue.push(1)

A: 1
B: empty

queue.pop()

Flow the elements first

A: empty
B: 1

And then pop from B

A: empty
B: empty

queue.push(1)

A: 1
B: empty

queue.push(2)The

A: 2 1
B: empty

queue.pop()

Flow the elements first

A: empty
B: 1 2

And then pop from B

A: empty
B: 2

queue.pop()

No need to flow element this time as we already have some element around, just pop from B

A: empty
B: empty

See, that's how it works - the fun is in the analysis. It looks like that a pop operation could be $ O(n) $, and indeed it is, from a full stack to access the bottom take significant time. But we could look at it in a amortized way. Every element flow through the stack through two push() and one two pop() operation. So if we do $ n $ operation, the total time is guaranteed to be $ O(n) $, an amortized bound is usually good enough for practical purposes, except we occasionally may take a hit.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/implement-queue-using-stacks/

#include "LEET_IMPLEMENT_QUEUE_USING_STACKS.h"
#include <map>
#include <iostream>
#include <stack>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_IMPLEMENT_QUEUE_USING_STACKS
{
    class Queue {
    public:
        // Push element x to the back of queue.
        void push(int x)
        {
            input_stack.push(x);
        }

        // Removes the element from in front of queue.
        void pop(void)
        {
            if (this->output_stack.size() == 0)
            {
                this->flow();
            }
            output_stack.pop();
        }

        // Get the front element.
        int peek(void)
        {
            if (this->output_stack.size() == 0)
            {
                this->flow();
            }
            return output_stack.top();
        }

        // Return whether the queue is empty.
        bool empty(void)
        {
            return this->input_stack.size() == 0 && this->output_stack.size() == 0;
        }
    private:
        stack<int> input_stack;
        stack<int> output_stack;
        void flow()
        {
            while (!this->input_stack.empty())
            {
                this->output_stack.push(this->input_stack.top());
                this->input_stack.pop();
            }
        }
    };
};

using namespace _LEET_IMPLEMENT_QUEUE_USING_STACKS;

int LEET_IMPLEMENT_QUEUE_USING_STACKS()
{
    Queue queue;
    cout << queue.empty() << endl;
    queue.push(1);
    cout << queue.peek() << endl;
    queue.pop();
    cout << queue.empty() << endl;
    queue.push(1);
    queue.push(2);
    cout << queue.peek() << endl;
    queue.pop();
    cout << queue.peek() << endl;
    queue.pop();
    return 0;
}

No comments :

Post a Comment