Let us understand how to prepare queue using two stacks
When we say we have to prepare queue using stack that means all the operations of stack should be used to get the queue functionality.
Queue has FIFO property i.e. First-In First-Out i.e. element which is inserted first , same element should be removed or pop first.
Consider that we have two stacks s1 and s2. Initially both the stacks are empty. Here we have used Stack Using Linked List.
When we push any data in to stack, we have to make sure that when pop happens, it happens from the top(since we are using stack) and that top element should be first element that was pushed(because we want queue functionality) not the last element.
#include <iostream>
using namespace std;
class queue {
stack s1;
stack s2;
public:
void insert(int data) {
while (!s1.isEmpty()) { //1st Step
s2.push(s1.pop());
}
s1.push(data); // 2nd Step
while (!s2.isEmpty()) { //3rd Step
s1.push(s2.pop());
}
}
int get() {
return s1.pop();
}
};
int main() {
queue q1;
q1.insert(10);
q1.insert(20);
cout << "Element: " << q1.get() << endl;
q1.insert(30);
q1.insert(40);
cout << "Element: " << q1.get() << endl;
cout << "Element: " << q1.get() << endl;
cout << "Element: " << q1.get() << endl;
cout << "Element: " << q1.get() << endl;
return 0;
}
Output:
10
20
30
40
-1 //Empty Queue
Let us understand output of insert as per the main function.
Insert 10: As part of first insert, only 2nd step of insert function will be used since s1 and s2 are empty
Insert 20:
Stack data after 1st Step of insert function:
Stack data after 2nd Step of insert function:
Stack data after 3rd Step of insert function:
get:
Stack data after get function:
Now, as part of get, pop is performed on S1. So it will return 10 i.e. element is pop(get) which is inserted first. Similarly others insert will happen.