Queue Implementation using Stack | O(1) Push and Pop Operations

In case you are thinking to buy courses, please check below:

Watch at 1.25x for better experience ..
---------------------------------------------------------------------------------------------------------------------------

Use "TAKEUFORWARD" coupon to get 10% discount.
---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

#dsa​ #striver #leetcode

[takeUforward]

Complete DSA playlists in description..

Instagram: striver_79

[adityachauhan]

Today at 6:00 am I watched this video and at 2:00 PM in my 2nd interview round the interviewer asked the same question and now I am typing this message after getting a intern at Service Now

[anshumaan]

For, *empty()* use, *return !(input.size() | output.size());*

If anyone of the stacks has still some element, means queue is not empty and return false
I hope it helps 🙂🙂

[advait]

guys if u don't get the intuition at first don't give up try watching the video twice or thrice u will surely get it.

[Neo-mxyf]

For anyone confused.. Amortised cost is basically the average time complexity in worst case.In last algorithm, u can think of it like every element will undergo 4 operations in the worst case :(1 push, 1 pop, 1 push, 1 pop)... For eg, say u do n operations: worst case will be u do n/2 pushes and n/2 pops... total time taken will be: (n/2+n/2x3)=2n.. Then if we find avg time complexity here = (2n)/2=2... hence it is O(1) amortised cost...

[pratheekhebbar]

bro ur explanation is too easy to understand and its helpful for those who are learning coding.

[VaasaviPasupulati]

Just discovered your channel 2 days ago...awesome explanation🙌🏼
Following your SDE Sheet😇

[MdArif-ycyj]

bhaiya kyaa kahu aapko mainn schh kah rha hu bhaiii aap mere teacher hote to main 10 lpa se upar crack krta maine late start kiyaa hu padhai ..bhai mere yaha 1 mahine bad cimpanies aane wali haii..main aapke questions follow kr rha hu aurt bhaiii sb smjh aa rha haii, , bas tress ke sre vedios bana do bhaiii, , jaldi se..aur poore sde sheeta ka jaldi se ..shukriyaa bhaii is madad ke liye ..love you bhaiiii

[anchitbhushan]

Depending on how frequent the push and pop calls are, we have a choice to either make push operation in constant time or make pop and peek operation in constant time. we cannot have both.

[phanisriimmalaraju]

Thankyou!!!! This video helped me in my exams

[paragroy]

Nice explanation your videos are really good...please keep on making such videos.

[kamyakamya]

Great Explanation . Thanks for sharing, but could u help in finding the ans of question-
Why this implementation is used when we have Queue as Data Structure, what is the use case for this implementation? It would be helpful if u could help in finding it's answer.

[elanchezian]

When I think of logic, I am getting only the brute force logic. But if I see the answer I am understanding the logic and if any similar kind of problems occurs, I am able to use this logic in some other problems.



But I am never getting the optimal logic so far by not seeing the solution. I am only getting the brute force logic.



Now I feel like memorizing the logics but problem solving means deducing the solution on the spot, right? without having seen the similar problem before.



I dont understand what I am doing, is it problem solving or memorizing the logics?



However in any interviews, the questions will be somehow new only. It is not guaranteed that I will get only the questions which I have practised.



Please suggest me on this.

[mrrealnobody]

this topic is the second hardest thing in this room 🗿

[HGAMES]

Tomorrow I have mid exams for data structures and here I am watching this hoping to ace the exam.

[souravjoshi]

You can keep a variable to keep track of top element and it will always be O(1) then. My code below (Accepted)
class MyQueue {
public:
stack<int> st1;
stack<int> st2;
int peekEl = -1;
/** Initialize your data structure here. */
MyQueue() {

}

/** Push element x to the back of queue. */
void push(int x) {
if(st1.empty())
peekEl = x;
st1.push(x);
}

/** Removes the element from in front of queue and returns that element. */
int pop() {
//O(n) only when st2 is empty()
if(st2.empty()) {
while(!st1.empty()) {
st2.push(st1.top());
st1.pop();
}
}

int x = st2.top();
st2.pop();
return x;
}

/** Get the front element. */
int peek() {
return st2.empty() ? peekEl : st2.top();
}

/** Returns whether the queue is empty. */
bool empty() {
return st1.empty() && st2.empty();
}
};

[csea__shayoribhowmick]

Understood completely thank you striver

[shivamingole]

in second explanation (10:22)we cant put the while loop inside the else because as at last the top gives 6 as ans but the top should give 2 as ans as it was the first element

[deweshjha]

Thankyou Great content hamesha ki tarah

[gyaneshjha]

If someone is stucking at leetcode in empty() function just try with this piece of code
Return