So with linked lists,

rather powerful data structure,

we can actually develop an implementation of

the push-down stack that actually implements

our API and meets our performance requirements.

So again, push-down stack is an idealized model of a LIFO storage mechanism.

We have an ADT that allows us to write useful Java programs that manipulates stacks,

and that's our API,

but we also have performance specifications.

The operations have to be constant time,

the memory use has to be linear in the size of a collection,

and there have to be no limits within the code on the collection size.

And if implementation doesn't meet the specs,

we say it implements some other kind of data structures,

but not a push-down stack.

So, let's take a look at how we're going to

implement it using a linked list. That's our choice.

We're going to hold the collection in a linked list,

so objects in the stack are going to be nodes in linked list,

and we're going to have just a single variable

first that points to the node within the linked list.

The instance variables and the constructor are going to support this use.

We're going to have a variable first,

which is the first thing on the linked list,

and that's going to get initialized to null.

And we're going to keep track of the size of the stack and its variable.

And we need the private class node,

and we can use generics within that class that

allow us to develop this code for stack to hold any type of data,

and then every node has a next field that is a reference to another node.

That's the code that we need for instance variables and constructor.

Our instance variables are a reference to the first node in the size of the stack.

Now, there's something that doesn't quite work,

that's not really a problem here but it'll come up later,

or might come up if you try to imitate this code in other contexts.

You can't declare an array of generics,

you need to cast.

If you need an array of items for some other more complicated thing,

you have to cast it from an array of objects and just list that for later reference.

Okay, test client.

Our test client is the same,

except now we can use

the generic stack which we didn't do for the string main thing that we had before,

that's a test client.

And so we expect it to work no matter what type of data that we put in.

We can have a test client with integers,

or whatever else in our implementation would work as well.

That's what we expect of the implementation,

so now, all that's left is the methods.

How are we going to implement the various operations?

First one is empty,

one thing we could do is just say is first null if there's no nodes in the linked list,

then the stacks empty.

Since we have N, we could also test if N equals zero as well.

That's equivalent.

Okay, how do we push a new item onto the stack?

What we're going to do is put a new node at

the beginning of the list and we looked at that code.

So that's second gets first,

first gets a new node,

first.item gets the item that we're supposed to put on

the top of the stack, first.next gets second.

That's exactly the code that we looked at for

adding a new node to the beginning of a list.

And then we increment N, because we have a new item on the stack.

That's the implementation of push.

And remember, first is our instance variable.

Pop, so what we want to do for pop,

the most recently added item to the stack is the first item on the list.

What we want to do is,

remove and return the first item on the list.

In that case we pull off first.Item, again,

this is the code that we looked at for list processing.

Say, first equals first.next and that makes first skip that first node,

and releases it for garbage collection.

And then since we removed an element from the stack,

we decrement N and then return the item.

That's the implementation of pop.

And then size is just return in as before.

It's a bit more complicated than

the one liners that we saw with the array representation,

but the significant difference is that

this implementation is going to meet our performance specification.

That's a summary, there's the instance variables,

there's the nested class for node,

those are the methods in the test client we already looked at.

Let's look at the behavior we expect.

Here's a trace showing that a new item is going on to the front of the linked list,

and then being removed from the front of the linked list.

A pop from the beginning,

and push to the beginning of the list.

And just looking at this diagram,

you can see that the space used is

just a multiple of the number of items in the stack always.

If the thing grows to be a million,

they'll be a million nodes there,

but when it's three,

there's only three nodes there,

and that's meeting the performance specification in terms of space.

And that's a trace. Now, let's benchmark this against our specifications.

It completely implements the API that we gave,

and all operations are constant time,

they were just a couple of statements to

add an item to the beginning or remove an item from the beginning.

The memory uses linear in the size of the collection,

and there's no limits within the code on the collection size.

Again, at the beginning of this lecture,

you may have thought this is a relatively simple problem, what's all the bother?

But when you think about it,

this is actually a profound step in

being able to meet performance specifications of this sort.

And as you saw,

the ability to do so is extremely important in real world applications,

like the Java Virtual Machine or PostScript,

and it's all made possible by introducing the concept of a linked data structure.

It's also possible implement the queue abstraction with a singly-linked list,

and you can see that in the book.

De-queue is the same,

en-queue a little more complicated,

and you can see that in the book.

In summary, we've got these two basic data structures that are fundamental abstractions,

they only differ in the order in which items are removed,

and they have these performance specifications that really characterize them.

You'll find implementations that claimed to be

stacks in queue that don't meet these performance specs,

and they're generally not really acceptable for industrial strength applications.

And what this points out for us,

is that linked structures are really a fundamental alternative to arrays,

that allow us to do things that we can't do just with arrays.

And in particular, we've shown in this lecture,

they enable implementations of the stack and queue of

abstractions that we couldn't meet just with arrays.

Next, we're going to talk about symbol tables,

which is a more difficult problem that uses double-linked structures again,

to meet performance specifications,

and that support a huge range of important applications.

Implementations

Computer Science: Algorithms, Theory, and Machines

Conoce a los instructores