## Thursday, August 6, 2015

### LeetCode OJ - Implement Stack using Queues

Problem:

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;
}