0:01

Okay. Those are some basic data structures and implementations and it seem quite

Â elementary and simple but actually right away we can get to some very sophisticated

Â applications of these basic concepts and that's what we're going to consider next.

Â Now, first thing to mention is that often the kinds of data types and data

Â structures that we implement or found in a Java library. So, that's true in many

Â programming environments. So, for example stacks and queues you can find those words

Â mentioned in the Java library so there's a Java collection library and the so-called

Â List interface which is displayed here. So Java has general API for sequences of

Â items and its got things like a, append at the end, remove from the beginning, and

Â so forth. Any uses of the resizing array, so many of the principles that we consider

Â does also a, a link list interface. So, why not just use those? Why use our own

Â implementations? Well, the problem is often in such library code is kind of

Â designed by committee phenomenon that more and more operations get added and the API

Â becomes too broad or bloated. It's not a good idea to have lots and lots of, you

Â know, operations in the same API. And we'll see example in a second. The

Â problem, the real problem is that when you do that you can't know much about the

Â performance or you can't assume much about the performance. And so you can kind of

Â immediately arrive at that performance even for simple clients. So our best

Â practice that we recommend is so few that these basic data structures that we use

Â and there's so simple is to go ahead and use the implementations that we've just

Â discussed for these fundamental data structures. Maybe later, later on, after

Â 2:24

an experienced programmer who knows what he or she is doing could use some of these

Â library collections effectively. But inexperienced programmers often have

Â trouble with it. Here's a war story from students Programming assignments not that

Â long ago. So, we have an assignment where you need to generate a random open sites

Â in a percolation system. We have one student who was paying attention to what

Â we're saying and uses an array and can pick the indices into that array at random

Â check whether they're open and, and repeat. And so the array is N by N, it's

Â N^2 things and it takes about N^2 time, which is actually a linear time for this

Â application. But then we have another student who had some Java before coming to

Â us and considered himself an expert and said, well, I'm going to use linked list

Â because I could use Java's library and I don't have to worry about downloading your

Â stupid code. And so, I'll just use that one and pick an index at random and delete

Â and that program took quadratic time and poor Kenny, when trying to run his program

Â for the huge instance that we asked found out that it wasn't finishing. And the

Â reason is that the Java linked list implementation takes a linear time to find

Â an item with a given index. Not constant time like an array. And that's difficult

Â for Kenny to think about and difficult to drive that information from the

Â implementation so program is just too slow. And with the Swiss knife

Â implementation with so many operations it's hard to know whether or not the

Â particular set of operations that your client needs is efficiently implemented. So

Â our insistence in this course is that students should not use the library until

Â we've implemented it in class. At least that some indication that you understand

Â the performance characteristics. So now, let's look at some applications then of,

Â of stacks. There's the stacks are really actually fundamental underlying

Â computation because they implement , recursion and so, you use stacks often

Â everyday when you wrote, use the Back button in the Web browser, the places that

Â you've been are saved on a stack. Right now we will look at two examples. One,

Â having to deal with compiling from a programming language or interpreting into

Â an actual computation and then the other one is the PostScript language which is

Â widely used for, for printing and publishing. So, so the way the compilers

Â implement functions is using stacks. When there's a function call the whole local

Â environment is pushed and then along with the return address and then the function

Â returned is pop the return address in the local environment. So there is the stack

Â there that contains all that information and whether the function calls itself or

Â not is not relevant. The stack contains the recursion. In fact, you can always use

Â an explicit stack to make a recursive program non-recursive. So, this is so when

Â we have the GCD function, computing the greatest common denominator, greatest

Â common denominator p and q is greatest common denominator of q and p mod q and it

Â just calls itself until q gets to be zero. And as this graphic integrates, it just

Â does it by saving the information on a stack. Now a specific example that really

Â shows this off and also will illustrate the utility of being able to process

Â multiple types of data with the same code is this example is Dijkstra's two-stack

Â algorithm for arithmetic expression evaluation. So the goal is, you got an

Â arithmetic expression this is just actually like a simple stand in for a

