Implement Stack using Queues - Leetcode 225 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
4:45 - Coding Explanation

leetcode 225

#stack #queue #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[hrvmhv]

As per the problem statement, you are only supposed to use valid queue operations i.e. push to back, peek/pop from front, size and is empty.
So by that logic top() method is incorrect. If you write the for loop in push() then you can use peek() method in top().

[Mykelboachie]

Looks like you are starting to make these every day which is great news! Thank you

[green]

I'm so glad you point out at the beginning that it would take O(n) to implement the pop operation. I was thinking to myself "that doesn't even make sense to use a queue, I'll have to iterate through the whole thing to pop the next stack item. (I literally was wracking my brain before watching the solution video about who I could possibly do that in O(1)).

[ngneerin]

The reason leetcode is showing poor performance is that there are lot of people who have implemented it like a stack and not queue that behaves like stack

[blossombabalola]

This explanation is top tier. Thank you Neet

[CEOofTheHood]

Hi Mr.Neet, you have about covered most graph topic but one that seems to be missing is strongly connected components. Would really appreciate it if you could teach that when you have time.

[CodeShode]

performance is relative, and many people have implemented it using stacks which pushes your solution towards the less efficient ones.

[jayeshvarma]

Here, we are using deque funtionality in case of getting top element
But we should use it as queue
So we cannot directly get element from rear
So it is wrong i think
For that we should first perform operation like pop then we can get top element without popping

[flatmapper]

Leetcode says:
"You must use only standard operations of a queue, which means that only `push to back`, `peek/pop from front`, `size` and `is empty` operations are valid."
And here you used self.q[-1] which is accessing the last element which is not allowed

[aryamankukal]

how are you allowed to use q[-1] if you need to use only queue operations

[xkzyngo]

Dear Neet, can you teach us about 232. Implement Queue using Stacks as well? 232 is on the Grind 75 list

[rahulprasad]

If you know its length and are accessing it using -1 anyways then why not just use pop or return the -1 element and then do del q[-1]?

[ericndirangu]

When using two queues the runtime and space is over 70% ...strange

[pichu]

May i ask what app do you use to annotate in the video?

[arpitjainaj]

Better to use queue, from queue import Queue. This makes more sense bcoz u r using deque and only implementing queue feature, so y not use queue. By the way nice explanation.

[waseem_ibrahim]

For any one who is saying that the top() function is implemented properly, the idea behind using the index of [-1] as he did was that there is already a function for queues called "peek" that you could use that gives you the last element directly, so it is safe to say that it is implemented, and we always have an idea of what the top element would be.
However, if anyone faces an issue in interview where the interviewer still wants an implementation for the top() function, you could make sure to keep O(1) for it by using a value that always tracks the top value, which would be always the last one pushed, or the 2nd to last one after popping

Code Example:
from collections import deque

class MyStack:

def __init__(self):
self.q1 = deque()
self.peek = None

def push(self, x: int) -> None:
self.q1.appendleft(x)
self.peek = x

def pop(self) -> int:
n = len(self.q1)
for i in range(n - 1):
poped = self.q1.pop()
self.q1.appendleft(poped)

if i == n-2:
self.peek = poped

return self.q1.pop()


def top(self) -> int:
return self.peek

def empty(self) -> bool:
return len(self.q1) == 0

[HoratiuEugenVLAD]

The top() could be implemented much simpler by reusing pop() and push()

def push(self, x: int) -> None:
self.q.append(x)

def pop(self) -> int:
for i in range(len(self.q) - 1):
self.push(self.q.popleft())
return self.q.popleft()

def top(self) -> int:
res = self.pop()
self.push(res)
return res

[VaishnaviMamilla]

if using dequeue we can simply use pop() right it will pop from rear abd behave as a stack why to use popleft

[pinpon]

Might be me, but I find this problem to be unnecessarily complex. It is not hard, but it is just annoying.

[yashsrivastava]

There is no solution for Leetcode 332 Reconstruct Itinerary. Please provide one.