Implementing stack using queue
Two methods to solve this
1-) Making push method costly
2-) Making Pop method costly
1- Making Push operation costly
Logic-
First make two queues then you want to push elements into the queue so first pushed element will store in the q2 and then add all the element from q1 to with q2 and then swap it to q1 and the process continues till last element .
for better explanation please watch out the video
Must watch out this video to understand the logic with visualization and animation so must watch it.
Coding
#include <bits/stdc++.h>
using namespace std;
class Stack
{
public:
int N;
queue<int> q1;
queue<int> q2;
Stack() // constructor
{
N = 0; // size initialize with 0
}
void push(int val)
{
q2.push(
val); // according to our algo we first enter
// our push value into second queue
while (!q1.empty())
{
q2.push(q1.front());
// then according to algo now we have to put all
// the element that is present in q1 add into q2
// till q1 is not empty
q1.pop(); // pop that element from q1
}
// to swap
queue<int> temp = q1; // make a temporary queue
q1 = q2;
q2 = temp;
}
void pop()
{
q1.pop();
N--;
}
// find top value
int top() { return q1.front(); }
// give the current size of stack
int size() { return N; }
};
int main()
{
Stack st;
st.push(2);
st.push(5);
st.push(8);
st.push(4);
cout << st.top() << endl;
st.pop();
cout << st.top() << endl;
st.pop();
cout << st.top() << endl;
st.pop();
cout << st.top() << endl;
st.pop();
st.pop();
cout << st.size() << endl;
return 0;
}
2-) Making Pop method costly
Logic-
First make two queues then you have to then push values into q1 then here is the important step for this step 2 so we have to pop the top element (first the value insert into queue) from the stack and add the rest values into Q2 and then swap it
for better explanation please watch out the video
Must watch out this video to understand the logic with visualization and animation so must watch it.
Coding
#include <bits/stdc++.h>using namespace std;class Stack{int N;queue<int> q1;queue<int> q2;public:Stack() //constructor{N = 0; //size initialize with 0}void pop(){if (q1.empty()) //check there if something is present{return;}while (q1.size() != 1) //jabtak q1 ek value nhi bach ta tab tak continue{q2.push(q1.front()); //and add into q2q1.pop(); //then pop it}q1.pop();N--;//to swapqueue<int> temp = q1; //make a temporary queueq1 = q2;q2 = temp;}void push(int val){q1.push(val);N++;}// Top valueint top(){if (q1.empty()){return -1;}while (q1.size() != 1){q2.push(q1.front());q1.pop();}int ans = q1.front();q2.push(ans);//to swapqueue<int> temp = q1; //make a temporary queueq1 = q2;q2 = temp;return ans;}int size(){return N;}};int main(){Stack st;st.push(1);st.push(3);st.push(7);st.push(9);cout << st.top() << endl;st.pop();cout << st.top() << endl;cout << st.size() << endl;}
Post a Comment
Post a Comment
Please do not spam in comment