1
00:00:00,700 --> 00:00:01,660
Hi everyone.

2
00:00:01,660 --> 00:00:06,880
Welcome to this data structure Crash course where we're dealing with stacks and queues.

3
00:00:06,910 --> 00:00:10,720
Now in this video, these are the two things that we will focus upon.

4
00:00:10,720 --> 00:00:13,240
We will try to understand stacks and queues.

5
00:00:13,240 --> 00:00:18,340
And then we will look at Big-O analysis of common operations for stacks and queues.

6
00:00:18,340 --> 00:00:22,930
So let's get started and try to understand what stacks and queues are about.

7
00:00:22,960 --> 00:00:31,240
Now when it comes to stacks, these are just LFO data structures and LFO stands for last in first out.

8
00:00:31,240 --> 00:00:33,700
Now let's take an example to understand this.

9
00:00:33,700 --> 00:00:34,810
This is a table.

10
00:00:34,810 --> 00:00:37,720
And let's say we have a few books on this table.

11
00:00:37,750 --> 00:00:44,500
Now if you want to take a book out and if we can't just pull one book out from in between, then this

12
00:00:44,500 --> 00:00:46,750
would be the book that we would take out first.

13
00:00:46,750 --> 00:00:47,140
Right?

14
00:00:47,140 --> 00:00:51,610
And remember, when we place the books, this is the book that we place first.

15
00:00:51,610 --> 00:00:53,200
This is the one we place second.

16
00:00:53,200 --> 00:00:57,100
And this book over here is the book that we place last, right or third.

17
00:00:57,100 --> 00:00:59,470
Now when we take out we are taking this first.

18
00:00:59,470 --> 00:01:03,910
So that means the element which was entered last is coming out first.

19
00:01:03,910 --> 00:01:09,370
Now if we were to add another book to this stack, it would be added over here which is at the top.

20
00:01:09,370 --> 00:01:09,850
All right.

21
00:01:09,850 --> 00:01:13,090
Again when we remove this would be the first one which we can remove.

22
00:01:13,090 --> 00:01:19,330
So this type of a data structure where the element which was added last is taken out first is called

23
00:01:19,330 --> 00:01:19,990
a stack.

24
00:01:19,990 --> 00:01:23,590
Now when it comes to a queue it's a little bit different.

25
00:01:23,590 --> 00:01:26,620
A queue is a Fifo data structure.

26
00:01:26,980 --> 00:01:30,490
Now Fifo stands for first in first out.

27
00:01:30,970 --> 00:01:33,040
Now let's take an example to understand this.

28
00:01:33,040 --> 00:01:35,020
So this over here is a counter.

29
00:01:35,020 --> 00:01:37,210
And let's say we are selling tickets over here.

30
00:01:37,210 --> 00:01:40,360
And people are standing in a queue to buy a ticket.

31
00:01:40,360 --> 00:01:46,330
Now the first person who would get the ticket and would come out of the queue is this person over here,

32
00:01:46,330 --> 00:01:49,660
and this is the person who entered the queue first, right?

33
00:01:49,660 --> 00:01:52,240
So this is how a normal queue works in real life.

34
00:01:52,240 --> 00:01:58,090
And if a new person wants to join this queue, he would have to join over here, which is at the end.

35
00:01:58,090 --> 00:01:59,830
So this is how a queue works.

36
00:01:59,830 --> 00:02:06,310
So a queue in short is a Fifo data structure and a stack is a data structure.

37
00:02:07,520 --> 00:02:13,220
Let's now take a look at how stacks and queues are implemented now in JavaScript.

38
00:02:13,220 --> 00:02:17,060
Stacks under the hood are implemented as dynamic arrays.

39
00:02:17,060 --> 00:02:22,670
And this is a good news because the major operation that we would be doing in stacks is adding to a

40
00:02:22,670 --> 00:02:27,020
stack and removing from a stack, and it follows the last in first out property.

41
00:02:27,020 --> 00:02:32,570
Now for this push and pop is going to be a constant time and constant space operation.

42
00:02:32,570 --> 00:02:36,560
And when it comes to pushing to an array which is adding at the end, right.

43
00:02:36,560 --> 00:02:41,900
So that is amortized constant time operation because it's implemented as a dynamic array.

44
00:02:41,900 --> 00:02:46,580
And we have seen this previously in the case of a dynamic array, adding at the end or pushing to an

45
00:02:46,580 --> 00:02:49,430
array is amortized constant time operation.

46
00:02:49,430 --> 00:02:54,890
Now, when it comes to a queue, a queue is typically implemented as a linked list.

47
00:02:54,890 --> 00:02:55,400
All right.

48
00:02:55,400 --> 00:03:00,500
So this is done so that we can get constant time adding and removing from the queue.

49
00:03:00,500 --> 00:03:06,050
Now in some questions you will see that a queue is implemented as an array in JavaScript.

