Video 2-1: §2.1 Stacks and Queues

0:00 Introduction

0:03 welcome to unit 2 on fundamental data structures this will be the first unit where we really dive into the computer science topics and we leave the mathematical preliminaries behind us finally it will be a recap unit for all of the for all of you who have an undergraduate degree in computer science you will have seen most of what i present and i also will go over this at a fairly fairly rough pace so there's a lot of extra material on the website in particular really well done lecture videos professionally studio recorded ones they're not for free but they're really worthwhile investing time and a little money into them if you want to understand these topics in more detail for what we need in this class and for your course uh everything will be covered in the lecture but again um if you feel you want to be a full-fledged computer scientists you won't get around knowing the basics of these data structures and my lectures today and next week will probably only scratch the surface if you want to go deeper you're encouraged to check out the website

1:18 but uh that said let's um let's see what what i can do for you today we'll talk about the very basic data structures and i will probably start with a little bit um of what linked lists are maybe just the term was not what we what you uh knew we'll talk about resizable arrays um and as a as a building block for other data structures and finally the two big classic data structures in computer science that build on these very elementary ones priority queues and binary search trees

1:54 first very basic data structures stacks and cues that you might have seen or maybe even the terms are intuitive enough to make out what they mean but i will use these to also introduce the concept of abstract data types which is an important conception an important concept in computer science that people found very useful so let's let's look at what that is the contrast is to be drawn between abstract data types on the one side and concrete data structures on the other side and if you're if you've learned programming in java then you will it will help you to think about abstract data types types as something like the interfaces in java where you specify the operations of the methods but you don't provide any implementation and data structures are the concrete classes that implement a certain interface

3:02 of course you can have classes that don't implement nd interfaces but what i really mean is you have an abstract data type on the one side an interface and then a class that implements it there's this analogy is useful but it's not a complete and true representation of what abstract data types are so um it's it's helpful to keep the two separate

3:30 oh i see someone pointed out that the question i asked only allowed one answer and that's of course nonsense so let me maybe open that one again let's reset the results and just do that exercise again thanks for pointing that out

3:59 it's a weird interface in in slido if you don't say limit options then it's just one okay so we get a different turnout um i'll briefly show the turnout element the distinction between abstract data types and data structures is fundamental so i want to cover that part either way so java interfaces are what you can think of but an abstract data type has to have a little bit more than just a method name it has to list the supported operations but it should be precise in specifying what exactly should happen so you want a little bit of a clear description it can be a natural language as use as usual we if we're doing this for humans it can also be a little more formal than that what it does not specify is how to implement it to implement the operations and it also doesn't say how to store data that is associated with a certain data structure

5:05 and on the other side data structures do exactly that they tell you exactly how the data is represented they tell you exactly how the operations are implemented and it has because of that the algorithms have concrete cost in time and space

5:23 using the analysis methods from them from the last unit you have a an idea how to work out these these costs so this is what you can really implement in in a program and what you can run an abstract data type is just a shallow interface where you can't really use this to to run a program you always need an implementation

5:50 you can argue why it makes sense to separate the two i can think of a couple of reasons in practical from from a practical perspective it's helpful if you can swap out implementations that's what people in in java do a lot you can say i have a list of objects and then you can specify it's a linked list or an array list

6:15 that makes code more reusable both on the client side that uses a data structure or an abstract data type then and on the implementation site of a specific abstract data type you can create linked lists once and use them wherever you need them it's also helpful because it often allows better abstractions and i think this is under uh it's underappreciated how much that helps to build uh programs and to understand a task attend a comp a computational problem uh and lastly it's also um the way to approach lower bounds if you can isolate the functionality of a certain task to an abstract data type you can talk about what are the best possible implementations for this abstract data type that's something that's hard to do if you always mix your data structure with client code

7:12 okay with that let me show the results from the opening poll again uh people still know erase but half of you know linked lists that's uh reassuring and uh many of you have seen binary surgeries uh a quarter or so has seen binary heaps

7:39 and okay good so i was i was freaking figuring some of you must have seen the more advanced data structures as well good so as i said i won't talk about hash tables and i won't talk about these two but we'll talk about the rest and do that somewhat briefly

8:19 as a last point i want to mention that despite all these positive aspects of having the separation between abstract data types a clean interface and then implementing it sometimes an interface doesn't really help much and like in this example right you see the host coming out and than it looks like it's a not it's a nice fountain but it's really just a stone with a with a a pipe in it uh sometimes this separation and this fix this this uh rigid abstraction can also be harmful and it's occasionally useful to break it open and that's why i think it's so it's so vital that you don't only know the abstract data types and you know that there's implementations of binary search trees and all the like in in programming libraries so that you can use them it's also vital for computer scientists to know what's inside the black box so that in some cases you can break it open and and exploit that fact and get to a better solution uh with that i want to see again a little bit how well these these terms are known to you now before i start that let me double check that you can

9:47 that was the wrong one this one but you can actually answer it with several several questions several i'll wait a little bit to give a few more people a chance to vote it's a question with a lot of answers

10:53 i want to point you to a little nitpick here which of the following are examples of abstract data types okay 30-ish people is what we had for the previous questions so maybe

