Video 3-1: Stacks and Queues

0:04 In the next unit, we'll look at some fundamental data structures that are at the basis of algorithms that then use these as a building block. And so um we we'll look at some of these uh that are rather fast-paced because they should be familiar maybe with some exceptions um of isolated parts that are a bit more advanced or where we'll do the analysis a bit more in detail than in undergrad classes other at the in the first year.

0:39 We'll start with um the simplest of these stacks and cues and resizable arrays where we'll look at the analysis um and then the other two main abstract data types priority cues and symbol tables and I'll I'll say a bit more about hashing at the end um time permitting um but not today.

1:05 Uh this is a little reminder where we come from. I don't want you to forget the models that we have behind this. Uh if I in Java write something like this, I allocate a new array and it doesn't matter too much what the type here is. Say it's a an array of pointers or references to objects. Um but it could be int. That doesn't make a big difference. What is the running time of this? And here assume that we execute Java on our word RAM. But really this is just as well applicable to um any actual machine with maybe the only objection that n isn't ever going to infinity on a physical machine.

2:34 Okay, apologies. I I forgot to click go live or it didn't register. So, live stream only started now in case someone's watching or uh they've given up by now. The recording is still there so that's not affected. Okay, my bad.

2:54 There's a few more people than seven. Anyone still thinking actively or struggling with slido? All set up on the new ed your room. Uh yeah, the word run model. you want to rewatch the videos from last week is the this machine um that we worked on where you can you have registers that you can add numbers in and you have one large uh array memory given that everything's recorded I can just point to that that was the word RAM um example program bit Maybe you remember this this kind of code listing. It's a low-level machine that has the the key property is that it works with integers only and the integers have w bits in binary and we assume that when the input size is n when I'm dealing with objects of size n w has login bits roughly theta of login which means I can I can do a few things that otherwise wouldn't be clear whether I can do them for example I can always hold a pointer to some position in the input in a single word in a single uh register.

4:17 Okay. Uh various opinions and there's a lot of uh confusing answers on purpose. So this is a bit of a trick question. Um the W is the word size, right? This is the number of bits that we have in in the one word in the word RAM.

4:44 But it doesn't matter. An array by definition has the same like one entry in the array, one cell in the array is one memory cell. So no matter how big W is, I always need constant time for one such cell to read or write or do whatever with it. Um now here it's also important that I'm I'm talking about a Java instruction because Java has this property that it wants to be memory safe which means whenever you allocate an array it goes through the array and initializes all cells to zero or null and that takes linear time. So it's uh essentially as as much time as there are cells and it needs to write them each once. Okay, that is one of the things that means some things that are theoretically possible on a word RAM and are possible in C or some other low-level languages are not possible in Java. There's a fundamentable t fundamental tension between security and and performance sometimes. And this is one such case.

5:52 Java wants to be memory safe. So you never get access to a piece of memory that somebody else might have filled with data because that might be confidential in some way. So whenever you get some piece of memory by the Java virtual machine, it's zeroed out. But that takes time. So nothing is for free. That's a a little nitpick and the question is my excuse to talk about that a little bit. I think it's worth knowing that this is a restriction in most languages, but it doesn't need to be a restriction. If you think about the word RAM, I can just pretend my array has starting position 5 million and goes to 6 million and these 1 million elements I'm now going to use. I don't need to initialize them to some specific value. If my program can tolerate that these are uninitialized that could have arbitrary initial values, I may be able to do this instruction in constant time. But then I'm on my own, so to say.

6:54 Can't be done in Java or Python. Um, sometimes sometimes a cool trick to pull off in low-level languages. Random access machine. Um, I think I've said most of these things. um already um we'll pretend we can just use s standard pseudo code and things work. Um and most of all most of the time that's that's totally fine. Just sometimes uh keep in mind that certain things if you write them as a single instruction in some higher level programming language may not translate to a constant time instruction on the lowest level. Um, Python is even more extreme in this sense that it allows many things that are built into the language. For example, um, on lists in Python, you can insert in the middle and it looks like this is a harmless little operation, but it actually needs to copy a lot of data and so it can be slow if you do it repeatedly. So that's uh that's just um a convention in the language or a trade-off of how easy is it to program and how performance uh how how transparent is the performance.

8:19 Let's look at some first data structures uh stacks and cues. I assume that you've seen these before. I'll briefly say again what it is. Uh what I care about a bit is this distinction between abstract data types and data structures. And the distinction is that an abstract data type tells you what is supposed to happen, but it doesn't tell you how it's done or how costly it is. So everything on the left is essentially uh without performance. You cannot say how fast an operation is in an abstract data type because there's no implementation behind it. Whereas a data structure is some if you want if you wish a concrete Java class that implements all of the operations. So every method is a specific algorithm and you can analyze that algorithm to determine how fast it is. Think about Java classes versus interfaces. By and large that's correct. Uh an abstract data type should include the semantics, the intended meaning of the operations, not how they're implemented, but what they are supposed to do. So maybe the Java doc is counted as part of that even though it's not a very formal language. But you know these days maybe it's a nicely worded Java do comment might be enough for an LLM to generate the code. So maybe it's not as bad as it was.

