**Problem:**Given a stack data structure that supports standard operations like push() and pop(), implement a queue using given stack data structure.

**Solution:**Use two stacks.

**Implementation:**

class Queue

{

public:

Queue(){}

void insert(int i);

int remove();

bool isEmpty();

~Queue(){}

private:

std::stack<int> st1, st2;

};

void Queue::insert(int i)

{

st1.push(i);

}

int Queue::remove()

{

if(isEmpty())

return -1; //Error

if(st2.empty())

{

while(!st1.empty())

{

st2.push(st1.top());

st1.pop();

}

}

int retval = st2.top();

st2.pop();

return retval;

}

bool Queue::isEmpty()

{

return st1.empty() && st2.empty();

}

**Complexity:**insert - O(1), remove - O(n)

## No comments:

## Post a Comment