CareerCup

Use two stacks:

For deQ if the 1st stack is empty, check the 2nd stack and do a pop from the 2nd and push into the 1st until 2nd stack is empty. When done or if 1st stack is not empty pop the first element and return it.

For enQ always push into the 2nd stack and if is full then do another round of push/pops and then do a push.

use two stacks in the following way:

Initially both the stacks are at the same position

1. Stack 1 at the left end of the array
2. Stack 2 at the right end of the array
3. Use Stack 1 to deque
4. Use Stack 2 to enqueue.
5. Make sure that collision is handled.

Template<typename T> Class StackQueue
{
	stack<T> EnQStack; //stack to use for enqueue operation
	stack<T> DQStack; //stack to use for dequeue operation
     public:
	void enQ(T data)
	{
		EnQStack.Push(data);
	}
	
	T deQ()
	{
		//this means that the DQStack is empty, in this case need to transfer contents from EnQStack to DQStack
		if (DQStack.Empty()) then TransferStack(EnQStack,DQStack);
		
		return DQStack.Pop();
	}

	void TransferStack(stack<T> From, stack<T> To)
	{
		T data;
		while (!From.empty())
		{
			data = From.Pop();
			To.Push(data);
		}
	}
}

garimaa.blogspot.in/2012/04/program-3rd-in-c.html

i think we would also be needing a temporary stack
imagine a situation where we have stack 2 full and stack 1 not full
now even though we have space left we cant utilize it
so for such situations we need to transfer whole of stack 2 to temp stack
pop it and transfer it to stack1 till its full
and transfer back the remaining elements to stack2

i think we would also be needing a temporary stack
imagine a situation where we have stack 2 full and stack 1 not full
now even though we have space left we cant utilize it
so for such situations we need to transfer whole of stack 2 to temp stack
pop it and transfer it to stack1 till its full
and transfer back the remaining elements to stack2

1 # !/usr/bin/python
  2 # -*- encoding: utf-8 -*-
  3 
  4 class DoubleStackQueue:
  5 
  6     def __init__(self):
  7         self.first_stack = []
  8         self.second_stack = []
  9 
 10     def en_queue(self, el = None):
 11         self.first_stack.append(el)
 12 
 13     def de_queue(self):
 14         if len(self.second_stack) == 0:
 15             while len(self.first_stack) != 0:
 16                 self.second_stack.append(self.first_stack.pop())
 17         return self.second_stack.pop()
 18 
 19 if __name__ == '__main__':
 20     queue = DoubleStackQueue()
 21     queue.en_queue(1)
 22     queue.en_queue(2)
 23 
 24     print queue.de_queue()
 25     print queue.de_queue()
 26 
 27     queue.en_queue(3)
 28     print queue.de_queue()

why can't we use a stack implemented using linked list ? Then the solution will be available with just one stack, right?

If enQ, add the node to the last.

If deQ, move the head pointer by one node.