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

0:03 in unit two of comp 526 we'll look at some fundamental data structures which are often covered in undergraduate algorithms and data structures classes I'll just give you a a very quick rundown showing you the gist and the basic uh fun the basic results from those that we'll use uh and build on in other units this will be very fast-paced if it's the first time you see the topics if it's a refresher then maybe at some some intermediate stages you you'll get bored a little bit uh but at least it's fresh in your memory then for the upcoming units so specifically um what I want you to take from this the distinction between an abstract data type and its implementation something we'll talk about then um a a list of concrete abstract data types that I think are useful to know outside of this unit as well outside of this module we'll specifically look at a few implementations specifically these that are listed here um I will go through those so no need to um um discuss them in detail now these are basically the upcoming

1:19 sections we'll start with a very basic data structure stacks and qes and then basically look at at two others um binary heaps and binary search trees I recall from from yesterday from unit one what we're working on at the end of the day is our abstract model of a computer the random access machine and uh uh we uh basically have just one big piece of memory but we assume that there is something like a memory allocation system so you can just wish for a new instance of an object and your wish shall be granted the operating system somehow hands handles this for you there's a few um basically these work for for every programming language will give you access to some of these features um because we're doing most of it in Python there's a few caveats so we'll we'll assume that we can do basic pseudo code on our Ram uh discussed this yesterday in detail that we can create arrays and we can create objects now uh much of this you can just do in Python and pretend it is a Ram for all intents and purposes except for arrays python doesn't really nicely have arrays I know this statement is technically not quite true there's a part of the standard library that gives

2:45 you access to more lowlevel arrays it's just not a very um intuitive way and the standard thing you use in Python are lists so if you just write these uh square brackets that would be a list and the object that backs it has many features of an array but it is dynamic in size so you can change the size whereas arrays are always of a fixed size that you have to uh specify at allocation time we'll actually look in this module at what python does under the hood because python does run on a on a computer where the operating system just gives you fixed size array there's no such thing as a resizable array provided by the operating system and python gives you this abstraction and we'll look at how this is done it's a very standard trick so it's just a point point to remember will mostly write code as if it was python but it's not really a random access machine if you write python code so it means some things that you can write in Python in a single line or a single build-in function doesn't actually take constant time classic example if you uh if you have a very long list and you insert something in the middle it's linear in the size of

4:00 the list it's not constant time it's a very expensive operation if you do it on a long list that's just something to be mindful of with that said let's look at our first examples uh of some uh data types abstract data types and um implementations and before we get to that I should finally tell you what I mean when I say abstract data type so here's a a a list of of the properties of the two an abstract data type tells you what the operations are that a certain structure is supporting it tells you what should happen but not how it's done so in a way uh you can con you can compare it to an interface or these abstract base classes in Python which is maybe a bit more of an esoteric feature that not too many people use all the time but python has something like this if you want to read it up the the basic idea is you tell the programmer someone who uses your data structure what they can do and you don't tell them how it's done not because you're a mean person and don't want to keep give your secrets away but because that means you can implement it in a different way and the user can't really

5:20 notice because you haven't told them so you can swap out implementations afterwards in programmers terms people call this a drop in replacement for some part of the code right if uh if you program just against the public interface of a data structure which is in older terms so This this term predates interfaces in modern languages that's why people stick with abstract data type uh we can debate if the term is great but I'll I'll stick to it because it's it's very standard in in textbooks and so on if you program just against these public methods then you can swap out how it's done under the hood and it shouldn't change your program so that's the essence of producing reusable code which is as we know is one of the only ways how we can tame complexity in programs good abstractions and Independence between Parts but on the other hand at some point you have to uh you have to show how things are done and you have to implement them if you actually want to run them so data structures are flushing out all the parts that are left open uh I said this last time already so they they tell you exactly how data is represented and how these operations are are implemented what algorithms are used