11:28 i'll reveal the answers so uh strictly speaking i would say adt is not an example of an abstract data type because it's just the abbreviation for abstract data types it's not an example of it but okay not so important

11:43 um let me show the answers um stack is an abstract data type we'll talk about that in a minute dec is a stack and a queue together so you can can use both ends that's an abstract data type maybe not so well known but occasionally used linked list is not an abstract data type i would say it's an implementation so it's a data structure and the same is true for binary search tree sometimes people use this a bit in interchangeably with dictionary sorted dictionaries that will come below but i would say it's a data structure q is an abstract data type yeah resizable raise the data structure that's that's right it's not an adt uh same for heap priority queue is an adt because there's um well it is according to my definition and symbol tables again that's the abstract data type that is implemented by binary search trees so that's correct okay cool um i hope the we get the the terms a little clearer or better separated in

12:59 in a minute uh let's talk about the simplest example maybe of an abstract data type the stack and as i said an abstract data type has to specify the operations that you can do and what's what's implicitly behind this is also um what is a stack a stack is a collection of objects and you can do basically three things with it you can ask what is the currently topmost element on a stack so you can return that item and top is understood as not modifying the stack you can push an item onto the stack so there's a new book entering the stack and you just put it on top what we all do that often obviously grows the stack by one item and you can pop the topmost item off what you cannot do in a safe way is like take this book out and hope that the rest will not collapse so a stack does not allow this it only allows access to the topmost element it's usually useful to also have a way to check if the stack is empty and to well to create a stack from from scratch if you start with nothing i guess that's that's known to you but just to be on the safe side

13:02 Stacks

14:23 let me ask you this little question to see if you understand that part and to make sure you're awake so you have a stack of numbers and in the picture i drew it would be one is at the top

15:03 and again i read the numbers top down so this is top down and you should do the same for the answer this is uh top down red the numbers on the stack

15:33 okay i i i see not everyone has voted but uh the result is so clear that i would say you got this and no need to waste more time on this so obviously pop does pop pop and then you do one push of the one so you read this down as one three four five all right um that was easy enough now uh let's talk briefly about linked lists um there's different ways how you can implement a stack it's an abstract data type and it doesn't say how you implement it but uh one one typical way of doing it is like this with a linked list and for that let me briefly repeat what a linked list looks like i assume you have a programming language that allows you to generate objects and these objects have fields and one can be a value

15:50 Linked Lists

16:36 and we will use this pointer it's a singly linked list that i will create it's a pointer to another element so that will be just the next element in the list so as an example take the example from before we had one which was at the top and this has a pointer to a next element and that was 3 so this points to the next element and then we had four and five

17:08 the beauty about linked lists is there's no way that there's no requirement as to where these objects are really stored they could be just arbitrarily scattered around in memory and uh this will have a null pointer because it doesn't have a new element now that's that's a link a singly linked list it has a beginning and it has an end and we can traverse it by following the pointers that's that's pretty much what a linked list can do it's a very flexible way of representing a sequence because at any point in time you can insert a new element by uh inserting a new element inside this pointer if you like pointing to the new element and from the new to the previous successor

17:54 how do you make a stack out of this um it's fairly simple you just imagine that you have these boxes stacked on top of each other and it always points to the thing the next thing below it and you have one global variable top that points to the topmost element so you can access that topmost element through this global variable and you can pop it by just setting top to the successor and then this this is essentially deleted and you can add a new item by creating a new one here setting its next pointer and then rewiring the top pointer to point to this new element that's how you do a stack based on a simply linked list in like two minutes um as most of you will have seen this this is probably a sufficient level of detail

18:57 how good is this implementation it's actually pretty good for a stack it does all operations in constant time and that's worst case constant time so there's nothing else we could really hope for and it requires a linear amount of space to be a little more precise we need n of these objects each of which has to store well the value that we're representing in the stack and a pointer so we we waste a bit of space in that we have n extra pointers but other than that the linked stack implementation is as good as we can hope for

19:47 Arrays

19:51 sometimes this requirement of having an extra pointers is is too much and um we can we can think about if we can do away with these extra pointers and uh well yes we can uh if we store the items in an array instead now uh that again is also somewhat easy we uh have an array and i just draw it upwards to make it more look like the stack of books that we had before and we stored the elements here so we had 5 4 3 1 and we have an additional variable top that tells me what is the index here so it doesn't really matter where i start with 0 but let's say it's ordered like this so top would store 3 so i would always know what is the topmost element and i can push another element in by setting top to four and adding this new element whatever it is

21:01 so far so good easy enough and well you could you can do all the other operations you can figure out how this works um the problem is what do we do if we want to pop and the stack is and the array is already used up because uh arrays need a fixed capacity that's how arrays usually work that's down to the memory management of operating systems and and programming libraries they allow you to allocate a certain chunk of memory and that's it you can't easily make it bigger than that if you need that later so what you can do is uh you can either say let's do a fixed size array and have a fixed capacity for our stack and we can never ever go above that capacity then we need that capacity of space but there's no extra pointers this is really just the space for c elements so that's good in terms of space this is um this is efficient as long as c is close to the actual number of elements that we need and all operations are a constant time again so that's also great except that this fixed capacity is a bit of a a pain in in some applications if you don't know a good bound on on the size then uh you're screwed

22:23 with this