50
00:03:06,050 --> 00:03:09,770
This is because we want to save time in some algorithm questions.

51
00:03:09,770 --> 00:03:12,800
And there is no inbuilt queue in JavaScript.

52
00:03:12,800 --> 00:03:17,780
Now this is not optimal because you know that if you are using an array and again we have seen that

53
00:03:17,780 --> 00:03:19,340
we want to remove from the beginning.

54
00:03:19,340 --> 00:03:20,780
So let's say this is our array.

55
00:03:21,850 --> 00:03:23,290
And this is the end.

56
00:03:23,320 --> 00:03:25,960
So when we add we will be pushing right.

57
00:03:25,960 --> 00:03:28,060
So this is going to be pushing to the array.

58
00:03:28,060 --> 00:03:32,890
And when we remove we want to remove the item which was first entered, which is this element over here

59
00:03:32,890 --> 00:03:33,430
in the array.

60
00:03:33,430 --> 00:03:39,040
And we know that removing the first element in the array is an o of n operation time, right.

61
00:03:39,430 --> 00:03:44,680
The time complexity is going to be o of n because the remaining elements have to be re-indexed so that

62
00:03:44,680 --> 00:03:48,430
is why with respect to time complexity, this is not a good practice.

63
00:03:48,430 --> 00:03:54,490
But if you're doing a question in the interview which requires a queue, and if that is not the central

64
00:03:54,490 --> 00:03:59,740
part of the question, then you can always tell the interviewer that typically you would have to implement

65
00:03:59,740 --> 00:04:04,990
a queue as a linked list to get optimum performance, but then because you're not having time, you're

66
00:04:04,990 --> 00:04:10,150
just implementing the queue as an array, and he or she the interviewer would mostly be okay with that.

67
00:04:10,150 --> 00:04:15,010
Now, when we are implementing a queue as a linked list, we will be tracking the head and the tail,

68
00:04:15,010 --> 00:04:21,370
and this will enable us to insert to the queue and to remove from the queue in constant time and constant

69
00:04:21,370 --> 00:04:21,820
space.

70
00:04:21,820 --> 00:04:24,280
So we have seen that when we discussed a linked list, right?

71
00:04:24,280 --> 00:04:29,890
Adding at the beginning and removing from the end for a linked list is going to be a constant time operation

72
00:04:29,890 --> 00:04:31,840
and a constant space operation.

73
00:04:32,170 --> 00:04:36,910
Let me also quickly mention that we can implement a stack also as a linked list.

74
00:04:36,910 --> 00:04:42,610
But then even when we are just using an array, we are getting constant time and constant space adding

75
00:04:42,610 --> 00:04:44,020
and removing from the stack.

76
00:04:44,020 --> 00:04:46,540
But that's not the case when we are looking at a queue.

77
00:04:46,570 --> 00:04:52,300
If you're using an array, then in that case, removing from the queue or dequeuing from the queue is

78
00:04:52,300 --> 00:04:53,680
an O of n operation.

79
00:04:53,680 --> 00:04:59,020
Now again, remember in the case of a queue, inserting to the queue is called n queuing and removing

80
00:04:59,020 --> 00:05:00,940
from the queue is called d queuing.

81
00:05:00,940 --> 00:05:01,420
All right.

82
00:05:01,450 --> 00:05:07,060
Now let's go ahead and take a look at the Big-O analysis of common operations for stacks and queues.

83
00:05:07,060 --> 00:05:10,870
Now inserting into a stack is an O of one operation right?

84
00:05:10,870 --> 00:05:12,760
Or a constant time and space operation.

85
00:05:12,760 --> 00:05:16,720
And removing from a stack is also a constant time and space operation.

86
00:05:16,720 --> 00:05:19,000
And it's called pushing and popping from the stack.

87
00:05:19,000 --> 00:05:22,720
Now, these are the most important operations for a stack, and a queue.

88
00:05:22,720 --> 00:05:28,570
And then as we are implementing the queue as a linked list, even in that case inserting or removing

89
00:05:28,570 --> 00:05:30,400
from the queue, which is called n queuing.

90
00:05:30,400 --> 00:05:33,790
And d queuing is a constant time and space operation.

91
00:05:33,790 --> 00:05:39,670
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

92
00:05:39,670 --> 00:05:45,130
operation and even peeking at an element, peeking at the element which will be removed, right?

93
00:05:45,130 --> 00:05:46,510
Which will be removed next?

94
00:05:47,420 --> 00:05:51,950
Is a constant time operation for a stack and a constant time operation for a queue.

95
00:05:51,980 --> 00:05:56,420
Now this is very much similar to popping or removing from the queue.

96
00:05:56,450 --> 00:06:00,500
The only difference is that we are not actually removing the element, we are just taking a look at

97
00:06:00,500 --> 00:06:06,380
that element which would come out if we were to pop or dequeue from the queue, whichever is the respective

98
00:06:06,380 --> 00:06:06,920
case.