Today, we're going to start talking about data structures, ways of organizing data within the computer to make it accomplish certain tasks more efficiently. To start, we're going to talk about two very fundamental abstract data types called stacks and queues. At first blush, they seem quite simple, but actually, they lie at the heart of many computational procedures. As with everything we do, we're going to precisely describe these abstractions with API. First, just a little review of the distinction between data types and data structures. So we know, and we've talked from the beginning, a data type is a set of values and a set of operation on those values. Some of the data types are built into Java, like int, double, or string. But most of the data types we use are not built into Java. We define them ourselves, like complex, or picture, or charge, and other examples that we have considered in this course. And we described the data types with APIs, and these are just examples that we've considered in earlier parts of this course. So, data structure is a different thing. That's about representing data within the computer and relationships among data. And you'll see in this lecture that even with a few, very simple mechanisms, we can build quite intricate data structures. Sometimes data structures are built into Java. For example, array is an example of a data structure, one-dimensional or two-dimensional that are built into Java, where we can store tables of numbers or any kind of object. But most are not, and that's what we're going to start looking at today. We're going to look at the linked list today. Next time, we're going to look at trees. They can take all different types of form. So, for every data type, you have a set of values, you have your data, and there's a design challenge, which is what data structure should we use. There's two primary resources that come into play. The first one is, how much memory is needed? And the second one is, how much time do the data type methods use given that data structure? And those are going to be inform the design decision every time we define a data type that is going to involve processing a significant amount of data. So, now let's look at the APIs for stacks and queues. And there are examples of collections, collections and abstract data type whose values are a set of items that are all of the same type. We say a multiset because they could be all equal. So, several actually, the fundamental collection entities, in particular, the stack and the queue, differed just in the detail of the specification of their operations. So, let's look at a stack. The basic operations for a stack are to add a new item to the collection. And we say, we add it at the beginning. And then, the second operation is to remove and return the item most recently added. That's the specification of what that operation should do. That's called a LIFO discipline, last-in-first-out. So we take away from the beginning of the stack operations. And then we also want to test if there's any items there, tests if the collection is empty, and we want to know the size of the collection. So, those are the basic operations that characterize a pushed out stack. A queue is very similar. The only difference is the specification of which item to remove and return. For a queue, we think of adding new items at the end and taking items from the beginning. That's called a first-in-first-out discipline. And again, we test if the collections empty, return the size of the collection. So those are very similar abstract data types. They only differ in this detail of the specification, whether we use the LIFO or a FIFO discipline to decide which item to remove and return. Now, these two data types arise naturally in countless applications, and we'll examine a few of them in just a bit. One of the key characteristics that we want to emphasize is, there's no predetermined limit on the size of the collection. From the point of view of the program, there's no limitation on how many items can go into the stack or how many items can go into the queue. And that's very important conceptually. It allows the design of code that can survive the test of time. As computers become bigger and bigger, the programs can operate with more and more data because there's no specification about the size of the collection. And we'll come back to that point in a minute. It's a subtle point, but it's a really important one that we want to emphasize in this lecture. So let's look at some examples of a stack in operation. So, we're talking about renaming operations, push and pop. Push is add an item to the collection. Pop is remove and return the item that was most recently added. So, if we push 'to', then push 'be', then we put 'be' at the top of the stack, put another one 'or', and you see the items go to the top of the stack. So, always we take the new item and put it on the top. Now we'll specify pop just by writing a minus sign. So, that says, take the item most recently added to the collection. So we remove the 'to' from the top in this case. And that's what we return, and then what's left in the stack is the other four in the order that we put them in from bottom to top. So that way, we know that when we remove one, we take it from top, right at the top. So, now put 'be' in, take that one from the top, that's 'be', then the next one is 'not'. Now if we push that, that goes to the top, and so forth. So this trace of the example of stacks, give you a good feeling of what this data structures is supposed to do. By contrast, here's what happens with the queue with the same list of operations. So, now we put the new items down at the end, and that's not in the specification. That's in the implementation of this example, but it allows us to remove and return the item least recently added. We take that one from the beginning or from the top. So, dequeue, again, indicated by the minus sign. If we remove and return item least recently added, it's going to come from the top. Then we put another 'be' on, and that goes at the end. And we remove the 'be' and so forth. Again, remove from the beginning, add to the end. That implements the operation of remove and return the item least recently added. That's what happens with a queue. So, that's the basic idea. Those data types in operation, there's one other thing that we want, is we want to be able to put any type of data on a stack or a queue. And that requires a little more effort in Java code. The way that Java deals with data structures like collection that are intended to work for any type of data is called generics or parameterized data types. And it's not that difficult to understand the code. And then if you look at our coding and use it as a template, you'll be able to write a code of this kind to yourself. The idea is to rather than using a real type name and the definition of the data type, we use a placeholder type name, and actually within angular brackets. And then, in client code, we put a real data type in for the placeholder. Let's look at how that works. We'll give some examples. For now, I just want to point forward to that kind of code so that we can specify the API. So, rather than just say we want to define what a stack is, we want to say what a stack of items is. So, inside the bracket is the, not a real type name, but a placeholder type name. We want to have a stack of items that we want to be able to substitute any type of data for item. So, the constructor creates a stack of items, and they all have to be the same type of that type item. Then our push method takes an item as parameter. And again, in client code, that will be substituted for string, or integer, or any other type of data, doesn't return anything, just adds the item to the stack. The pop takes no argument. It's just returns the item most recently pushed from the stack, and the type of that is our placeholder name item. IsEmpty returns of boolean, says whether the stack is empty or not, and size is in int, which is the number of items on the stack. That's our specification of a stack. And queue specification actually is the same except that the names are different. We call the add item to a queue method enqueue, and we call the remove or return the least recently in queue item dequeue. And again, otherwise, the definition of the API is exactly the same, differs only in name. And then we have isEmpty in size. So, those are our APIs. And we're going to look at some client code in just a second, and then we'll look at implementations. That's our specification of what these data types are. But we're going to add one other thing because it's extremely important in many applications and we've seen it already in several examples, performance matters. And what we want to do is provide guarantees on performance so that not only is our client code simple, safe, and clear, but also efficient. We don't want to have performance bugs hidden within our implementation. And somehow, we want to specify, when we're talking about what a data structure is, that it's got some performance guarantees with it. This is a little bit outside what you normally see in language specifications of libraries, but it's very important particularly for a fundamental data types like this. We'll back to this point often later on. So, for stacks and queues, we want to have the specifications. First of all, all the operations should take constant time. These are simple operations, should only take a few instructions, shouldn't waste memory. If the collections got a few items, we should only use a little bit of memory. If it has a lot of items, we should use a lot of memory, but linear in the size of the collection. We should only use a constant factor times, the number for every item in the collection, if it's not empty, because if it's empty, the size is zero. But if there's any number of items, the memory used should be about constant times the number of items. And then the other thing I already mentioned is, there shouldn't be any limits within the code on the size of a collection. As we'll see, it's kind of easy to solve this problem if you have such limits, but it's a much better design goal to say that our code can be used even way in the future when collections may turn out to be much bigger. We don't want to have to change our code to adapt to changes in technology. So, these are requirements. Again, if the client code is going to be scalable, it's going to be useful in the face of Moore's Law. Now, as I mentioned, it's typical in programming languages to say that if you implement the API, we specify the methods that we're going to use, then you have implemented the stack and queue abstraction. But we're holding our implementations to a stronger standard. We're going to say, if you don't meet those performance specs, then you do not implement the abstractions. It's not a stack if some operation takes linear time or if the many memory use is huge. It's not a queue if some operation takes more than constant time. Those are some other kind of data structures, but they're not stacks and queues. We're saying, if you want to use that name, you better not only match the API, but also meet the performance specifications. Otherwise, you're talking about some other kind of data structure.
