Thursday, August 6, 2015

LeetCode OJ - Implement Stack using Queues

Problem:

Please find the problem here.

Solution:

Queue cannot reverse order - there is no way I can reverse a queue to pop it out. So I have to choose, whether I invert it during push or pop.

It makes more sense to do that during push(), because one can call top() many times, and if I keep the queue in the order I wanted, it will be simply trying to obtain the front of the queue many times for top(), pop() would be easy too.

There is a 'trick' - I could have implement that as well, effectively using the queue as a stack cell and implement a linked list based stack. That I consider a 'cheat' instead, so I abandoned that approach.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/implement-stack-using-queues/

#include "LEET_IMPLEMENT_STACK_USING_QUEUES.h"
#include <queue>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_IMPLEMENT_STACK_USING_QUEUES
{
    class Stack
    {
    private:
        queue<int> data;
    public:
        // Push element x onto stack.
        void push(int x)
        {
            data.push(x);
            for (unsigned int i = 0; i < data.size() - 1; i++)
            {
                data.push(data.front());
                data.pop();
            }
        }

        // Removes the element on top of the stack.
        void pop()
        {
            data.pop();
        }

        // Get the top element.
        int top()
        {
            return data.front();
        }

        // Return whether the stack is empty.
        bool empty()
        {
            return data.empty();
        }
    };
};

using namespace _LEET_IMPLEMENT_STACK_USING_QUEUES;

int LEET_IMPLEMENT_STACK_USING_QUEUES()
{
    Stack stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    cout << (stack.top() == 3) << endl;
    stack.pop();
    cout << (stack.top() == 2) << endl;
    stack.pop();
    cout << (stack.top() == 1) << endl;
    stack.pop();
    cout << (stack.empty()) << endl;
    return 0;
}

No comments :

Post a Comment