1
00:00:01,096 --> 00:00:06,043
Welcome back. Today we're going to talk
about algorithms and data structures for

2
00:00:06,043 --> 00:00:10,096
implementing some fundamental data types
called bags, queues and stacks. You maybe

3
00:00:10,096 --> 00:00:15,038
somewhat familiar with these, but today
we're going to take a careful and close

4
00:00:15,038 --> 00:00:19,064
look at them. The idea is that in many
applications, we have collections of

5
00:00:19,064 --> 00:00:24,044
objects that we want to maintain. And the
operations are very simple. We want to add

6
00:00:24,044 --> 00:00:28,622
something to the collection, maybe remove
something from the collection and iterate

7
00:00:28,622 --> 00:00:33,799
through the objects in the collection
performing some operation on them, and of

8
00:00:33,799 --> 00:00:39,204
course, test if it's empty. Now for most
of these, the intent is very clear. The

9
00:00:39,204 --> 00:00:45,570
key is when it comes to removing an item,
which item do we remove? The two

10
00:00:45,570 --> 00:00:51,007
fundamental classic data structures for
this, the stack and the queue differ in

11
00:00:51,007 --> 00:00:57,001
the way in which the item to be removed is
chosen. For the stack, we take out the

12
00:00:57,001 --> 00:01:03,026
item that was most recently added for, the
terminology that we used is push to insert

13
00:01:03,026 --> 00:01:09,302
an item and pop to remove the item most
recently added. That's also called the

14
00:01:09,302 --> 00:01:15,024
LIFO discipline last-in-first-out. For
queue, we examine the item least recently

15
00:01:15,024 --> 00:01:21,045
added and those operations to distinguish
them we call inqueue to insert an item and

16
00:01:21,045 --> 00:01:27,015
dequeue to remove an item and that's also
called the FIFO discipline, first in,

17
00:01:27,015 --> 00:01:32,070
first out. So now we're going to take a
look today on how to implement these

18
00:01:32,070 --> 00:01:38,166
things. Our subtext today is all about
modular programming. And that's going to

19
00:01:38,166 --> 00:01:42,573
be a discipline that we're going to follow
up carefully throughout this course. The

20
00:01:42,573 --> 00:01:46,477
idea is to completely separate the
interface and the implementation. So, when

21
00:01:46,477 --> 00:01:53,539
we have these types of data structures and
data types that are precisely defined like

22
00:01:53,539 --> 00:01:58,530
stacks and queues and so forth, what we
want to do is completely separate the

23
00:01:58,530 --> 00:02:03,365
details of the implementation from the
client. The client has, can have many

24
00:02:03,365 --> 00:02:08,824
different implementations from which to
choose but the client code should only

25
00:02:08,824 --> 00:02:13,600
perform the basic operations. The
implementation on the other hand, can't

26
00:02:13,600 --> 00:02:19,320
know the details of the client needs, all
it's supposed to do is implement those

27
00:02:19,320 --> 00:02:24,617
operations. In that way, many clients can
reuse the same implementation. So this

28
00:02:24,617 --> 00:02:29,466
allows us to create modular reusable
libraries of algorithms and data

29
00:02:29,466 --> 00:02:34,684
structures that we can use to build more
complicated algorithms and data

30
00:02:34,684 --> 00:02:40,713
structures. It also allows us to focus on
performance when appropriate. Again, this

31
00:02:40,713 --> 00:02:45,973
is a modular programming style that's
enabled by object oriented programming

32
00:02:45,973 --> 00:02:52,246
languages such as Java and we'll be very
disciplined in our use of this style.

33
00:02:52,246 --> 00:02:59,129
Alright. So to begin, we'll talk about the
stacks. [cough] Stacks are familiar, many

34
00:02:59,129 --> 00:03:05,321
of you probably implemented stacks in an
introductory programming course but we'll

35
00:03:05,321 --> 00:03:09,948
do a thorough introduction to
implementations right now. As a warm up,

36
00:03:10,151 --> 00:03:15,729
let's suppose that we have string, a
collection of strings. They might be

37
00:03:15,729 --> 00:03:21,912
short, they might be long and what we want
to have is the ability to save away a

38
00:03:21,912 --> 00:03:26,589
collection of strings and remove and
return the most recently added string

39
00:03:26,801 --> 00:03:33,094
periodically, and also test if it's empty.
So that's our API. We have a constructor

40
00:03:33,094 --> 00:03:40,027
to create an empty stack, we have for
insert and we have a method called push

41
00:03:40,027 --> 00:03:46,861
that takes a string as argument. And for
remove, we have a method pop that returns

42
00:03:46,861 --> 00:03:53,196
to the string most recently added. And we
have these empty test which returns a

