@@asiandramas1477 package twostackqueue; import java.util.EmptyStackException; import java.util.List; import java.util.Stack; /** * @author LazyElectron * @since 03/25/2019 */ public class TwoStackQueues { /** * MyQueueI interface to be implemented. * @param is the element in the Queue */ interface MyQueueI { public E dequeue(); public void enqueue(E element); public boolean isEmpty(); public E peek(); } /** * A queue that is implemented using two stacks. * @param is the element in the Queue. */ public static class TwoStackQueue implements MyQueueI {
private Stack s1; private Stack s2; /** * Default Constructor */ public TwoStackQueue() { s1 = new Stack(); s2 = new Stack(); }
/** * Constructor which accepts a List as a parameter and builds a Queue with it. * @param L is the list from which we build the Queue. */ public TwoStackQueue(List L) { s1 = new Stack(); s2 = new Stack();
for (Object o : L) s1.push((E) o);
while (!s1.isEmpty()) s2.push(s1.pop()); }
/** * Method to remove an item from the queue. * @return item that has been removed. */ @Override public E dequeue(){ if (isEmpty()) throw new EmptyStackException();
if (s2.isEmpty()) while (!s1.isEmpty()) s2.push(s1.pop());
return s2.pop(); } /** * Method to add an item to the queue. * @param element is the element to be added. */ @Override public void enqueue(E element) { s1.push(element); } /** * Method which checks whether the queue is empty. * @return true if empty, false if not. */ @Override public boolean isEmpty() { return s1.isEmpty() && s2.isEmpty(); } /** * Method which checks and returns the front of the queue. * @return front element in the queue. */ @Override public E peek() { if (isEmpty()) throw new EmptyStackException();
if (s2.isEmpty()) while (!s1.isEmpty()) s2.push(s1.pop());
return s2.peek(); } /** * String representation of the TwoStackQueue * @return String representation of the TSQ */ @Override public String toString() { return "TwoStackQueue{" + "s1=" + s1 + ", s2=" + s2 + '}'; }
@@asiandramas1477 You're welcome. Sorry, but I can't help you with the C programming language . But you can simply search Two Stack Queue on Google and there will be a link to a website called Geeksforgeeks where they have the same thing written in C. Good luck !!
Very nice video beautiful explanation of problem and the solution, I hope you will make more videos on DS and Algo. many people struggle with these topics.
In dequeue you forgot an important step. Either you need to transfer everything back from s2 to s1 or you can have a separate variable that is always pointing to the stack that you intend to be your queue. like this Stack myQueue = s1 perform dequeue myQueue = s2 After that you will use s1 as the stack you will transfer to when performing a dequeue or front and then myQueue will be pointing towards s1
Why would one ever do this in real life? It seems to me this approach supports O(n) for dequeue....but a linked list or circular array could do dequeue in O(1) could it not?
Late answer but for anyone else wondering why you would use this approach. Reversing the contents of an array is in fact an O(n) operation but the overall dequeue cost is still amortized O(1). Imagine having a large number of items in both the let and right stack. IF you dequeue all the elements, first it will remove all of the elements from the left stack, then reverse copy the right stack only one, and then continue removing elements off the left stack. So there are a few benefits here. Compared to array-based implementation, we were able to transform dequeue into an amortized O(1) operation. Two stack implementation is fully dynamic and doesn't have the fixed size restriction the ring-buffer implementation does. Better then Linked List in terms of spacial locality. This is because array elements are next to each other in memory blocks. So a large number of elements will be loaded in a cache on first access. Linked list aren't in contiguous blocks of memory which could lead to more cache misses and increase access time.
Great explanation, you basically have an input and an output Stack!
That's kind of fun when you think of it that way!
Very well explained. Helped me a lot!
Quick and thorough explanation, also very good English!
thanks G. explained in 5 minutes very well
Quick and clear! Great explanation, thanks
The best video I came across , helped me a lot..
Thank you very much ! You helped me with my homework. I gave you a thumbs up !
Hey do u know the program for this algorithm? My sis wanted it. It would be great help if ull send me the program
@@asiandramas1477
package twostackqueue;
import java.util.EmptyStackException;
import java.util.List;
import java.util.Stack;
/**
* @author LazyElectron
* @since 03/25/2019
*/
public class TwoStackQueues {
/**
* MyQueueI interface to be implemented.
* @param is the element in the Queue
*/
interface MyQueueI {
public E dequeue();
public void enqueue(E element);
public boolean isEmpty();
public E peek();
}
/**
* A queue that is implemented using two stacks.
* @param is the element in the Queue.
*/
public static class TwoStackQueue implements MyQueueI {
private Stack s1;
private Stack s2;
/**
* Default Constructor
*/
public TwoStackQueue() {
s1 = new Stack();
s2 = new Stack();
}
/**
* Constructor which accepts a List as a parameter and builds a Queue with it.
* @param L is the list from which we build the Queue.
*/
public TwoStackQueue(List L) {
s1 = new Stack();
s2 = new Stack();
for (Object o : L)
s1.push((E) o);
while (!s1.isEmpty())
s2.push(s1.pop());
}
/**
* Method to remove an item from the queue.
* @return item that has been removed.
*/
@Override
public E dequeue(){
if (isEmpty())
throw new EmptyStackException();
if (s2.isEmpty())
while (!s1.isEmpty())
s2.push(s1.pop());
return s2.pop();
}
/**
* Method to add an item to the queue.
* @param element is the element to be added.
*/
@Override
public void enqueue(E element) {
s1.push(element);
}
/**
* Method which checks whether the queue is empty.
* @return true if empty, false if not.
*/
@Override
public boolean isEmpty() {
return s1.isEmpty() && s2.isEmpty();
}
/**
* Method which checks and returns the front of the queue.
* @return front element in the queue.
*/
@Override
public E peek() {
if (isEmpty())
throw new EmptyStackException();
if (s2.isEmpty())
while (!s1.isEmpty())
s2.push(s1.pop());
return s2.peek();
}
/**
* String representation of the TwoStackQueue
* @return String representation of the TSQ
*/
@Override
public String toString() {
return "TwoStackQueue{" + "s1=" + s1 + ", s2=" + s2 + '}';
}
}
}
Thank you so much. What if we want to implement it in c language ? Is it different?
@@asiandramas1477 You're welcome. Sorry, but I can't help you with the C programming language . But you can simply search Two Stack Queue on Google and there will be a link to a website called Geeksforgeeks where they have the same thing written in C.
Good luck !!
Thanks
Very clear!!! Thank you
Loved this, thanks.
Amazing explanation.
You're a life saver! Thanks!
Super sir😍😍😍thank you so much.. Love you 😍
Thanks dude! this helped a lot!
Fast and easy to u deter and explanation, thanks!
Well explained
Very nice video beautiful explanation of problem and the solution, I hope you will make more videos on DS and Algo. many people struggle with these topics.
thanks, it helps buddy!
Crystal Clear
In dequeue you forgot an important step. Either you need to transfer everything back from s2 to s1 or you can have a separate variable that is always pointing to the stack that you intend to be your queue. like this
Stack myQueue = s1
perform dequeue
myQueue = s2
After that you will use s1 as the stack you will transfer to when performing a dequeue or front and then myQueue will be pointing towards s1
Helpful
wouldnt the pop() on s2 give 'z' since pop() removes the last elemnt of the array but first element of the stack?
thank you
This is not correct. 5:17 if you call size() after pop(), you are supposed to get 3 {y,z,b} instead of 1 {b}.
Why would one ever do this in real life? It seems to me this approach supports O(n) for dequeue....but a linked list or circular array could do dequeue in O(1) could it not?
Late answer but for anyone else wondering why you would use this approach. Reversing the contents of an array is in fact an O(n) operation but the overall dequeue cost is still amortized O(1). Imagine having a large number of items in both the let and right stack. IF you dequeue all the elements, first it will remove all of the elements from the left stack, then reverse copy the right stack only one, and then continue removing elements off the left stack. So there are a few benefits here. Compared to array-based implementation, we were able to transform dequeue into an amortized O(1) operation. Two stack implementation is fully dynamic and doesn't have the fixed size restriction the ring-buffer implementation does. Better then Linked List in terms of spacial locality. This is because array elements are next to each other in memory blocks. So a large number of elements will be loaded in a cache on first access. Linked list aren't in contiguous blocks of memory which could lead to more cache misses and increase access time.
where do we apply this??
It's a common interview question.
Thanks
nice tutorial but voice is very low
That accent though.... BTW nice video thanks!