1
00:00:06,240 --> 00:00:07,260
Hey buddy How's it going.

2
00:00:07,260 --> 00:00:09,230
This is Caleb with Deb's slopes dot com.

3
00:00:09,240 --> 00:00:13,260
And in this video we're going to talk about the data structure called the stack.

4
00:00:13,260 --> 00:00:17,170
And we're going to learn how to build one in swift which is very cool.

5
00:00:17,190 --> 00:00:19,290
So let's go ahead and let's pull up an X code.

6
00:00:19,290 --> 00:00:19,680
Click.

7
00:00:19,680 --> 00:00:25,410
Get started with a playground and I'm going to go ahead and just do a blank playground and I'm going

8
00:00:25,410 --> 00:00:28,490
to name this my stack.

9
00:00:28,650 --> 00:00:33,840
Ok save it wherever I just said to the desktop and I'll make that full screen.

10
00:00:34,060 --> 00:00:39,370
And we're going to go ahead and just actually delete all of this boilerplate code and then import Foundation.

11
00:00:39,450 --> 00:00:43,900
We don't necessarily need you like it but Foundation is good enough.

12
00:00:44,280 --> 00:00:52,320
And now what we're going to do is we're going to go ahead and create a struct called Stack.

13
00:00:52,350 --> 00:00:53,270
All right.

14
00:00:53,490 --> 00:00:59,290
And we're going to go ahead and talk about first what is a stack and how does it work.

15
00:00:59,550 --> 00:01:06,500
So a stack is a data structure that is exactly what it sounds like it's a stack of pieces of data.

16
00:01:06,510 --> 00:01:15,690
And if you think about books or I don't know cubes or some type of thing that can stack if you put one

17
00:01:16,260 --> 00:01:21,780
on the table then put another thing on top of it and on top of it on top of it you get a stack.

18
00:01:21,780 --> 00:01:28,350
And the way that a stack works is the last object you put onto the stack is the first one you can remove

19
00:01:28,350 --> 00:01:29,390
easily right.

20
00:01:29,400 --> 00:01:33,630
You wouldn't want to pull out the item from the bottom because then the rest of the stack would collapse.

21
00:01:33,630 --> 00:01:35,390
So in a stack it works the same way.

22
00:01:35,400 --> 00:01:41,590
And this is called leaf so kind and that stands for last in first out.

23
00:01:41,760 --> 00:01:47,130
Kate that's what this data structure is it's last in first out the last item you add is the first one

24
00:01:47,130 --> 00:01:48,080
you can remove.

25
00:01:48,330 --> 00:01:54,090
So we're going to go ahead and add a private variable called array.

26
00:01:54,090 --> 00:01:54,790
All right.

27
00:01:54,870 --> 00:02:01,530
And it's going to be well we should declare it as an array of type String OK because our types are going

28
00:02:01,530 --> 00:02:06,540
to be a stack of strings and so you know what let's actually call this a string stack for an Now just

29
00:02:06,660 --> 00:02:08,380
so that we're 100 percent clear.

30
00:02:09,000 --> 00:02:15,340
And I'm going to go ahead and just initialize this from the get go with just an empty array.

31
00:02:15,480 --> 00:02:19,200
OK nothing there but it's of type string and that's the type it accepts.

32
00:02:19,200 --> 00:02:25,500
Now we're going to use an array because an array has a very nice linear structure and we can add items

33
00:02:25,500 --> 00:02:28,410
to this array just like we would add things to a stack.

34
00:02:28,440 --> 00:02:34,220
So let's go ahead and let's dive into the three methods that are a part of a stack.

35
00:02:34,320 --> 00:02:40,230
We have peek which allows us to look at the top item of the stack but not do anything with it we're

36
00:02:40,230 --> 00:02:47,380
just going to return a value we have pop which is going to remove and return the top item of the stack.

37
00:02:47,520 --> 00:02:52,170
And we also have push which allows us to add a new element on top of the stack.

38
00:02:52,320 --> 00:02:56,080
So let's go ahead let's write those functions phunk peak.

39
00:02:56,840 --> 00:02:57,280
OK.

40
00:02:57,330 --> 00:03:00,680
And below that we have phunk pop.

41
00:03:01,260 --> 00:03:06,060
And then below that we're going to do phunk push and this is where we're going to add an element.

42
00:03:06,090 --> 00:03:12,870
And so I'm going to go ahead and just pass in an element of type string right because our array is of

43
00:03:12,870 --> 00:03:14,490
type string.

44
00:03:14,490 --> 00:03:17,390
So we have three functions here Peke.

45
00:03:17,400 --> 00:03:21,170
Like I said allows us to peek at the top element of our stack.