43
00:03:53,196 --> 00:03:59,620
Boolean. Also in some applications, we
would include the size as well. So again,

44
00:03:59,847 --> 00:04:06,241
as always, we'll first read a client and
then look at implementations and our

45
00:04:06,241 --> 00:04:13,376
client, simple client is to take some
strings on standard input and some pop

46
00:04:13,376 --> 00:04:20,917
commands which are indicated with hyphens.
And so, it'll this client reads strings

47
00:04:20,917 --> 00:04:27,742
from standard input. If the string is
equal to the hyphened character, it'll pop

48
00:04:27,742 --> 00:04:34,026
the string at the top of the stack and
print it. Otherwise, if it's a string

49
00:04:34,026 --> 00:04:39,209
that's not equal to the hyphen character,
it'll just push it on to the stack. So in

50
00:04:39,209 --> 00:04:45,436
the example down below here if we have
this file called tobe.txt then what we'll,

51
00:04:45,436 --> 00:04:51,488
what the client will do is push to be or
not to all in the stack then when it comes

52
00:04:51,488 --> 00:04:57,754
to this hyphen it'll pop the most recently
inserted item which is two in this case

53
00:04:57,754 --> 00:05:03,757
then it'll put b in the top of the stack
and then pop the top item on the stack

54
00:05:03,757 --> 00:05:09,653
which is now b and then pop the item most
recently added, b is gone, two is gone so

55
00:05:09,653 --> 00:05:15,642
the next is not and so forth. So, this is
a simple test client that we can use to

56
00:05:15,642 --> 00:05:22,444
test our implementations. So now, let's
look at the code for implementing a stack.

57
00:05:22,444 --> 00:05:28,094
Now, the first implementation that we'll
look at, uses link list. If you're not

58
00:05:28,094 --> 00:05:35,294
familiar with the link list you'll need to
review that in section 1.3, 1.3 at the

59
00:05:35,294 --> 00:05:41,710
book or in our Introduction To Programming
Java book. Even if you are familiar with

60
00:05:41,710 --> 00:05:46,954
link list, it's worth taking a look at
this code because it's the style of coding

61
00:05:46,954 --> 00:05:52,420
that we'll use throughout the coarse for
much more complicated data structures. So

62
00:05:52,615 --> 00:05:58,449
the idea is to keep a link list where
which is consists of nodes that have

63
00:05:58,449 --> 00:06:05,867
strings in them and references to the next
item in the link list and to, to implement

64
00:06:05,867 --> 00:06:12,320
a stack when we do a, a push operation, we
insert a new node at the beginning of the

65
00:06:12,320 --> 00:06:18,802
link list and we do a pop operation where
we move the first node from the beginning

66
00:06:18,802 --> 00:06:24,943
of the link list, that's the most recently
added items. So, let's look at what that

67
00:06:24,943 --> 00:06:31,440
code looks like. We use to implement link
list in all linked data structures through

68
00:06:31,440 --> 00:06:37,066
out the course. We use what's called an
inner class in Java and that's just a way

69
00:06:37,066 --> 00:06:41,669
to describe that we're going to be
manipulating node objects that consist,

70
00:06:41,669 --> 00:06:48,052
each consist of a string and a reference
to another node. So, the pop operation for

71
00:06:48,267 --> 00:06:54,594
link list is very easy to implement.
[cough] first, we, we're going to need to

72
00:06:54,594 --> 00:07:00,874
return the first item on the list so we
save that away. Take first that item and

73
00:07:00,874 --> 00:07:07,458
save that in the variable item. A h, then,
to get rid on the first node, we just

74
00:07:07,706 --> 00:07:14,904
advance our pointer to the first item on
the list to point two of the next item and

75
00:07:14,904 --> 00:07:20,181
then that first node is ready to be
reclaimed by the garbage collector. And

76
00:07:20,181 --> 00:07:26,310
then, the last thing we need to do is just
return the item that we saved away. Okay,

77
00:07:26,310 --> 00:07:32,065
so that's the pop operation. What about
the push operation? [cough] push

78
00:07:32,065 --> 00:07:37,231
operation, we want to add a new node at
the beginning of the link list. So, first

79
00:07:37,231 --> 00:07:42,778
thing we do is save a way the pointer to
the beginning of the list. That's a little

80
00:07:42,778 --> 00:07:48,021
first thing first. Then we'll create a new
node, that's going to be the new node that

81
00:07:48,021 --> 00:07:53,037
we put at the beginning of the list,
that's first equals new node. And then we

82
00:07:53,037 --> 00:07:58,060
said it's instance variables. It's items
is the string that we want to put at the

83
00:07:58,060 --> 00:08:02,934
beginning of the list, in this case, not.
And it's next is the old first item of the

