This course introduces the broader discipline of computer science to people having basic familiarity with Java programming. It covers the second half of our book Computer Science: An Interdisciplinary Approach (the first half is covered in our Coursera course Computer Science: Programming with a Purpose, to be released in the fall of 2018). Our intent is to demystify computation and to build awareness about the substantial intellectual underpinnings and rich history of the field of computer science. First, we introduce classic algorithms along with scientific techniques for evaluating performance, in the context of modern applications. Next, we introduce classic theoretical models that allow us to address fundamental questions about computation, such as computability, universality, and intractability. We conclude with machine architecture (including machine-language programming and its relationship to coding in Java) and logic design (including a full CPU design built from the ground up). The course emphasizes the relationships between applications programming, the theory of computation, real computers, and the field's history and evolution, including the nature of the contributions of Boole, Shannon, Turing, von Neumann, and others. All the features of this course are available for free. No certificate will be offered upon completion.
Strawman implementations
Loading...
Do curso por Princeton University
Computer Science: Algorithms, Theory, and Machines
95 classificações
Na lição
STACKS AND QUEUES
Our introduction to data structures is a careful look at the fundamental stack and queue abstractions, including performance specifications. Then we introduce the concept of linked structures and focus on their utility in developing simple, safe, clear, and efficient implementations of stacks and queues.
Conheça os instrutores
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Kevin WaynePhillip Y. Goldman '86 Senior Lecturer
Computer Science
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.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2019 Coursera Inc. Todos os direitos reservados.