46
00:03:21,180 --> 00:03:23,050
And so that's going to return.

47
00:03:23,310 --> 00:03:26,620
Well what type is our array string.

48
00:03:26,670 --> 00:03:30,270
So we have a peak function that will return a string.

49
00:03:30,330 --> 00:03:35,760
We have a pop function that will remove the top item and return it so we know what it was.

50
00:03:35,760 --> 00:03:37,980
So we're going to return a string here as well.

51
00:03:38,220 --> 00:03:42,780
So let's go ahead and let's actually begin with our push function because we're going to need to do

52
00:03:42,780 --> 00:03:46,620
that first in order to actually add an item to our stack.

53
00:03:46,680 --> 00:03:52,260
And so in order to add an element we're going to go ahead and call our array and instead of appending

54
00:03:52,280 --> 00:03:54,580
of value because that would add it to the end.

55
00:03:54,600 --> 00:03:57,740
I want to make sure that it's always being added to the top.

56
00:03:57,750 --> 00:04:01,580
I'm going to call DOT insert new element at index.

57
00:04:01,700 --> 00:04:02,410
OK.

58
00:04:02,670 --> 00:04:09,150
So the new element is the element that we're passing in OK and we're going to add it at the index 0

59
00:04:09,180 --> 00:04:14,400
so that whenever we add a new one it's at the index 0 and everything else gets pushed down.

60
00:04:14,610 --> 00:04:16,890
Or I guess not pushed down because we're building on top of it.

61
00:04:16,890 --> 00:04:19,850
So that is what we're going to do in order to insert a value.

62
00:04:19,860 --> 00:04:25,450
But you're noticing can not use mutating member on immutable value.

63
00:04:25,670 --> 00:04:26,360
OK.

64
00:04:26,430 --> 00:04:33,300
At the current moment this struct is immutable meaning that we need to make our function mutating or

65
00:04:33,480 --> 00:04:35,490
allowing it to modify this value.

66
00:04:35,490 --> 00:04:42,480
So go ahead and type mutating at the beginning and that will allow this function to actually modify

67
00:04:42,480 --> 00:04:43,880
our array variable.

68
00:04:44,220 --> 00:04:49,350
Now of course these are throwing errors because it's expecting a return which we have not yet done but

69
00:04:49,350 --> 00:04:51,010
now we can call push.

70
00:04:51,030 --> 00:04:53,960
And that allows us to add an element to our right.

71
00:04:54,090 --> 00:05:03,180
So peak is going to show us the top item and return it and we need to think though a stack it might

72
00:05:03,180 --> 00:05:05,250
not have a top Ellen.

73
00:05:05,320 --> 00:05:06,270
Right from the get go.

74
00:05:06,280 --> 00:05:12,160
So we're going to go ahead and use guard lat so that we can be safe guard let's And let's call this

75
00:05:12,310 --> 00:05:22,550
top element and we're going to say that that will be Auray dot first right now if you saw that I don't

76
00:05:22,550 --> 00:05:30,550
know if you saw that there first is optional because there's not always an element at the first index.

77
00:05:30,550 --> 00:05:36,160
So we're going to go ahead and say else and if there is a problem ok.

78
00:05:36,250 --> 00:05:42,760
If there is a problem meaning if a write up first is nil we're going to go ahead and call fatal error

79
00:05:42,850 --> 00:05:49,680
with a message and just say the stack is empty and we'll see how that works in just a second.

80
00:05:49,870 --> 00:05:57,040
Then assuming that we do have a value we're going to go ahead and return return top element.

81
00:05:57,040 --> 00:06:00,700
Now if we don't have a value there obviously is a better way to do this.

82
00:06:00,700 --> 00:06:06,940
We could you know call some notification that would present an error saying hey that's not going to

83
00:06:06,940 --> 00:06:07,560
work.

84
00:06:07,870 --> 00:06:14,620
But for now we're just going to call fatal error and return that element if it exists pop is even easier

85
00:06:14,620 --> 00:06:21,850
because we're going to go ahead and just return Flip's return array and we can call a function called

86
00:06:21,940 --> 00:06:28,710
remove first and check out what this does it removes and returns the first element of the collection.

87
00:06:28,930 --> 00:06:30,040
That's exactly what we want to do.

88
00:06:30,040 --> 00:06:36,040
So it's almost sort of built into an array remove first is very similar to the pop function in a stack.

89
00:06:36,040 --> 00:06:43,420
So similarly to our push function pop is also mutating our array so we need to tell the function that

90
00:06:43,420 --> 00:06:45,130
it's allowed to do so.

91
00:06:45,640 --> 00:06:49,230
And with that our stack is now finished.