84
00:08:02,934 --> 00:08:07,640
list which is now the second item of the
list. So, after this operation, we are

85
00:08:07,640 --> 00:08:12,511
first pointing to the beginning of the
list and we have the items on the list in

86
00:08:12,511 --> 00:08:18,699
decreasing order of when they were put on
to the stack. So that also is a four liner

87
00:08:18,930 --> 00:08:24,784
to implement the stack push operation. So
this is a complete link list

88
00:08:24,784 --> 00:08:31,083
implementation of all the code to
implement a link list for a stack of

89
00:08:31,083 --> 00:08:38,308
strings in Java. It's, it's a class the
constructor doesn't have to do anything,

90
00:08:38,308 --> 00:08:44,526
there's no constructor. We have this inner
class that we use to build the items in

91
00:08:44,526 --> 00:08:50,826
the link list and we make them an inner
class so we can directly refer to those

92
00:08:51,050 --> 00:08:56,085
instance variables. And then the only
instance variable of a stack is a

93
00:08:56,085 --> 00:09:02,344
reference to the first node on, on the
list and that starts out being null. Then

94
00:09:02,544 --> 00:09:08,525
it's empty is just testing whether the
first node on the list is null and then

95
00:09:08,744 --> 00:09:15,667
push is the four lines of code that I gave
on the previous slide and pop is the three

96
00:09:15,667 --> 00:09:20,903
lines of code that I gave on the slide
before that. Tha t's a complete

97
00:09:20,903 --> 00:09:26,582
implementation for the link list that'll
work with as a fine push down stack

98
00:09:26,582 --> 00:09:31,848
implementation for any client. So now we
can analyze the performance of that so

99
00:09:31,848 --> 00:09:36,880
that we can provide clients with
information and how well the algorithm

100
00:09:36,880 --> 00:09:42,082
data structure will perform. In this case,
it's easy to see that every operation

101
00:09:42,082 --> 00:09:48,050
takes constant time in the worst case.
There is only a few instructions for each

102
00:09:48,050 --> 00:09:53,097
one of the operations, there's no loops.
So that's obviously a very desirable

103
00:09:53,097 --> 00:10:00,024
characteristic. Then how about space
units, usage? Well, that depends very much

104
00:10:00,024 --> 00:10:06,578
on the implementation in machines so this
a typical Java implementation that we'll

105
00:10:06,578 --> 00:10:13,798
do the analysis for and contest this out
for different types of environments easily

106
00:10:14,022 --> 00:10:20,727
in this representative. So, in Java, an
inter class there's for every object there

107
00:10:20,727 --> 00:10:26,490
is sixteen bytes of over head. There are
some extra over head, eight bytes because

108
00:10:26,490 --> 00:10:31,541
that's an inter class and then there is
two references that we built in our, in,

109
00:10:31,541 --> 00:10:36,892
in our class node. One to string and
another one to a node and those are each

110
00:10:36,892 --> 00:10:41,531
eight bytes. So, we have 40 bytes per
stack node, if we have a stack of size n,

111
00:10:41,531 --> 00:10:47,584
we have about 40 n bytes. That's a little
extra first but that's about an overhead

112
00:10:47,584 --> 00:10:53,095
for the whole stack but when n is large,
40n is a very close estimate to the amount

113
00:10:53,095 --> 00:10:59,386
of space needed. This does not include the
space for the strings themselves which are

114
00:10:59,386 --> 00:11:05,378
owned by the client. But with that, we can
properly asses the research usage of this

115
00:11:05,378 --> 00:11:11,766
implementation for different client
programs. Now it's constant time but

116
00:11:11,766 --> 00:11:18,557
there's faster implementations of stack
and since stack is used inner loop of some

117
00:11:18,739 --> 00:11:24,063
algorithms it's important to think about
even faster implementations. And another,

118
00:11:24,063 --> 00:11:29,904
natural way to implement a stack is to use
an array to store the items on a stack so

119
00:11:29,904 --> 00:11:35,299
let's take a look at that. This
alternative of choosing between length

120
00:11:35,299 --> 00:11:40,616
structures and arrays is fundamental and
it's go ing to come up again and again

121
00:11:40,616 --> 00:11:46,189
when we consider more complicated data
structures in algorithms. So, we want to

122
00:11:46,189 --> 00:11:51,594
be sure to analyze it in the simple case
for stacks to set the stage for more

123
00:11:51,594 --> 00:11:57,676
complicated applications later on.
Alright, so the use in array we just keep

124
00:11:57,676 --> 00:12:05,320
the n items on the stack in the array and
the array location within the n is the

125
00:12:05,320 --> 00:12:13,564
place the top of the stack where the next
item is going to go. So, to push we just

