Hi everyone.
Welcome to this data structure Crash course where we're dealing with stacks and queues.
Now in this video, these are the two things that we will focus upon.
We will try to understand stacks and queues.
And then we will look at Big-O analysis of common operations for stacks and queues.
So let's get started and try to understand what stacks and queues are about.
Now when it comes to stacks, these are just LFO data structures and LFO stands for last in first out.
Now let's take an example to understand this.
This is a table.
And let's say we have a few books on this table.
Now if you want to take a book out and if we can't just pull one book out from in between, then this
would be the book that we would take out first.
Right?
And remember, when we place the books, this is the book that we place first.
This is the one we place second.
And this book over here is the book that we place last, right or third.
Now when we take out we are taking this first.
So that means the element which was entered last is coming out first.
Now if we were to add another book to this stack, it would be added over here which is at the top.
All right.
Again when we remove this would be the first one which we can remove.
So this type of a data structure where the element which was added last is taken out first is called
a stack.
Now when it comes to a queue it's a little bit different.
A queue is a Fifo data structure.
Now Fifo stands for first in first out.
Now let's take an example to understand this.
So this over here is a counter.
And let's say we are selling tickets over here.
And people are standing in a queue to buy a ticket.
Now the first person who would get the ticket and would come out of the queue is this person over here,
and this is the person who entered the queue first, right?
So this is how a normal queue works in real life.
And if a new person wants to join this queue, he would have to join over here, which is at the end.
So this is how a queue works.
So a queue in short is a Fifo data structure and a stack is a data structure.
Let's now take a look at how stacks and queues are implemented now in JavaScript.
Stacks under the hood are implemented as dynamic arrays.
And this is a good news because the major operation that we would be doing in stacks is adding to a
stack and removing from a stack, and it follows the last in first out property.
Now for this push and pop is going to be a constant time and constant space operation.
And when it comes to pushing to an array which is adding at the end, right.
So that is amortized constant time operation because it's implemented as a dynamic array.
And we have seen this previously in the case of a dynamic array, adding at the end or pushing to an
array is amortized constant time operation.
Now, when it comes to a queue, a queue is typically implemented as a linked list.
All right.
So this is done so that we can get constant time adding and removing from the queue.
Now in some questions you will see that a queue is implemented as an array in JavaScript.
This is because we want to save time in some algorithm questions.
And there is no inbuilt queue in JavaScript.
Now this is not optimal because you know that if you are using an array and again we have seen that
we want to remove from the beginning.
So let's say this is our array.
And this is the end.
So when we add we will be pushing right.
So this is going to be pushing to the array.
And when we remove we want to remove the item which was first entered, which is this element over here
in the array.
And we know that removing the first element in the array is an o of n operation time, right.
The time complexity is going to be o of n because the remaining elements have to be re-indexed so that
is why with respect to time complexity, this is not a good practice.
But if you're doing a question in the interview which requires a queue, and if that is not the central
part of the question, then you can always tell the interviewer that typically you would have to implement
a queue as a linked list to get optimum performance, but then because you're not having time, you're
just implementing the queue as an array, and he or she the interviewer would mostly be okay with that.
Now, when we are implementing a queue as a linked list, we will be tracking the head and the tail,
and this will enable us to insert to the queue and to remove from the queue in constant time and constant
space.
So we have seen that when we discussed a linked list, right?
Adding at the beginning and removing from the end for a linked list is going to be a constant time operation
and a constant space operation.
Let me also quickly mention that we can implement a stack also as a linked list.
But then even when we are just using an array, we are getting constant time and constant space adding
and removing from the stack.
But that's not the case when we are looking at a queue.
If you're using an array, then in that case, removing from the queue or dequeuing from the queue is
an O of n operation.
Now again, remember in the case of a queue, inserting to the queue is called n queuing and removing
from the queue is called d queuing.
All right.
Now let's go ahead and take a look at the Big-O analysis of common operations for stacks and queues.
Now inserting into a stack is an O of one operation right?
Or a constant time and space operation.
And removing from a stack is also a constant time and space operation.
And it's called pushing and popping from the stack.
Now, these are the most important operations for a stack, and a queue.
And then as we are implementing the queue as a linked list, even in that case inserting or removing
from the queue, which is called n queuing.
And d queuing is a constant time and space operation.
Now, if you want to traverse or search for an element in a stack or a queue, it's an O of N time complexity
operation and even peeking at an element, peeking at the element which will be removed, right?
Which will be removed next?
Is a constant time operation for a stack and a constant time operation for a queue.
Now this is very much similar to popping or removing from the queue.
The only difference is that we are not actually removing the element, we are just taking a look at
that element which would come out if we were to pop or dequeue from the queue, whichever is the respective
case.