6:38 for those the rough equivalence could be uh in Java you have interfaces and then classes implementing an interface uh in Python you can have a subtype of these abstract based classes but is a little less direct uh what I want to point out is um in in Java for example an interface is merely syntactical it just tells you what the methods signatures are the names of the functions and the types of the parameters and that's it it's very shallow it doesn't tell you anything about the meaning maybe you have Java doc a comment about it or a doc strings in in Python you have some natural language text that explains to the programmer what that thing should do but this is not enforced on the technical side uh we'll be a bit more strict we uh we require that our abstract data types tell you exactly what the meaning of these functions is uh without having a formal way to check it which is assume that you do this as a

7:45 human I already dra uh talked about why uh it's useful to have abstract data types so you can swap out uh the implementations uh there's another one that I haven't touched on which is a A Little Less Direct but if you keep things generic and you prove a general result about the generic thing it's more applicable it holds for everything so sometimes you can prove a lower bound which is an impossibility result lower bound means you cannot possibly do better than a certain running time for example and we'll see an example for sorting um that you've seen in undergrad classes if you've done so those in computer science uh but that's that's only really effective if you have a level of abstraction so we'll come back to that um not so much today but uh that's another advantage of of staying a bit more abstract now there's also a downside that I just want to humorously point out with this picture sometimes if you enforce a certain abstraction and a certain weird interface it might it might mean you make your life more complicated like in this case you just want to get some water but then you had to build this weird structure to have have it look like a nice nice water tap

8:54 whereas if you need the water further away you could have just taken the hose and and carried it over over but that's hidden by the abstraction if you just look at the at the tab from the front you can't move it anymore this sometimes happens so abstractions are great but it's important that you're able to look behind them because sometimes if you crack them open you get a much better solution so don't slavishly follow abstract data types but it's it's important to know them because they're the language people use uh and they're generally

9:29 useful all right enough of talking for me for a moment let's see if that has sunk in and if you uh know a few of these already I guess for those where you don't know what the what the name stands for it's a bit you can't really give a sensible answer either way and I guess you'll just have to uh to

10:46 we had 126 people vote on the welcome thing and then 89 for the attendance code if you want to do me a favor for the attendance code I will sent this got it so that I know how many people we have in the room it's bit easier then for the next section uh so we're already at 86

11:12 89 let's see if we can get 100 full again it's nice a few people are still typing goody I'll start showing some some results um I don't want to discuss this in in too much detail we talked about Stacks now several of these terms as I said if you don't know what the term stands for uh you can only guess uh we'll come back to those so I'll just leave that without much um without much comment but here's that's that's the right answer um and and basically all of these will touch on in this unit so you'll see them and and the rest I mean ADT is just the abbreviation but the others are um implementations are data

12:18 structures let's have a look at F which uh let's take it offline okay um let's let's look at a first um ADT for uh for this unit it's a very simple one it's a stack and as the picture shows you can put things on top and you can get the topmost item out let's assume there's no way for you to balance and pull out the book from the middle so you can do top get the topmost item you can put another book on top and you can say pop which removes the topmost and a few helper methods that are not so important so let's see just uh that everyone's clear on this but I'll I'll do it quickly on this

13:31 one so you have some stack of this type with one at the top so it looks like yeah looks looks like you got this so uh you can still put in your answer but you may see that the vast majority came down to the same thing so if we do one pop then we remove the one if we do another pop we remove the two then if we push one again we put the one here and so in the same convention like I did it here reading from top to bottom we have 1 three four five so that's this one

14:34 right good so that's that's how Stacks work again remember this is an abstrct data type it only tells you what is supposed to happen it doesn't tell you how it is happening and there are different ways how to do it I want to just briefly show you the two main ones uh the easiest one is with the linked list and if you've seen this before that's all you need to know but I wanted to show uh some well python inspired code it's not python by the syntax we need a certain uh class that has two Fields a value that we store that's the value on the stack and a pointer to the next thing um and then uh the way this works is we have a top Mo a pointer that points to the topmost item on the