126
00:12:13,564 --> 00:12:20,006
add a new item at s(n) into pop we remove
the item that's at s(n) - one and

127
00:12:20,006 --> 00:12:27,050
decrement n. Now there is a fundamental
defect in using an array and that is that

128
00:12:27,300 --> 00:12:32,552
you have to declare the size of array
ahead of time and so the stack has a

129
00:12:32,552 --> 00:12:38,174
certain capacity. And if there is more
items on the stack than the capacity we

130
00:12:38,174 --> 00:12:44,116
have to deal with that problem and that's
a fundamental problem that we have to deal

131
00:12:44,116 --> 00:12:49,479
with in array implementations in all sorts
of algorithms and data structures. So

132
00:12:49,664 --> 00:12:55,733
again, considering it for the simple case
we'll pay off later on. Alright, so here's

133
00:12:55,733 --> 00:13:03,082
the full implementation of stack for using
an array to represent the stack. So now we

134
00:13:03,082 --> 00:13:10,266
have an instance variable which is an
array of strings and or variable n which

135
00:13:10,266 --> 00:13:16,278
is both the size of the stack and the
index of the next position, next open

136
00:13:16,278 --> 00:13:22,151
position on the stack. This one has a
constructor and the constructor creates

137
00:13:22,151 --> 00:13:27,539
the array. Now, we are cheating in this
implementation to keep it simple and we'll

138
00:13:27,539 --> 00:13:32,419
take care of this cheat in a little while
by requiring the client to provide the

139
00:13:32,419 --> 00:13:37,066
capacity of a stack. In a few applications
this might be fine but in many, many

140
00:13:37,066 --> 00:13:41,571
applications that's two owners are
requirement and client really can't know

141
00:13:41,571 --> 00:13:47,011
how big the stack is. Client might have a
lot of stacks that need to be maintained

142
00:13:47,011 --> 00:13:52,124
simultaneously and then maybe they reached
their maximum capacities at different

143
00:13:52,124 --> 00:13:56,883
times and various other things. So, we
need to remove this cheat and will. But

144
00:13:56,883 --> 00:14:03,217
the code is nearly trivial. If we have the
capacity to check if it's empty we check

145
00:14:03,217 --> 00:14:08,573
if n is zero. To push an item we use n to
index into the array put the item there

146
00:14:08,573 --> 00:14:15,003
and then increment n, that's the short cut
in many programming languages nowadays for

147
00:14:15,003 --> 00:14:20,305
use the index and then increment it. And
to pop we decrement the index and then use

148
00:14:20,305 --> 00:14:26,067
it to return the item in the array. So
each of the operations is a one liner and

149
00:14:26,067 --> 00:14:31,406
this is a fine implementation for some
clients. That's array implementation of

150
00:14:31,406 --> 00:14:37,131
stack but it breaks the API by requiring
the client to provide the capacity. So

151
00:14:37,131 --> 00:14:41,749
what are we going to do about that? Well,
there are a couple of things that we

152
00:14:41,749 --> 00:14:46,792
didn't consider. We didn't put in a code
to throw an exception if the client pops

153
00:14:46,792 --> 00:14:51,433
from an empty stack. Probably should do
that and for overflow, what happens when

154
00:14:51,433 --> 00:14:56,962
the client does too much well, we're going
to talk about an approach called resizing

155
00:14:57,216 --> 00:15:05,254
that will allow us to avoid overflow for
clients. There's another issue about

156
00:15:05,535 --> 00:15:12,539
whether clients can insert null items into
the data structure. In this case, we do

157
00:15:12,539 --> 00:15:19,026
allow the client to insert null items but
we do have to worry about in Java about a

158
00:15:19,026 --> 00:15:25,517
problem called loitering and that is the
idea that we have references to an object

159
00:15:25,517 --> 00:15:31,630
in our array implementation and the stack
array and we are not really using it. So,

160
00:15:31,832 --> 00:15:37,300
when we decrement that value in, there's
still a pointer to the thing that we took

161
00:15:37,300 --> 00:15:42,990
off the stack in that array even though we
know we're not using it. The Java system

162
00:15:42,990 --> 00:15:50,054
doesn't know that. So to avoid that and
really allow most efficient use of memory

163
00:15:50,311 --> 00:15:57,028
it's best to set that. [cough] removed
item entry to null so there's no reference

164
00:15:57,028 --> 00:16:02,742
to the old item left there and then the
garbage collector can reclaim the memory

165
00:16:02,945 --> 00:16:09,467
since there's no outstanding references.
So that's a, a detailed but an important

166
00:16:09,467 --> 00:16:15,049
one that we have to take care of and or
implementations to make sure that we're

167
00:16:15,049 --> 00:16:25,082
getting most efficien t use of memory.