Skip to content

Instantly share code, notes, and snippets.

@kartikkukreja
Created October 27, 2016 04:01
Show Gist options
  • Save kartikkukreja/3ea8b76ddd0a56bbe8bc5c1c457f9870 to your computer and use it in GitHub Desktop.
Save kartikkukreja/3ea8b76ddd0a56bbe8bc5c1c457f9870 to your computer and use it in GitHub Desktop.
Queue with two stacks
template <typename T>
class QueueWithTwoStacks {
private:
stack<T> S1, S2;
public:
void enqueue(T& x) {
S2.push(x);
}
T dequeue() {
if (S1.empty()) {
while (!S2.empty()) {
T top = S2.top(); S2.pop();
S1.push(top);
}
}
if (S1.empty())
throw "queue empty";
T top = S1.top(); S1.pop();
return top;
}
int size() {
return S1.size() + S2.size();
}
bool empty() {
return S1.empty() && S2.empty();
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment