Video 2-1: §2.1 ADTs, Stacks and Queues

0:00 Intro

0:03 welcome to unit two of com five to six we'll talk about fundamental data structures things that some of you will know others will not have seen will go at a pace that's not right for anyone it's too fast for those who haven't seen it too slow for those who've already seen it but it's the best i can do in a single lecture i try to give additional material online and i try to do give some some hints and connections that people who haven't have seen it before might not have heard because they're a little additional to the standard content that's that's my way of of trying to strike this balance i hope it works somewhat for all of you

0:42 Outcomes

0:45 i do love this unit because it's beautiful topics even though they're quite basic there's lots of beautiful ideas in it and i hope at least you can take some appreciation and joy out of those even if you have seen them before the outcomes for me the biggest one maybe is the distinction between an abstract data type and an implementation of a data structure where an implementation is a data structure in this sense we'll talk about that at length if you haven't seen it i think this is just conceptually very useful in in many different applications it helps you become better programmers as well i think so we want to be able to define concrete examples of abstract data types ones that occur often and these are the ones we want to understand very basic implementations data structures that implement some of these abstract data types and two slightly more sophisticated ones but still undergraduate level and those are binary heaps and binary search trees okay

1:49 Sections

1:53 there's quite a few of sections these sections basically reflect the videos that i made last time so each of the sections should be between 10 and 30 minutes of lecture so you see this fills two full days and probably i won't be able to squeeze it into two days because we started a bit late we'll talk about very fundamental data structures and how to implement them and then about priority queues and how to implement them than about simple tables and how to implement them and split up so that it's in digestible chunks

2:23 Stacks

2:28 let's start with stacks and cues and before we continue with that uh i'd like to have a quick look at slido to see how much you have seen of this

2:42 okay so a few people have not seen any of the data structures uh most people have seen arrays and linked lists but not so many binary heaps okay um but many more people binary search trees that's interesting uh good to know uh fibonacci heaps is a much more sophisticated version of priority queue just a few skip lists hash tables we won't talk about hash tables at length even though i would like to but i had to make a cut at some point okay thanks a lot um that means i should probably on the binary heaps at least give you a fair chance to understand them if so many haven't seen them but before we get to that let's start with the more basic stuff

3:29 and the first thing is this distinction i already mentioned in the outline what is an abstract ah sorry guys i didn't switch the screen what is an abstract data type and what is a data structure an abstract data type is is basically an interface that gives access to certain data in a certain way and we do this by supplying certain operations that we support we'll see examples soon which makes this a probably a bit more tangible uh the abstract data type only tells you what should happen it doesn't tell you how to store the data it doesn't even talk about any any kind of storage or representation it doesn't tell you how to implement the operations how these are done it just tells you what you're supposed to do and what the operations allow you to do in programming languages there's some support for doing abstract data types for for realizing that in in languages but none of them is complete in exactly reflecting what an abstract data type is for those of you who know java there's the type the interface construct and python has something like this as well can i have a quick hands who has seen abstract base classes in python

3:37 Abstract Data Types

4:57 that's like a handful of people is it's a topic that might not be covered as often in python because it's considered a bit more advanced but if you want to object oriented if you want object orientation in python you hardly get around it i'd say um if you haven't seen it seen it maybe i can find out some some find some nice tutorials it's not really relevant for us but it helps you link things if you have seen it so in in python there's a way to represent interfaces similar to that where you can say uh any object that i want to consider of this type should have these these methods should have functions of this of this name i would say in both cases we want to include the comments that explain what the functions do as part of the interface or part of the abstract base class because this is what an abstract data type also tells you it has operations and an explanation what they do

6:00 and let's contrast that with data structures which exactly tell you how to represent data not just what to do they tell you exactly how operations are implemented what are each what are the algorithms for doing that and you can for a data structure precisely analyze how much space does it need and how long do the operations take again in the worst case in the average case all these things we discussed last time on a word ram or by counting fundamental dominating operations dominant operations this is this is what you've seen and in java and python these are basically classes so they a class is a template for creating objects an object is a specific instance of a data structure and the class is the implementation is the data structure itself somehow that's how it maps to programming constructs

6:55 Why Decouple

6:59 why do we want to separate these two things in the first place i think there's a practical reason in programming it's just very convenient to decouple things so that you can change one part of the program maybe improve it by replacing with a more sophisticated and more efficient implementation without having to change the rest of the code

7:23 people call this a drop-in replacement you can just take a piece of code change it to something else and the rest will remain working without any any further changes that makes code reusable and allows uh to build libraries in a sense in the first place i also think conceptually it helps because better abstractions give you a name so you can a complicated concept can become a single single variable a single name for you in your brain that helps you build bigger systems we'll come back to the last point

7:59 Warning

8:03 a little uh warning at this point though sometimes as in this picture things can go a little awkward if you have interfaces and you limit yourself to an interface it might look like this is a tab somewhere that you can only access by turning there but actually there's a long hose attached to it and if you need it to get water somewhere else it might be better to just detach that hose or or at this point whatever and pull that over so sometimes it's useful to break open the encapsulation the abstraction of a data type and look at what is inside so don't slavishly follow uh a certain interface if it looks like you're building something like on the picture that that

