to really demonstrate the benefits of having two queues, it is important to get the oldest and newest values. in a normal stack or queue, getting the highest priority ( newest for stack, oldest for queue) is an O(1) operation. getting the lowest priority (oldest for stack, newest for queue) is O(n). Having a double queue allows us to get highest and lowest priority in O(1), with added spatial complexity.
I agree. Not implementing a method to make use of the primary benefit of this specific data structure-also getting the lowest priority item in O(1)-makes this example much more confusing than it needs to be. If someone asked me to "implement X using two Ys", the first question I would ask is "why?". You know? What is it supposed to accomplish; why might we want to build it that way? Otherwise, in this example, why not use the in-built Queue data structure in Java?
@Bilbo What are you talking about? In first place, having 1 or 2 collections doesn’t change the space complexity, it is still O(n). In second place you can implement double ended queue with a single linked list. In third place, who is “demonstrating the benefits of having 2 queues”? This problem is about being faced with a constraint, not always you can choose the data structure to use, sometimes you gotta be creative and work with what’s available.
I think a good way to explain this is when the oldestOnTop stack becomes empty, we grab the newestOnTop stack, flip it upside down, and it becomes the new oldestOnTop stack.
@@alexnezhynsky9707 to really demonstrate the benefits of having two queues, it is important to get the oldest and newest values. in a normal stack or queue, getting the highest priority ( newest for stack, oldest for queue) is an O(1) operation. getting the lowest priority (oldest for stack, newest for queue) is O(n). Having a double queue allows us to get highest and lowest priority in O(1), with added spatial complexity.
It's called a generic. Basically saying "this could contain any type of data". So this queue could contain int, strings, objects, etc. If she had defined it as MyQueue { private Stack stack1.... } it would only be able to hold integers. Instead she uses type T so the consumer can determine what type it holds. In my code, to use this class, I would define it new MyQueue() or new MyQueue() or new MyQueue()
Would runtimes of these operations be considered amortized O(1)? It seems like it is similar to an ArrayList where in most cases it is O(1) but occasionally everything must be copied over.
Enqueue is obv O(1) (or amortized O(1) if your stack uses a vector, which is the case in Java). Dequeue must be amortized O(1) since the element to be dequeued will have been copied exactly once. This is assuming that the entire queue is emptied before deleting. Otherwise it can be as bad as O(n) -- that is, n copies, but only 1 dequeue operation. However, if you logically amortize the copy operations as part of enqueue (the enqueued element will be copied once in the future), then you can still claim amortized O(1) for dequeue. Because of this, you can claim amortized O(1) for all operations.
Now if we have stack newest on top, I mean stack oldest on top and now we want to peek, I mean dequeue we don't have to move anything into the new array, I mean the new stack Why would a company want to ask this question? It's obviously too confusing to coherently explain even if you've written books about it.
"We need to pop everything off the top", well no, you can just call .shift() in any standard language, but interesting video to explain why this problem would even be conceived.
@@ssshah3333 Oldest item meaning it was the first item placed in the first stack, but then when the items are put in the second stack with Oldest on top, this item is at the top. The old item is at the top of the second stack after moving the items. Do not refer to the word, but the meaning. The command removes the item at top of second stack and this is the oldest item (first item placed in first stack). Hope this makes sense.
w....why would you not use a linked list for this. this is literally why a linked list exists. the time complexity of getting the first or last item from a linked list is O(0).
double checked that there was no sane reason for this and there could be some distributed cloud complexity but the option of a circular array where start and end indexes are stored and updated rather than THE ENTIRE ARRAY COPIED EVERY SINGLE TIME YOU TOUCH ANYTHING confirms the fact that despite having learned some fancy things from very smart people, even the people answering these questions are not very smart. she wrote a book on this. she wrote a book on this. she wrote a book on this. it took me three minutes, which is more time than it took any single person to read the incorrect information that she wrote.
and before you "oh, priorities and whatnot" then use separate priority queues, there, done, checking to see if they're empty every pull is faster than reordering the array
also just because i'm being critical doesn't mean that i don't appreciate the information being shared. in this case, the entire video should be redone, and i'm not trying to put her down so much as i'm saying to think critically about the things that you're taught, because they're not infallible.
to really demonstrate the benefits of having two queues, it is important to get the oldest and newest values. in a normal stack or queue, getting the highest priority ( newest for stack, oldest for queue) is an O(1) operation. getting the lowest priority (oldest for stack, newest for queue) is O(n). Having a double queue allows us to get highest and lowest priority in O(1), with added spatial complexity.
I agree. Not implementing a method to make use of the primary benefit of this specific data structure-also getting the lowest priority item in O(1)-makes this example much more confusing than it needs to be. If someone asked me to "implement X using two Ys", the first question I would ask is "why?". You know? What is it supposed to accomplish; why might we want to build it that way? Otherwise, in this example, why not use the in-built Queue data structure in Java?
@Bilbo What are you talking about? In first place, having 1 or 2 collections doesn’t change the space complexity, it is still O(n). In second place you can implement double ended queue with a single linked list. In third place, who is “demonstrating the benefits of having 2 queues”? This problem is about being faced with a constraint, not always you can choose the data structure to use, sometimes you gotta be creative and work with what’s available.
I think a good way to explain this is when the oldestOnTop stack becomes empty, we grab the newestOnTop stack, flip it upside down, and it becomes the new oldestOnTop stack.
Well Explained, Could you please explain that "what is the benefits of creating queue using two stack?"
The benefit is you pass the interview and get an offer.
@@alexnezhynsky9707 to really demonstrate the benefits of having two queues, it is important to get the oldest and newest values. in a normal stack or queue, getting the highest priority ( newest for stack, oldest for queue) is an O(1) operation. getting the lowest priority (oldest for stack, newest for queue) is O(n). Having a double queue allows us to get highest and lowest priority in O(1), with added spatial complexity.
Can also be done with only one stack, but the space complexity and time complexity will always be O(n)
You have several videos about data structures, better wrap them up as a playlist
It doesn't matter, just thank her. You are not paying her.
@@sonnix31 its in her best interest too 5head
Can someone tell me what is the meaning of when creating an object?
It's called a generic. Basically saying "this could contain any type of data". So this queue could contain int, strings, objects, etc. If she had defined it as
MyQueue {
private Stack stack1....
}
it would only be able to hold integers. Instead she uses type T so the consumer can determine what type it holds. In my code, to use this class, I would define it new MyQueue() or new MyQueue() or new MyQueue()
its generic, it can be ,,
Would runtimes of these operations be considered amortized O(1)? It seems like it is similar to an ArrayList where in most cases it is O(1) but occasionally everything must be copied over.
Enqueue is obv O(1) (or amortized O(1) if your stack uses a vector, which is the case in Java).
Dequeue must be amortized O(1) since the element to be dequeued will have been copied exactly once. This is assuming that the entire queue is emptied before deleting. Otherwise it can be as bad as O(n) -- that is, n copies, but only 1 dequeue operation.
However, if you logically amortize the copy operations as part of enqueue (the enqueued element will be copied once in the future), then you can still claim amortized O(1) for dequeue. Because of this, you can claim amortized O(1) for all operations.
How are you running these methods in your main class. What are the parameters being pushed?
Now if we have stack newest on top, I mean stack oldest on top
and now we want to peek, I mean dequeue
we don't have to move anything into the new array, I mean the new stack
Why would a company want to ask this question? It's obviously too confusing to coherently explain even if you've written books about it.
Your explanation is really good.
what is in that program
Generics, it means you could have MyQueue, MyQueue, MyQueue, etc
@@andritogv yep, good examples.
Awesome !! Can I know which Java compiler you are using?
SAHILRSJ SAH she compiled this code on the hackerrank platform.
"We need to pop everything off the top", well no, you can just call .shift() in any standard language, but interesting video to explain why this problem would even be conceived.
I thought peek shows the top element in the stack or the "newest" in your example?
And that is exactly what it is doing.
@@sonnix31 it says "oldest" item in her example
@@ssshah3333 Oldest item meaning it was the first item placed in the first stack, but then when the items are put in the second stack with Oldest on top, this item is at the top. The old item is at the top of the second stack after moving the items. Do not refer to the word, but the meaning. The command removes the item at top of second stack and this is the oldest item (first item placed in first stack). Hope this makes sense.
@@sonnix31 oh yeah I get it, thanks
Great Explanation thanks a lott!!!
i have understood the concept ...but iam getting lot of syntax errors while im trying to run it...can someone please provide the source code for this
nice
w....why would you not use a linked list for this. this is literally why a linked list exists. the time complexity of getting the first or last item from a linked list is O(0).
double checked that there was no sane reason for this and there could be some distributed cloud complexity but the option of a circular array where start and end indexes are stored and updated rather than THE ENTIRE ARRAY COPIED EVERY SINGLE TIME YOU TOUCH ANYTHING confirms the fact that despite having learned some fancy things from very smart people, even the people answering these questions are not very smart. she wrote a book on this. she wrote a book on this. she wrote a book on this. it took me three minutes, which is more time than it took any single person to read the incorrect information that she wrote.
and before you "oh, priorities and whatnot" then use separate priority queues, there, done, checking to see if they're empty every pull is faster than reordering the array
also just because i'm being critical doesn't mean that i don't appreciate the information being shared. in this case, the entire video should be redone, and i'm not trying to put her down so much as i'm saying to think critically about the things that you're taught, because they're not infallible.
cause this is the type of random shit they ask in interviews
Bro is mad 💀
You wont understand the logic until you put pen to paper and draw out everything as you go.
Good job sweetheart