92
00:06:49,240 --> 00:06:52,510
Now what we're going to do is we're going to go ahead and play around with this so I'm going to create

93
00:06:52,510 --> 00:06:55,610
an instance of my stack by typing var.

94
00:06:55,870 --> 00:06:57,670
Let's make it a stack for names.

95
00:06:57,670 --> 00:07:04,750
I'm going to send in names so names stack equals string stack like so.

96
00:07:04,870 --> 00:07:08,030
And put some Princie is here to initialize it.

97
00:07:08,110 --> 00:07:13,650
We now have a stack available to us and we can call name dot wups names stack.

98
00:07:13,690 --> 00:07:16,360
Sorry dot peak pop or push.

99
00:07:16,360 --> 00:07:19,700
Now if I call names stacked peak we get an error.

100
00:07:19,870 --> 00:07:24,730
It's going to crash and we get our little error message we passed in the stack is empty.

101
00:07:24,760 --> 00:07:25,360
So that's good.

102
00:07:25,360 --> 00:07:26,320
It works.

103
00:07:26,350 --> 00:07:28,620
We can call pop.

104
00:07:28,870 --> 00:07:35,690
OK just like that and what it's going to do is it's going to say that it can't remove the first element

105
00:07:35,690 --> 00:07:39,010
from an empty collection because we have not yet added anything.

106
00:07:39,020 --> 00:07:44,910
So let's go ahead and let's call push and let's pass in the name pass in my name.

107
00:07:45,350 --> 00:07:48,730
OK let's let's go ahead and.

108
00:07:48,920 --> 00:07:54,230
Well now we can call names stack dot pop and we can remove that.

109
00:07:54,280 --> 00:07:58,700
It will go ahead and print out the element remember because it returns it and then it removes it.

110
00:07:58,700 --> 00:08:04,520
Now if I go ahead and type name stack dot may be peek.

111
00:08:04,660 --> 00:08:05,270
OK.

112
00:08:05,480 --> 00:08:08,490
We should get an error saying hey the stack is empty because it's empty again.

113
00:08:08,510 --> 00:08:09,600
We removed it.

114
00:08:09,600 --> 00:08:10,850
See that's how it works.

115
00:08:10,850 --> 00:08:15,520
So very cool let's get rid of those too and let's push in some more names here.

116
00:08:15,650 --> 00:08:24,300
Push let's add in Mark's name names stack names stack push and I'll add in Jacob.

117
00:08:24,680 --> 00:08:30,530
And now we have three elements in our stack but we don't have a really good way of visualizing it.

118
00:08:30,560 --> 00:08:38,740
And if I print it out like so we don't really get a very easy to look at understanding of what's happening.

119
00:08:38,870 --> 00:08:43,490
Now I'll show you in a second we're going to actually write an extension of custom string convertible

120
00:08:43,490 --> 00:08:46,780
that will print out a very nice visual representation of our stack.

121
00:08:46,940 --> 00:08:50,680
But for now we can see that the first one I added is now at the bottom.

122
00:08:50,690 --> 00:08:54,590
Then I added Mark that's in the second index or I guess the first index.

123
00:08:54,590 --> 00:08:57,530
Then Jacob is at the zero index or the top.

124
00:08:57,530 --> 00:09:00,350
So that's very cool it's working which is awesome.

125
00:09:00,590 --> 00:09:06,020
So what I'm going to do is I'm going to go ahead and create an extension of string stack and it's going

126
00:09:06,020 --> 00:09:09,770
to be conforming to the custom string convertible protocol.

127
00:09:09,800 --> 00:09:14,180
So what we're going to do is we're actually going to modify the description property so that when we

128
00:09:14,180 --> 00:09:18,490
print out our name stack we get something a little bit different that's easier to visualize.

129
00:09:18,740 --> 00:09:24,590
So I'm going to go ahead and create a description here of type string and I'm going to use some curly

130
00:09:24,590 --> 00:09:29,210
brackets so we can go inside and modify what this description will be composed of.

131
00:09:29,210 --> 00:09:34,800
So we're going to create some dividers that will show like almost like our stack is in a box.

132
00:09:34,880 --> 00:09:43,530
So let's create a top divider top divider and that's going to be equal to this one two three.

133
00:09:43,610 --> 00:09:46,140
And then stack one to three.

134
00:09:46,880 --> 00:09:54,420
And then the bottom divider is going to be equal to just a bunch of dashes.

135
00:09:54,420 --> 00:09:55,010
One two three.

136
00:09:55,010 --> 00:09:58,830
And then there's five characters in stacks so one two three four five one two three.

137
00:09:59,000 --> 00:10:00,520
They're the same length now.

