1
00:00:00,460 --> 00:00:04,030
‫So now we're going to do our introduction to stacks.

2
00:00:04,300 --> 00:00:10,090
‫And my favorite analogy for a stack is that it's like a can of tennis balls.

3
00:00:10,390 --> 00:00:14,980
‫So let's take the balls out and put these in one at a time.

4
00:00:15,310 --> 00:00:20,710
‫When we add something to a stack, we say that we push it onto the stack.

5
00:00:21,070 --> 00:00:27,820
‫And when we push another item onto the stack, we can no longer get to the first item, that bottom

6
00:00:27,820 --> 00:00:32,020
‫item, until we remove the item that is above it.

7
00:00:32,230 --> 00:00:38,200
‫And we can't get to this second item if we push another item onto the stack.

8
00:00:38,620 --> 00:00:45,520
‫So if we're going to remove an item from a stack, the only one we can remove is the top item.

9
00:00:45,880 --> 00:00:50,980
‫This is called LFO, which is last in, first out.

10
00:00:51,400 --> 00:00:59,080
‫And when we remove that item, the terminology is that we pop that item from the stack and it's only

11
00:00:59,080 --> 00:01:04,570
‫by popping that top item from the stack that we can get to the next item and then we can pop that item

12
00:01:04,570 --> 00:01:08,110
‫from the stack and then pop that last item.

13
00:01:08,620 --> 00:01:13,000
‫So now let's look at an example of where we use stacks.

14
00:01:13,570 --> 00:01:17,830
‫We'll bring up a web browser and let's say we're going to go to Facebook.

15
00:01:18,070 --> 00:01:24,370
‫But after you get done looking at Facebook, you go to YouTube and then you go to Instagram and then

16
00:01:24,370 --> 00:01:25,870
‫you check your email.

17
00:01:26,020 --> 00:01:32,860
‫Well, those items on the right, those previously visited Web pages, that is a stack.

18
00:01:33,070 --> 00:01:38,620
‫And when you hit the back button, it pops that top item from the stack.

19
00:01:38,980 --> 00:01:45,160
‫And that if we hit the back button again, it will pop the next item from the stack and so on.

20
00:01:45,610 --> 00:01:49,960
‫So I'm going to go over a couple of common ways to implement a stack.

21
00:01:50,290 --> 00:01:55,870
‫First, we're going to look at a vector, and this is probably the most common way to do this.

22
00:01:56,200 --> 00:02:02,020
‫And in order for this to be a stack, you just need to add and remove from the same end.

23
00:02:02,560 --> 00:02:08,740
‫So if you add, this would be pushing onto the stack or remove from this end.

24
00:02:08,980 --> 00:02:12,460
‫Adding and removing are both of one.

25
00:02:12,850 --> 00:02:19,990
‫But if you implemented your stack where we're going to remove items from this end, remember when we

26
00:02:19,990 --> 00:02:28,480
‫do that, we have to re index all of these items and then if you want to bring it back, you have to

27
00:02:28,480 --> 00:02:32,980
‫do all of the re indexing again to bring this item back.

28
00:02:33,310 --> 00:02:39,760
‫So it doesn't matter if you're adding or removing or we would say pushing or popping from the stack.

29
00:02:40,120 --> 00:02:43,870
‫If you do it on this end, it's O of RN.

30
00:02:44,230 --> 00:02:49,690
‫So if you're going to implement a stack with a vector, you always want to have it be on the other end

31
00:02:49,690 --> 00:02:51,370
‫where it's o of one.

32
00:02:51,730 --> 00:02:59,080
‫And of course when you visualize this, this would be something more like this where we would pop from

33
00:02:59,080 --> 00:03:01,510
‫or push to the stack.

34
00:03:02,120 --> 00:03:08,660
‫So let's put this back and look at the other data structure that you can use for a stack, and that

35
00:03:09,110 --> 00:03:10,490
‫is a linked list.

36
00:03:10,760 --> 00:03:15,530
‫And a link list is what we're going to use to implement a stack in this course.

37
00:03:15,830 --> 00:03:22,040
‫And just as I mentioned with vectors, in order for this to be a stack, you just have to add and remove

38
00:03:22,040 --> 00:03:23,510
‫from the same end.

39
00:03:23,900 --> 00:03:27,140
‫Except our stack would look something like this.

40
00:03:27,410 --> 00:03:33,170
‫And if you're using a linked list for a stack, you always want the null pointer end to be at the bottom.

41
00:03:33,170 --> 00:03:35,960
‫You don't want the stack to look like this.

42
00:03:36,260 --> 00:03:43,190
‫So let's put this back as a linked list and look at the big O of adding and removing from each end.

43
00:03:43,610 --> 00:03:52,100
‫So if we do it from this end, removing a node is o of n and adding a node is of one, whereas on the

44
00:03:52,100 --> 00:03:58,100
‫other end it's o of one to remove a node and of one to add a node.

45
00:03:58,370 --> 00:04:00,800
‫So this is going to be more efficient.

46
00:04:01,130 --> 00:04:06,620
‫So that's why you always want to do a stack with a null pointer end pointing down.

47
00:04:07,270 --> 00:04:09,460
‫So let's put this back like this.

48
00:04:09,820 --> 00:04:16,210
‫In the Linked List section, we wrote a function for removing the first node, which was called Remove

49
00:04:16,210 --> 00:04:22,690
‫First, and we wrote a function for adding a node to the beginning, which was called Pretend.

50
00:04:23,080 --> 00:04:29,950
‫So we can use those functions as a starting point for writing functions for pop.

51
00:04:30,520 --> 00:04:31,600
‫And push.

52
00:04:32,060 --> 00:04:36,290
‫And also when we created linked lists, we had head and tail.

53
00:04:36,710 --> 00:04:41,480
‫Since this is a stack, we'll rename these as top and bottom.

54
00:04:41,750 --> 00:04:48,050
‫But because we're only adding and removing at the top, we don't even need a bottom.

55
00:04:48,050 --> 00:04:51,920
‫So we can remove that and we just have top.

56
00:04:52,370 --> 00:04:55,580
‫And that is our quick introduction.

57
00:04:56,610 --> 00:04:57,780
‫To Stax.