CareerCup

T mainval;
public Enque(T x)
{
	que.Push(x);
}
public bool Deque()
{
	if(!que.isEmpty())
	{
		T val = que.Pop();
		if(!Deque())
		{
			mainval = val;
		}
		else
		{
			que.Push(val);
		}
		return true;
	}
	return false;
}
int main()
{
Stack <T> que;
}

Use 2 stacks..push into the 1st stack..whenever you want to pop an element pop all elements from first stack & push them in second and pop the element from second. once the the elements in 2nd stack is over, on the next pop again transfer all the elements from 1st stack to second. So its basically you are pushing the elements into the first stack & popping from second.
so Push() would involve just one stack operation. Pop() at times would involve operations on both stacks(the amortized cost of this can be proved to be 1). IsEmpty() would involve checking both the stacks

public class QueueWithTwoStacks implements Queue{
Stack stack1 = null;
Stack stack2 = null;

public QueueWithTwoStacks(){
stack1 = new LLStack();
stack2 = new LLStack();
}

//default implementation
public boolean isEmpty(){
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.isEmpty();
}

public void enQueue(Object data){
stack1.push(data);
}

public Object deQueue(){
if(!stack2.isEmpty()){
return stack2.pop();
}else{
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
}

If no extra space is allowed, I guess we have to use implicit stack space.(use recursive method)

// Queue using two stacks.
// Enqueue is guaranteed O(1).
// Dequeue is _amortized_ O(1).
        
class Queue <T> {
    
public Enque(T x) {
    
    enQ.Push(x);
}
    
public T Dequeue() {
    
    if (dQ.IsEmpty()) {
    
        while(!enQ.IsEmpty()) {
        
            dQ.Push(enQ.Pop());
        }
    }

    return dQ.Pop();
}
    
private:
    Stack <T> enQ;
    Stack <T> dQ;
}

// using one stack
public enque(T x) {

stack.push(x);
}

public T dequeue() {
T a = stack.pop();
if(stack.empty())
return a;
else
T b= deque();
stack.push(a);
return b;
}

I would say take two stack for a queue, and implement either deque() or enque using pop() and push() to maintain FIFO behavior.

The Enque() version modified from above solution:



class Queue <T> {

public Enque(T x) {

//get all elements out to temp stack (dQ)
while(!enQ.IsEmpty)
dQ.Push(enQ.Pop());

//put the new element to the bottom of storage stack (enQ)
enQ.Push(x);

//get back previous elements form temp stack (dQ)
while(!dQ.IsEmpty)
enQ.Push(dQ.Pop());

}

public T Dequeue() {
return enQ.Pop();
}

private:
Stack <T> enQ;
Stack <T> dQ;
}

This is a tower of hanoi problem, where the size of the disk can be indicates the position of the element.
-> For example, consider you have 1 stack for storing elements and 2 temporary stacks you can use to move elements and the size of the queue is 'N'.
Then once the queue is full i.e. you kept pushing into the 1st stack. You would have to move the elements (2^N)-1 times inorder to remove the first element in the stack.
-> Am not sure if there is an existing solution for 'K' towers of hanoi problem but I have the solution (in constant time ha haa :D ). So if creating a stack has an overhead then we can compute (using my solution) the maximum number of stacks we can use and keep the complexity low at the same time. But if there's no complexity in creating more and more Stacks then we can use the below solution.

// Create an array of Stack objects and use it as a regular array for implementing queue.
Queue
{
   public:
     Queue(int queueSize) : m_queueSize(queueSize), m_currentIndex(0), m_startIndex(0)
     {
       if(m_queueSize == 0)
       {
          m_queueSize = 0;
       } 
     }
     void Push()
     {
       if(m_data[m_currentIndex].empty())
       {
         m_data[m_currentIndex].Push();
         m_currentIndex = (m_currentIndex+1) % m_queueSize;
       }
       else
       {
         Pop();
         m_currentIndex = m_startIndex;
         m_data[m_currentIndex].Push();
         m_currentIndex = (m_currentIndex+1) % m_queueSize;
       }
     }
     void Pop()
     {
	if(!m_data[m_startIndex].empty())
	{
         m_data[m_startIndex].Pop();
         m_startIndex = (m_startIndex+1) % m_queueSize;
	}
	else
	{
	  //empty queue;
	}
     }
    bool IsEmpty()
    {
      return m_data[m_startIndex].IsEmpty();
    }
    private:
     Stack m_data[n];
     int m_queueSize, m_currentIndex, m_startIndex;
};

Keep a list of stacks each having a fixed size (suppose each has size 10). If last stack is full, add new stack to the list and keep adding elements to the last stack. Top() and Pop() will be performed on first list of the stack list. Push() will be performed on last stack of the list.

So Pop() and Top() will take only 10 or (size of stack) operations (O(1)). While Push() will take just one operation.

We need two stacks to implement a queue. However that second stack can be emulated with recursion.

Here you go with only one stack using recursion

T mainval;
public Enque(T x)
{
	que.Push(x);
}
public bool Deque()
{
	if(!que.isEmpty())
	{
		T val = que.Pop();
		if(!Deque())
		{
			mainval = val;
		}
		else
		{
			que.Push(val);
		}
		return true;
	}
	return false;
}
int main()
{
Stack <T> que;
}

// Take a stack and invert it's
// elements into a queue. pop and
// return the top of this queue.
invert(stack, queue) {
if (stack.isempty())
return queue.pop();
queue.push(stack.pop());
return invert(stack, queue);
}

// As long as the 'queue' is'nt empty keep
// returning from it. invert stack when
// it is.
pop() {
if (!queue.isempty())
return queue.pop();
return stack.getval();
}

// always push into the stack
push() { stack.push(); }