We'll start with the strawman implementation that's extremely simple and was actually used often in the early days of computing because it's so simple. But it points out the challenge of actually implementing the API that we set down. So this is a warmup. It's called a strawman. And we're going to simplify the specification a little bit. First of all, we're only going to implement it for one type of item, say strings. And the other thing we're going to do is to have the client provide a stack capacity in the constructor. And the rationale for doing this is that we can just use an array of strings to represent the values. So let's take a look at now the API that we're changing a little bit. So, first of all, in the constructor, we're specifying the capacity of the stack. And then we'll push a string, we pop a string. This is just to get started to look at how simple the code can be in a specific situation like this. So it’s a little different API than the one that we specified, but it'll get us looking at implementation code right away. And the whole idea is that with this, we can represent the collection with an array of strings. And once we have that decision that we're going to use that data structure, an array, then implementation of these methods becomes extremely simple. So what we're going to do is keep the items in stack in order in the array. And then N is going to be the index of the next open position in the array. And that's also the size of the stack. So it's kind of an upside down representation of the stack. The top of the stack is like later on in the array. But if you do this, then we start with what's our data type and our values are an array. And then and int, which is the size of the array. And then our constructor is, if the client gives us a capacity, we create a new array of that size. Those are the first two parts that we need to do to implement the data type. The instance variables are an array of the size N and then the constructor just creates that array. And then given that, now to implement the operations, well, let's do the test client first. And this is a test client that performs like the examples that I shared right at the beginning. What we're going to do is read strings of standard input. Well, it's not empty, we're going to take an item. If the item is a minus sign, then we'd pop and print the result of popping just like we did in our examples. Otherwise, we push, and that's the test client. So that's the example we gave at the beginning. To be or not to pop be, pop up that, pop pop pop is, gives that result just as the example that we went through. So that's a test client. You can see the constructor provides a maximum size that's taken from the command line in this case. So if we ran this with max too small, then there'd be an error. And that indicates the kind of problem you have when you start talking about capacity even with a simple test client. So that's what we expect the thing to do. It's worthwhile before going further just to thin about an amusing question. So this is the way our test client works. So if we do 6, 5, 4, 3, 2, 1, pop, pop, pop, pop, pop, it comes out 1, 2, 3, 4, 5, 6. Or if we do 1 pop, 2 pop, 3 pop, 4 pop, 5 pop, 6 comes out in order, or this more complicated would be 4, 1 pop, that brings out the 1, 3, 2 pop, pop, brings out 2, 3, 4, 5, 6 pop, pop brings out 5, 6. It comes out in sorted order. That's an interesting question. Can you always put the pops so that you can get them to come out in sorted order? The answer to that question is no. For example, if you have 5, 6, 1, there's no way that the 5 can be popped before the 6 and after the 1. Mathematicians study how many different ways are there to create strings like this where the items come out in sorted order and so forth. Even such a simple data structure can lead to fascinating mathematical questions. And a queue, this is a boring question because they always come out in the order they came in. So if they're in sorted order, it doesn't matter where the queues are. So to complete our implementation, we have to do the methods, the data-type operations. And with this data structure and the restrictions that we made, these are extremely simple. They're one liners. So what's isEmpty? That's just is N 0? What about push? Well, all we do is we take our new item, we put it in a of N, and then increment N. And that's accomplished with one line of code in Java. After the push, the new item's there, and it's been incremented by one. And for pop, we do the reverse. We decrement N and then return the item that's in that position. And then what's the size? It's just N. They're all one-liners, extremely simple to implement. And that's a full implementation of that strawman API that we gave. Constant-time one-liners and even in this simplest kind of machine language, these things are going to be only a few instructions. And so the very first computer systems that needed to use stacks to do things like evaluate arithmetic expression and functions calls would use implementations like this. That's the complete implementation, the instance variables, the constructors, the methods and the test client. And it produces the desired result. So now, here's a trace of what happens. So this is in an array of size 20. And it's following the example that we gave, but the stack is upside down. So it's a very simple computation, really. But the thing to notice about the simulation, you can see immediately why capacity is kind of a situation. There's a lot of space when the stack size is not near the capacity. And that's actually typical. A lot of times when you're processing data, you have to reserve for the worst case, the biggest capacity. But most of the time, you're operating at way under capacity. And in a typical computing application, you might have a large number of stacks in all that wasted space. That's the reason that we want to have that performance requirement that the space should be linear in the number of elements actually in the stack. So let's do a quick benchmark. What this thing implements, the strawman stack, is not really a stack. It's a fixed-capacity collection that behaves like a stack if the data fits, and that's a lot of restrictions. It does not implement the stack API, number one, because it requires the client to give capacity. And number two, it doesn't meet the performance specs. So the API says it shouldn't be an argument to the constructor but StrawStack requires the capacity. It only works for strings, so it doesn't do the generic thing, so that's okay. We know how to do that. It does get all operations done in constant-time. But it does not meet the requirement that memory use should be linear in the size of the collection. And there are limits within the code on the collection size. That's the use of max there. So StrawStack is not a stack. It does not meet the performance specs, and so we're going to have to look at some other way to meet the performance specs. And what we need is a new data structure, and that's what we're going to talk about next.