8:54 stops you from implementing optimizations you otherwise would have would have had but it looks nicer to use this that's why people like abstract data types as well okay we've discussed this uh sorry no we didn't i thought that was the other question you didn't see anything right did you

9:26 let's try this quickly uh for those who have seen this which are examples of abstract data types now of course everyone's at at home is at the advantage of just scrolling back in the video

10:26 okay i think we're expecting some 10 more people something like that okay i'm locking the question five four three two one oh someone just last minute submitted their their result uh okay so you can see on your phone what how you did and i'll switch back um

11:00 i will i will discuss all of these later so uh just very briefly stacking and deck so deck is a a queue and a stack in one thing uh these are abstract data types queue as well and priority queue and dictionary or simple table and the others are either just an abbreviation or their data structures

11:20 Stack

11:24 let's make this more concrete and look at one specific simple abstract data type and that's the stack and here is the list of operations that a stack can support it can give you the top most elements so you think of this stack of books and you're not allowed to play this balancing game you're not allowed to pull out a book from below you can only access the topmost book you can add a not a new book on top though that's fine and you can remove the topmost so the difference between top is top just lets you look at the top most but leaves the stack unchanged and pop takes the top most off and returns it to you okay and well a few other less exciting methods you can check if the stack is empty that's often convenient and you can start with an empty stack do the operations make sense so notice again there's this stack of books which has nothing to do with the computer but this stack of books is somehow an implementation of this idea of of a stack and and that's how i would like you to think about abstract data types they only tell you how things happen they don't show how you actually organize data but we'll of course come

12:40 back to that as well all right let's do this a quick question on whether you follow this it should be an easy one okay i'll give you a few more seconds but the results look fairly clear

12:47 Test

13:50 three two one ah this tension okay so this seems to seems to be quite clear so that's the right answer because basically we have the stack shown like this five four three two one um i'd like to have this black rather uh then we pop the first two off so these are gone i could actually just erase them then we push another one on top and if you read this top down again then we get this answer okay so you understood how this stack works that's great and then let's rush on something that many of you will also have seen is how you can implement a stack there's different ways one is to use a linked list and many of you have seen this so let me do this very briefly the idea is you maintain a pointer top that's a global variable which points to the the topmost element in the stack

14:34 Stack Implementation

15:08 and then here's one element say our one from before and another pointer which points to the next element further down in the stack so that was three and then this points down here

15:23 and we had two more we had four at five and this pointed to this one this pointed to this one and this one pointed nowhere it was null so that's the end of the stack that's oh now you could figure out how we can implement all the operations uh but i think most of you have seen this before so what i draw by these boxes and arrows is an abstraction of how you would implement this in a in a program in a computer

15:53 the pointers these arrows are addresses in memory you use objects maybe there's a class in python that has these two fields one for the element and one for a pointer to another element another box um

16:08 and then these are represented as just memory addresses where this next object begins uh i assume this is something you've seen before or at least you've done something like this in the python introduction or in your undergrads

16:27 Stack Analysis

16:31 let's have a quick look at the analysis though i don't know this is maybe something that not all previous courses have emphasized we need for every element on the stack we need one of these boxes so it's linear space we can express this in our fancy new notation it's theta of n space and we can measure the space in computer words again that's the word ram model if we have n elements currently on the stack and the operations all take constant time because they all mean follow a pointer from top and then do something with this topmost element either return it or remove it and return it or create a new object on top point it to the previous top most and re-wire top to point to this new one so these are all things that take a constant amount of uh of time it doesn't depend on how high the stack is okay so this is actually brilliant because this is the best you could hope for we definitely need linear space to store all the elements and we can't get better than constant time for the operations so in in terms of these theta classes we cannot hope for any better implementation of a stack

17:50 Arrays

17:54 this uh if you look a little closer though there's a little disadvantage of this we need to store end pointers for this linked list based stack and that's a little wasteful we only really need to store the elements in an ideal world and not as many pointers on top so maybe we can get rid of those and we can um by using an array instead of uh

18:21 of a linked list and let me draw the array um like we draw stacks so start with 0 1 2 and then count upwards so we can also represent our stack in here by storing the elements like so and we have again um a top top is again a variable for the entire stack and that just stores the index of the top most no one can read this but it's supposed to be a three so we just store the index of the topmost element currently in the stack

19:05 and we maintain the topmost position now there is a catch with this and um that is if we fill the array entirely so if top is the size of the array then what should we do um upon a push

19:30 if we get another push and the stack is full we don't have space in the array so we're kind of we're throwing our hands up and start crying uh so what this is at the moment is a fixed capacity stack we have at creation time we have to tell what's the maximal number of elements we'll ever going to put into this stack and we can't push more elements than that

19:53 then we need theta of c space again if c is too small you're screwed if c is too large you waste the space what's good is all operations are again constant times and they're they tend to be faster than in the link based representation a smaller constant but it looks like we started with this idea let's try to save space by not have pointers and now we still have this problem that we need to know the the final size and looks like we're we're not improving on space so much

20:31 so there's a slight modification of this which rectifies at least the problem that we need to know this this capacity uh but it turns out to some degree you can't completely avoid having extra space uh you need a little bit of extra space if you want to have the ability to grow beyond beyond size

20:52 and there's some interesting quite complicated theoretical data structures that try to push this to the limit but we won't cover this