Â program and we'll talk about that in a second but let's say, arithmetic

Â expressions. We have operands and operators and you want to evaluate it. And

Â Dijkstra's algorithm is very simple to express. You processes through the

Â expression from left to right. If you see a value, you put it, you maintain two

Â stacks and if you see a value, you put it on the value stack and if you see an

Â operator, you put on the operator stack. Left parenthesis you ignore. Right

Â parenthesis, you pop the operator and two values and push the result. Now that's a

Â lot of words let's look at a demo. So we start out with the empty value stack and

Â operator stack and we're going to move from left to right. So, and those are the

Â a top is summarize the four type of things that we could wind up with and what to do

Â so the left parenthesis we've ignored, a value we put on to the value stack. So,

Â that one goes right in to the value stack. Operator, we put on to the operator stack.

Â And plus it goes on the operator stack. Left parenthesis you ignore. It seems strange

Â to be ignoring parenthesis and we'll get back to that in a second. Value, put in

Â the value stack. Operator, put on the operating stack. Doesn't seem like we're

Â doing much except putting stuff on stacks and now, when we come to our right

Â parenthesis and that's when it gets interesting. What it says is to you have

Â the top operator and the top two values and that's what you want to do. Supply

Â that operator to those values and put the resulting value that you get back on to the

Â operation stack. So, we take off the top two things, we do the operation and then we

Â put the thing that we get onto the value stack. And that's right parenthesis. So

Â now continuing along we put a star on. Left parenthesis, we ignore. Four on, star.

Â The right goes to the value stack and now we got a lot of stuff on the stacks and we

Â got through right parenthesis and that's going to finish up the computation, take

Â the top two items off the stack and the top operator off the operator stack,

Â perform the operation, put the result back on the value stack. Another right

Â parenthesis, take the top two values off. Perform the operation. Put the value on to

Â the value stack and finally, the last right parenthesis, take the two operators

Â of the value stack, operators of the value stack, and operator of the operator stack,

Â perform the operation, put the result back on the value stack. And we're at the end

Â of the computation and that's the result. The value that arithmetic expression is

Â 101. Okay? Yup. Here's the code that implements Dijkstra's two-stack algorithm.

Â We have two different stacks. The operand stack the operator stack is string, it

Â could be characters which is just our operator. Then our value stack is doubled

Â so that's the same stack code but with generics, we're using, using two different

Â types of data. And then simply perform Dijkstra's algorithm. If we have a left

Â parenthesis... Read a new string. If we have a left parenthesis, do nothing. If we have

Â plus or times, push it. If we have a right parenthesis, then go ahead and pop the

Â operator. And if it's plus, add the result of the two values at the top of the value

Â stack and if it's a star, multiply the two values on the top of the stack and, and

Â then push the result. So and then when you're done then simply print out the

Â value on the stack and that's a fine and elegant implementation using stacks for

Â any arithmetic expression. And it's easy to extend that to handle other types of

Â things and so, why does this work? Well, when the algorithm encounters an operator,

Â say, in the inside, we got the parenthesis, operand, operator, operand, parenthesis

Â its easy to see that what its going to do inside there is put the at the top of the

Â stack whatever it is, is to put the two and three on the top of the value stack

Â and plus on the top of the operating stack and when it hits that right parenthesis,

Â it's going to perform the operation and it's going to proceed then exactly as if

Â the original input where that, where the value replaced. So, just go in from the

Â inside out for every operation enclosed within parenthesis like that it's just

Â repeat the argument that's exactly as if the original expression were (one + five)

Â twenty and then again, replacing that one, one + 100, 101. That's, that's why

Â Dijkstra's algorithm works. Actually fairly easy to understand why it works.

Â And you can go ahead and extend this algorithm to add functions like logs and

Â sines or other operators and have precedence among operators, have them

Â associate and multiple operations, and so forth. And actually that's on the road to

Â developing a compiler or a way to translate a, a program from a programming

Â language to a computation, so Dijkstra's algorithm that uses stack is

Â one way for entering and understanding of the basis of computation.

Â