138
00:10:00,830 --> 00:10:07,520
So what we need to do next is we need to access the array that is inside of our stack and then we need

139
00:10:07,520 --> 00:10:11,050
to basically join them together with a separator.

140
00:10:11,060 --> 00:10:16,400
But we're just going to actually use the new line separator like so.

141
00:10:16,400 --> 00:10:18,040
So I should actually put this right here.

142
00:10:18,040 --> 00:10:19,190
I have a new line.

143
00:10:19,310 --> 00:10:24,950
And then for this one I'm going to do a new line here and a new line here so that their separation from

144
00:10:25,010 --> 00:10:26,180
everything.

145
00:10:26,180 --> 00:10:33,960
So let's go ahead and let's create the actual stack elements by typing let stack elements equals array

146
00:10:34,370 --> 00:10:37,760
joined and you can see you can put in a separator there.

147
00:10:37,760 --> 00:10:43,700
I'm going to go ahead and just put in that the new line syntax as a separate or so that each element

148
00:10:43,940 --> 00:10:47,170
will be on its own line simulating a stack.

149
00:10:47,180 --> 00:10:48,440
Pretty cool.

150
00:10:48,440 --> 00:10:50,710
Next we're going to go ahead and return.

151
00:10:51,050 --> 00:10:58,220
Return top divider Plus the stack elements plus the bottom divider and check it out.

152
00:10:58,310 --> 00:11:01,560
When we actually print Oops that should be a plus sign.

153
00:11:01,850 --> 00:11:09,350
When we print this out now you'll see that our stack is much much easier to look at which it's running.

154
00:11:09,350 --> 00:11:11,080
And there we go look at that.

155
00:11:11,150 --> 00:11:13,950
We've got a stack that's pretty cool.

156
00:11:14,000 --> 00:11:15,190
It's running again.

157
00:11:15,320 --> 00:11:17,870
Looks like it's stopped.

158
00:11:17,900 --> 00:11:18,290
There we go.

159
00:11:18,320 --> 00:11:19,240
So there's our stack.

160
00:11:19,240 --> 00:11:21,350
It's easy to visualize Jacobs on the top.

161
00:11:21,440 --> 00:11:23,390
Mark is in the middle and I'm at the bottom.

162
00:11:23,540 --> 00:11:32,450
Now if I were to go ahead and type name stack dot Let's go ahead and let's pop an element off then print

163
00:11:32,450 --> 00:11:33,800
out name stack.

164
00:11:33,800 --> 00:11:35,960
You'll see we get a different result.

165
00:11:36,050 --> 00:11:37,640
Now Mark and Caleb are here.

166
00:11:37,640 --> 00:11:38,840
Mark is now at the top against.

167
00:11:38,840 --> 00:11:41,220
We pulled Jacob off the top.

168
00:11:41,300 --> 00:11:42,110
What else can I do.

169
00:11:42,110 --> 00:11:46,660
I can well you know what let's go ahead and let's actually peek.

170
00:11:46,790 --> 00:11:52,550
Stack peak and then I can print out the names stack again so we can see what's going on.

171
00:11:52,550 --> 00:11:54,400
So first we get a stack here.

172
00:11:54,590 --> 00:11:55,910
Jacob Mark and Caleb.

173
00:11:56,120 --> 00:11:57,890
Then we peek which returns.

174
00:11:57,890 --> 00:12:00,470
Jacobs That's the top element and we print it.

175
00:12:00,470 --> 00:12:01,870
Nothing is modified.

176
00:12:02,030 --> 00:12:04,360
Then we call names stack the top pop.

177
00:12:04,370 --> 00:12:07,240
And what that does is it removes Jacob from the top.

178
00:12:07,250 --> 00:12:08,030
That's pretty awesome.

179
00:12:08,030 --> 00:12:10,160
So guys this is basically it.

180
00:12:10,160 --> 00:12:11,810
This is how a stack works.

181
00:12:11,810 --> 00:12:17,510
It's last in first out the last element you add in is the first one you're able to remove.

182
00:12:17,510 --> 00:12:21,980
There is a function called peek which allows you to just look at the top element in the stack.

183
00:12:21,980 --> 00:12:28,070
There's a function called Pop which returns and removes the top element in a stack and there's push

184
00:12:28,070 --> 00:12:31,510
which allows you to insert a new item to the top of the stack.

185
00:12:31,800 --> 00:12:37,320
This is how the stack data structure works in Iowa and swift and it's basically the same in any programming

186
00:12:37,320 --> 00:12:40,350
language you might just have to change around the way you write your code.

187
00:12:40,420 --> 00:12:42,350
This is Caleb with slopes com.