9:45 Why do we separate these things? uh data structures and also algorithms are the pinnacle of reusable software. That might be something that people care a bit less about now that it's cheaper to to generate code. But it's not just that you can take a piece of code and use the same code elsewhere and kind of profit from your testing and your diligence in writing that code once and well uh by reusing it elsewhere. It also means you're forced to think in proper abstractions. And this latter part is way more important if you generate code. If you can say concisely in a few words what you mean, including all the baggage of what that term means for generations of programmers, you're going to be power orders of magnitude faster than if you have to explain everything in detail. But you can only really make these higher level of abstractions if you would use standard terminology. Otherwise, you may have a clever idea in your head, but to express it, you have to spell it out. Then you're not faster.

10:49 The old school version is drop in replacements. I can tell you uh the interface you work your colleagues work against the interface. I've seen you and um you can uh write one implementation for the interface and their code still works if you swap out your implementation for a better one that you've maybe taken more time to develop. Uh question I was thinking about the same language, but in a way you're right. It doesn't even need to be the same language. You can have libraries uh C extensions for Python or so. Um there can be Python packages where you even swap out the language by using C extensions and the Python code that uses your package may not need to know. the same exists uh old old school uh Linux libraries are the same. They have a an interface description of how you can call functions in um a standard format and then you can swap out the binary. All of these things are essentially uh clean abstractions, clean interfaces mean you can separate separately build different parts and you can only do that if you can swap out one part. It's all all the same idea I think.

12:21 Okay. Uh, one caveat that I always like at this point to show. Uh, suppose your interface says you have uh, you have a place to get water and that's all that you can do. So you can go with your bucket and fill it with water. That's the interface abstraction. The abstract data type tells you fill water is is the operation. Now, sometimes it would be rather convenient to be able to take the hose somewhere else and fill your bucket without carrying it all the way. That may be more performant or more efficient. Uh, but if it's built like this, there may even be a long hose attached. But the abstraction means or this interface here, this stone interface means you can no longer use the more flexible version of just taking the water hose and filling your bucket elsewhere. Sometimes abstractions can be a bit of a pain or can be just not the perfect abstractions to start with. So don't treat these as written in stone.

13:23 Sometimes it's uh worth cracking them open, but only if you have a good reason. Like that's the the other side of it. Okay. Uh let's see if people remember this. uh if you've done algorithm data structures with me then um I've certainly asked you roughly a similar question.

13:48 So here's a list of things. All of these exist in some form or another and some of them are abstract data types, some are not Okay, anyone uh still busy reading the gazillion answers?

15:38 If you would ask me with my machine learning lens on, I'm not sure I can learn the dis the discrimination from the answers. Uh but there's a certain tendency for more people more correct.

15:50 Let's go through them briefly one by one. Um ADT is the abbreviation for abstract data type, but it's not an example. Uh stack is one. We'll come to that. Deck is a double-ended Q. That's also an abstract data type. link list arguably not because it's an implementation. Uh binary search tree same Q is another abstract data type and resizable array again is an implementation rather than uh some of these are a bit debatable. Uh I give you that um you can see them either way. Heap is an implementation for me and priority Q is the abstract data type. Same for this and then hasht again is is a data structure.

16:39 Okay. Um let's look at a few of these in um a little bit more detail but rather quick question. >> You used the right words which is a signal right? You said we used heaps to implement priority cues. If you can say implement X then X must be an interface. No.

17:10 So the priority Q for me is an abstract data type that has well come to the insert and extract max or something like that. And u one way to realize a priority queue is is a heap binary heap. But there's other options as well.

17:38 Oh, you um DQ is an operation, but you you write it like this. It's a very it's a good um hangman word, right? Whereas deck is the double-ended Q and this is not really a proper English word or German or anything is a port manto I guess.

17:57 So that's the operation that's the abstract data type. Yeah, good point. So stack I guess people know a stack is a stack of say objects books. You can always put a new thing on top and you can get the topmost uh off and in a in um a fully pure stack. That's all you can do. There's no way for you to access this book in the middle.

18:29 You can also check if a stack is empty and create an empty one. That's the kind of uh the minimalist version of a stack. And um one way to implement it is using a linked list. There's an implementation in some pseudo code here that is is almost Python. If you if you wish, you can almost type it up like this. If it replace procedure by fun uh by defaf, sorry. and uh add maybe a few more few more u single uh characters. So that's a good way to briefly remember what a linked list was like. Um a stack as a linked list has one pointer top that tells you where the topmost element of the stack is. And this is an object that has two fields. It has a value that's your book and then it has a pointer to the next thing on the stack below it.

