CareerCup

Are we allowed to have an extra stack data structure ?
If so the algorithm is:

Say S1 and S2 are the 2 stacks, then
enqueue (data) : push data into S1
dequeue:
pop each element in S1 and push it to S2.
Return/remove the top of S2 as the dequeue result.
Pop and push back all elements in S2 to S1.

Basically you are retrieving the last element inserted into the stack S1 by storing all the other elements temporarily into a temp stack.

Hi CS
It is not necessary to "Pop and push back all elements in S2 to S1" in your solution. The next time Pop is called, the topmost item in S2 can be returned. Push will just add the item to S1.
Once S2 is empty and Pop is called, all elements from S1 can be moved to S2 and the topmost item on S2 returned.

To come up with a more efficient solution, the question you have to ask is whether or not you can use additional data structures. If you can use a simple array to keep track of the elements pushed to and popped from the stack you can easily determine which element you need to return during queue and enqueue.

#include <stack>

std::string deQ(std::stack<std::string>& s)
{
std::string tmp;
std::string val;
if(s.size() > 0)
{
tmp = s.top();
s.pop();
}
if(s.size() > 0)
{
val = deQ(s);
s.push(tmp);
}
else
return tmp;
return val;
}


void main()
{
std::stack<std::string> s;
s.push("one");
s.push("two");
s.push("three");
s.push("four");
std::cout << "The value is : " << deQ(s) << std::endl;
}

hw can there be 2 return statement ??

/* QUEUE USING STACK */

#include<stack>
#include<iostream>

using namespace std;

stack<int> S1;
stack<int> S2;

void enQ(int k)
{
     S1.push(k);
     
     }
     
int deQ()
{
    int t,retv;
    
    if(S2.empty())
    {
     
     while(!S1.empty())
     {
       t=S1.top();
       S1.pop();
       S2.push(t);
       }
       
        retv=S2.top();
        S2.pop();
        return retv;
        }
      
    else
    {
        retv=S2.top();
        S2.pop();
        return retv;
       
        } 
        
        }

I am not able to understand one thing in the above solution.
Suppose I have for element in queue, so the pic is like below
S1 S2
4 1
3 2
2 3
1 4
I did 4 deQ(). Then i did another deQ(). what will it return.. it should show that Q is empty.. right. But how it is maintain in the above code??????????????

Sand: your basic understanding of stack and queue is incomplete, have a look here :
http://en.wikipedia.org/wiki/stack_data_structure
http://en.wikipedia.org/wiki/queue_data_structure

Can you please suggest if my algo is right?

public int queFStack(Stack s)
   {
         int value;

         if(s.Count() == 1)
           {
             value = s.pop();
             return(value);
           }
         else
           {
             int m = s.pop();
             value = queFStack(s);
             s.push(m);
             return(value);
           }
   }

The main logic of this code is using internal stack.

wow..this algo for dequeue looks just perfect..i.e ofcourse using an internal stack