15:28 stack and then this item has two Fields right it has the value and it has a pointer to the next item so it points down to the next one and at some point uh we stop so this is pointing to null just draw this like that then uh that signals the end of the stack and now if we want to get the top item we just follow the top point and return the value that we find there we want to push a new item we add a new and this doesn't it doesn't matter where this is drawn it could be over here so we add a new item zero so we create this new note uh which points to wherever top pointed to and then we reset top to now point to this new item and that way we have added a new element on top and pop works in the opposite way you first get um the topmost item and then you just set top to wherever that pointed to so you rewire it like this I'm doing the pop again instead of that and uh you return the old item in this in this implementation that depends on how you do it so in a way this is still around we still have this element

16:55 that points to the the now top element but the data structure only cares about what follows from Top now what can we say about this implementation so that's a data structure right it implements the stack abstract data type just to get the terms straight um what's good about this well if we have n elements on the stack we probably need to store those n elements so we will have linear in n space overall that's inevitable also all operations just take constant time if you just go back to the code all they do um with our assumption on the random axis machine takes constant time um what's a bit uh a bit unsatisfactory maybe is that we have a an extra overhead of space for every element we store a pointer which means we have linear overhead in space and we could try to get a uh try to reduce that at least

18:00 so one way to do without pointers is to use an array instead and so uh if you draw an array not in the usual way left to right but kind of flipped 90° you could imagine you have a a variable top that just tells you at at what position is the current top of the stack so maybe you have these numbers again and then these are indices in the array 0 1 two 3 and then top just stores the index of the topmost element in this stack and you can implement the other operations similarly if you want to push something you write it to the next free cell and increment top if you want to pop you just decrement top uh so that's all relatively

18:56 easy but there's a problem if I have an array I told you earlier it has has to have a fixed size so I I have to allocate an array of a certain size I need to know it up front so if I keep pushing onto my stack I eventually have the entire array used up and then I can't push anymore and in a way for for a a strictly array based implementation that's impossible to solve so we have a fixed capacity and we have to the user has to promise us that they will never push more elements than the capacity of this array is uh but we need to know this up front so it's not strictly a full implementation of the abstract data type and and also if you look at it we always need linear we always need space c even if we just have five elements on the stack C might be much bigger so we tried to save space but it's is not necessarily so much better now um but the operations take constant time and in practice they're usually faster than doing a link list

20:03 uh those are the two the two different ways to implement arrays um basically that's all of the all of the ways that will uh sorry that's the two ways to implement Stacks e link list or or an array uh that's the two main ones um and these are also usually offered in some form in in the standard

20:28 Library let's look at at the same time at a small relative of the stack which is very similar to implement has a slightly different notion that's the Q uh it again is some um some data structure so here again that's the abstract data type has two operations inq and DQ you can add a new element and you can take the the front of the que but of course the uh the notion in a que if you're doing this in this in the proper British style you inq at the end and DQ from the front you're the next to go into the store whatever that is so the absor data type is different the order of elements that you obtain from getting elements out of this out of this data structure is different from a stack but the implementation can actually be very similar and uh I'll leave that to you to figure out or you can watch the video on it if you haven't seen it the the two same options exist and they have essentially the same

21:42 tradeoffs sometimes it's convenient to have a an abstraction that that captures both of these um what they have in common is that they're somehow a collection that you can put things in and you can get things out that's what stacks and q's both do so they both have an insert operation even though it has been given a special name and there's a way to get an element out in the general back you just say delete any element and you don't make any guarantees so this is this is less strict than a stack or less strict than a q so you can take any implementation of stack and Q and say Ah that's a bag it's a special kind of bag that gives you a specific order but if you program against the uh the interface of a back you're promis say you don't make any assumptions on the order um yeah this also exists uh in a under the name collection in standard libraries uh usually so there's there's not really a way to implement backs in a more efficient way than Stacks or cues but it can be useful for you as a programmer to express that what you need is just a back you don't care at all about the order of removal of the

22:56 elements