19:34 And that may have another pointer to something below it. Now, of course, here I'm I'm drawing it as if these were nicely aligned in memory from top to bottom. Of course, they could be anywhere. This is just uh the address of the next object where I can find the next element on the stack. Um then if I want to find the topmost element, I just follow this pointer return the value to push a new element onto the stack. I allocate a new object with my new element point with its pointer to the previous top and then bend top to point to this new thing.

20:17 And pop is the opposite of that. I follow the pointer of the topmost and uh rewire top to point there. You've all seen this in some form or another at some point.

20:33 Nobody strongly contradicts. Um the good thing about this implementation is that in terms of big O notation, it's the best possible. It uses precisely uh space proportional to the number of elements we store and all the operations take constant time by inspection of the code and I'm not doing anything else. The only thing I rely on is a memory management system. That's the one slide where I said you remember the the car the carpet and we swept details under the rug. um a word RAM in isolation doesn't have an operating system really but any machine that we ever program on does and so a memory management system is always available. So I'm also pretending that here which means I can write things like this and it just magically happens that I get a free uh location in memory that I can use for my next node.

21:37 So, as long as I have enough memory for the new objects, I'm unlimited. There's no hardwired constant in the code that tells me a stack more than 5 million will not work. I can make this as big as the machine allows it. And uh everything is constant time for the operations. Now, you could also say uh that's kind of bad to use theta of n space as opposed to what? As opposed to just storing the values because we need one extra pointer for each element. So in a way we're doubling the space that we need. You can try to avoid this and that's what you can do with an array based implementation. Uh it's a different problem because arrays have a a fixed size. So here let's just draw this once. We'll only really need this at one point in the module. So in uh preparation for that that's that's an array unlike usual um it's drawn top to bottom. So this would be cell one 0 1 2 3 4 and so on. Normally you would say it goes left to right. But for a stack it's a it's nicer to draw it this way because then you can say um top is just an index namely four. That's a four.

23:01 uh it points or maybe three uh points to the topmost element that is used and then if you want the read that you just go to that position. If you want to add another element you increase top. If you want to pop you just decrease top. That all works perfectly fine and is way faster and more memory efficient than the previous solution unless uh you need more elements than you have allocated space for.

23:30 So if you know up front how many elements you need, then this is great and is much faster. But this argument that it needs less space is a bit of a lie because you're you're overallocating space up front and you're using that space even if you don't have the elements filled. So in a way it's not much better, but it the operations are faster. The constants are smaller than or a linked list. So in practice often worthwhile even if in in terms of bigo notation you don't see a difference.

24:07 So if if you if your array is full and you do another push um one option is you uh you give up uh you fix the capacity up front. Uh another option is what we'll see later. Then um you can increase the the stack even then. The second abstract data type for this uh first part are Q's and here's your inq from before. Inq means um you add a new person at the end and dq means the first person can go in. Um no other operations necessarily needed. Maybe you're checking for emptiness. Again, the very same tricks that work for a stack also work for Q's. If you want to have an array based version, then the way to think about it is that you see the array as a ring where you have 0 one around the uh clock and then you use modulo operations if an index would be above n and then you can have your current q sitting in a contiguous range like this.

25:16 And uh you could add a new element on this side and consume an element here without moving the elements in the middle and your queue slowly shifts around the circle. Uh that's called a ring buffer. Then um something that low-level implementations often use. But again, you can only do this with a fixed capacity.

25:45 Uh the last abstract data type is an abstraction of these two question or just stretching. >> Uh because I'm I'm always adding on this side and I'm taking elements out on this side.

26:07 Yeah, I don't want to copy the many elements in between. I need to support these two operations. Adding a new element and um removing like this is on on two ends of the queue, right? This is the front. Uh this is the the back. The front is where you enter the the shop. Uh so the front and the back keep moving because you don't want to copy the elements each time. So you can still support all of these in constant time, right?

26:46 Uh either as a linked list then you can of unbounded uh number of elements or in this ring buffer if the capacity is enough.

26:59 An abstraction of those two is sometimes useful if you don't want to specify the order in which elements are taken out. Uh that's often called a bag or just a collection in Java. Uh is anything where you can put elements in and you can get something out and you don't have a particular wish for which ones come first. Um, this actually exists as a as an interface in most languages because it happens to be convenient sometimes to say I want a thing to store other things in and I don't care what they're ordered like. Now the usual implementation of a bag is just a stack or a queue whatever is uh faster. So it doesn't really add anything on the data structure side is more a communications uh issue. You want to tell the user of your data structure here. I'm happy if you supply me with any data structure that implements a bag. It doesn't need to be anything special. Question.