Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Java (http://www.velocityreviews.com/forums/f30-java.html)
-   -   Creating a new stack from an exisiting one. (http://www.velocityreviews.com/forums/t954175-creating-a-new-stack-from-an-exisiting-one.html)

Chad 11-03-2012 02:45 PM

Creating a new stack from an exisiting one.
 
I have stack like the following..

[1, 4, 10, 20]

What I need to do is pop the top item off the stack such that it looks
like the following..

[1, 4, 10] [20]

Then, starting at [20], I need to be able to push the numbers 78 and
99 onto this stack such that the output looks like

[1, 4, 10] [20, 78, 99]

Can this be done without creating a new stack? If so how? I just need
some general idea. Here is what I came up with so far..

import java.util.*;

public class funcTest {


public static void main(String[] args) {
Stack<Integer> stack = new Stack<Integer>();
stack.add(1);
stack.add(4);
stack.add(10);
stack.add(20);

System.out.println(stack);

Object temp = stack.pop();

System.out.println(stack + " " + "["+ temp + "]");

//This part from here on down doesn't work
/*
stack = (Stack)temp;
stack.push(78);
stack.push(99);

System.out.println(stack + " " + "["+ temp + "]");
*
*/
}//end main()

}

Ben Bacarisse 11-03-2012 03:51 PM

Re: Creating a new stack from an exisiting one.
 
Chad <cdalten@gmail.com> writes:

> I have stack like the following..
>
> [1, 4, 10, 20]
>
> What I need to do is pop the top item off the stack such that it looks
> like the following..
>
> [1, 4, 10] [20]
>
> Then, starting at [20], I need to be able to push the numbers 78 and
> 99 onto this stack such that the output looks like
>
> [1, 4, 10] [20, 78, 99]
>
> Can this be done without creating a new stack? If so how? I just need
> some general idea.


You seem to be using [...] to denote a stack so what you want as the
result clearly has two stacks. That seems to suggest you must make
another one (unless there is a spare one lying around for some reason).

> Here is what I came up with so far..
>
> import java.util.*;
>
> public class funcTest {
>
>
> public static void main(String[] args) {
> Stack<Integer> stack = new Stack<Integer>();
> stack.add(1);
> stack.add(4);
> stack.add(10);
> stack.add(20);
>
> System.out.println(stack);
>
> Object temp = stack.pop();
>
> System.out.println(stack + " " + "["+ temp + "]");
>
> //This part from here on down doesn't work
> /*
> stack = (Stack)temp;
> stack.push(78);
> stack.push(99);
>
> System.out.println(stack + " " + "["+ temp + "]");
> *
> */
> }//end main()
>
> }


This just deepens the mystery.

--
Ben.

Chad 11-03-2012 04:22 PM

Re: Creating a new stack from an exisiting one.
 
On Nov 3, 8:51*am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> Chad <cdal...@gmail.com> writes:
> > I have stack like the following..

>
> > [1, 4, 10, 20]

>
> > What I need to do is pop the top item off the stack such that it looks
> > like the following..

>
> > [1, 4, 10] [20]

>
> > Then, starting at [20], I need to be able to push the numbers 78 and
> > 99 onto this stack such that the output looks like

>
> > [1, 4, 10] [20, 78, 99]

>
> > Can this be done without creating a new stack? If so how? I just need
> > some general idea.

>
> You seem to be using [...] to denote a stack so what you want as the
> result clearly has two stacks. *That seems to suggest you must make
> another one (unless there is a spare one lying around for some reason).
>
>
>
>
>
> > *Here is what I came up with so far..

>
> > import java.util.*;

>
> > public class funcTest {

>
> > * * public static void main(String[] args) {
> > * * * * Stack<Integer> stack = new Stack<Integer>();
> > * * * * stack.add(1);
> > * * * * stack.add(4);
> > * * * * stack.add(10);
> > * * * * stack.add(20);

>
> > * * * * System.out.println(stack);

>
> > * * * * Object temp = stack.pop();

>
> > * * * * System.out.println(stack + " " + "["+ temp + "]");

>
> > * * * * //This part from here on down doesn't work
> > * * * * /*
> > * * * * stack = (Stack)temp;
> > * * * * stack.push(78);
> > * * * * stack.push(99);

>
> > * * * * System.out.println(stack + " " + "["+ temp + "]");
> > * * * * **
> > * * * * **/
> > * * }//end main()

>
> > }

>
> This just deepens the mystery.
>


That what I thought. However, I don't think so. Let me elaborate. This
is part of a much much larger software project. The part is question
is the RunTimeStack module. In this module, we have one stack which is
called runStack. This is an ArrayList that is supposed to hold the
data pushed onto the stack. In other words, after I push the numbers
onto the stack, it would look something like..

[1, 4, 10, 20]

There is another stack, of type Stack, that is called framePointers.
This holds the current offset. So if I have something like f(3) in the
source code, the corresponding runTimeStack is supposed to go
something like

LIT 3 //private machine code
[1, 4, 10, 20, 3]

ARGS 1 //ditto
[1, 4, 10, 20] [3]

CALL F<<20>>
[1, 4, 10, 20] [3]



I don't see how to create the new "stack" when I'm only given one
stack to hold the data and another to hold the offsets.


markspace 11-03-2012 06:20 PM

Re: Creating a new stack from an exisiting one.
 
On 11/3/2012 9:22 AM, Chad wrote:
>
> That what I thought. However, I don't think so. Let me elaborate. This
> is part of a much much larger software project. The part is question
> is the RunTimeStack module. In this module, we have one stack which is
> called runStack. This is an ArrayList that is supposed to hold the
> data pushed onto the stack. In other words, after I push the numbers
> onto the stack, it would look something like..
>
> [1, 4, 10, 20]
>
> There is another stack, of type Stack, that is called framePointers.
> This holds the current offset. So if I have something like f(3) in the
> source code, the corresponding runTimeStack is supposed to go
> something like



Well, most of us remember our lessons from our coursework, so there's
not much chance we'll do your homework for you. Most real machine code
that I've seen only uses one stack for both local variables and the
frame pointers. I don't know where you get two stacks from.

Since your specification sounds hookey to me, I'd ask you to ask your
instructor what is really going on. Without understanding the exact
specification it's impossible to say what is really going on here.


>
> LIT 3 //private machine code
> [1, 4, 10, 20, 3]
>
> ARGS 1 //ditto
> [1, 4, 10, 20] [3]
>
> CALL F<<20>>
> [1, 4, 10, 20] [3]
>
>
>
> I don't see how to create the new "stack" when I'm only given one
> stack to hold the data and another to hold the offsets.
>



BartC 11-03-2012 06:58 PM

Re: Creating a new stack from an exisiting one.
 
"Chad" <cdalten@gmail.com> wrote in message
news:b227ba50-ccbc-4da0-9f6a-31bb809f329d@ah9g2000pbd.googlegroups.com...

> That what I thought. However, I don't think so. Let me elaborate. This
> is part of a much much larger software project. The part is question
> is the RunTimeStack module. In this module, we have one stack which is
> called runStack. This is an ArrayList that is supposed to hold the
> data pushed onto the stack. In other words, after I push the numbers
> onto the stack, it would look something like..
>
> [1, 4, 10, 20]
>
> There is another stack, of type Stack, that is called framePointers.
> This holds the current offset.


So this is some sort of language where you can have a stack of frame
pointers (presumably due to nested functions)?

(Instead of the ones I'm used to where there only one frame pointer is
visible at any time, and usually kept in a register.)

So you have two stacks; why shouldn't that be enough? (Normally only one is
used.)

>So if I have something like f(3) in the
> source code, the corresponding runTimeStack is supposed to go
> something like
>
> LIT 3 //private machine code
> [1, 4, 10, 20, 3]
>
> ARGS 1 //ditto
> [1, 4, 10, 20] [3]
>
> CALL F<<20>>
> [1, 4, 10, 20] [3]


> I don't see how to create the new "stack" when I'm only given one
> stack to hold the data and another to hold the offsets.


It's not clear what you're trying to do. You haven't shown the stack of
frame pointers.

I would guess that when F is called, it has to create some space on the data
stack (for its local data), create a new frame pointer to point to that
space, and push that frame pointer onto the frame pointer stack (or maybe it
keeps the current one off the stack).

But if you are implementing something to do with such a language, then you
need to find out a bit more about how these things are done.

(BTW what's the difference between .add and .push in your OP?)

--
Bartc


Jeff Higgins 11-03-2012 08:46 PM

Re: Creating a new stack from an exisiting one.
 
On 11/03/2012 11:51 AM, Ben Bacarisse wrote:
> Chad<cdalten@gmail.com> writes:
>> I just need some general idea.

>
> This just deepens the mystery.
>

No mystery, just eternal student Chad.


Lew 11-03-2012 11:02 PM

Re: Creating a new stack from an exisiting one.
 
Chad wrote:
> I have stack like the following..
>
> [1, 4, 10, 20]


Others have commented on the vagueness of your spec. I'll just assume things.

I assume you mean that '20' is at the top of the stack, based on your later
remarks.

> What I need to do is pop the top item off the stack such that it looks
> like the following..
>
> [1, 4, 10] [20]


By this I assume you mean stack [1, 4, 10] and item '20' in its own memory.

> Then, starting at [20], I need to be able to push the numbers 78 and
> 99 onto this stack such that the output looks like
>
> [1, 4, 10] [20, 78, 99]


So here you push first 20, then the others onto a second stack.

> Can this be done without creating a new stack? If so how? I just need


Based on what you said and my assumptions, no. The very definition of your
operations is to push '20' onto a new stack, so you have to create a new
stack onto which to push '20'.

> some general idea. Here is what I came up with so far..
>
> import java.util.*;
>
> public class funcTest {


Java naming conventions call for an initial upper-case letter in type names.

> public static void main(String[] args) {
> Stack<Integer> stack = new Stack<Integer>();
> stack.add(1);
> stack.add(4);
> stack.add(10);
> stack.add(20);
>
> System.out.println(stack);
>
> Object temp = stack.pop();


Really 'temp' should be declared 'Integer'.

> System.out.println(stack + " " + "["+ temp + "]");
>
> //This part from here on down doesn't work


And by "doesn't work", you mean ...?

> /*
> stack = (Stack)temp;


Oh, /that's/ what you mean. This violates the type system of Java.

You see, the object in 'temp' is not itself a stack. So there.


> stack.push(78);


You can't "push" onto an 'Integer'.

> stack.push(99);


> System.out.println(stack + " " + "["+ temp + "]");
> *
> */
> }//end main()


Don't make comments that contribute no information.

> }


The fundamentals of Java rest on its type system. You tried to break it and
of course you ran afoul of type enforcement.

Don't do that.

Part of your misstep was to duck the generics. Don't try to run away from
generics. Generics turns the attempt to 'push()' an 'Integer' into a compile
error instead of a production exception.

When you program in Java, take time to think about types. You want two stacks
of integers by your very problem statement.

public class DualStacker
{
public static void main(String[] args)
{
Stack<Integer> stack = new Stack<>();
stack.add(1);
stack.add(4);
stack.add(10);
stack.add(20);

System.out.println(stack);

Integer temp = stack.pop();
System.out.println(popped + " "+ temp);

Stack<Integer> spill = new Stack<>();
spill.push(temp);
spill.push(78);
spill.push(99);

System.out.println(stack + " ["+ spill + "]");
}
}

--
Lew

Pascal J. Bourguignon 11-03-2012 11:49 PM

Re: Creating a new stack from an exisiting one.
 
Chad <cdalten@gmail.com> writes:

> On Nov 3, 8:51*am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>> Chad <cdal...@gmail.com> writes:
>> > I have stack like the following..

>>
>> > [1, 4, 10, 20]

>>
>> > What I need to do is pop the top item off the stack such that it looks
>> > like the following..

>>
>> > [1, 4, 10] [20]

>>
>> > Then, starting at [20], I need to be able to push the numbers 78 and
>> > 99 onto this stack such that the output looks like

>>
>> > [1, 4, 10] [20, 78, 99]

>>
>> > Can this be done without creating a new stack? If so how? I just need
>> > some general idea.

>>
>> You seem to be using [...] to denote a stack so what you want as the
>> result clearly has two stacks. *That seems to suggest you must make
>> another one (unless there is a spare one lying around for some reason).
>>
>>
>>
>>
>>
>> > *Here is what I came up with so far..

>>
>> > import java.util.*;

>>
>> > public class funcTest {

>>
>> > * * public static void main(String[] args) {
>> > * * * * Stack<Integer> stack = new Stack<Integer>();
>> > * * * * stack.add(1);
>> > * * * * stack.add(4);
>> > * * * * stack.add(10);
>> > * * * * stack.add(20);

>>
>> > * * * * System.out.println(stack);

>>
>> > * * * * Object temp = stack.pop();

>>
>> > * * * * System.out.println(stack + " " + "["+ temp + "]");

>>
>> > * * * * //This part from here on down doesn't work
>> > * * * * /*
>> > * * * * stack = (Stack)temp;
>> > * * * * stack.push(78);
>> > * * * * stack.push(99);

>>
>> > * * * * System.out.println(stack + " " + "["+ temp + "]");
>> > * * * * **
>> > * * * * **/
>> > * * }//end main()

>>
>> > }

>>
>> This just deepens the mystery.
>>

>
> That what I thought. However, I don't think so. Let me elaborate. This
> is part of a much much larger software project. The part is question
> is the RunTimeStack module. In this module, we have one stack which is
> called runStack. This is an ArrayList that is supposed to hold the
> data pushed onto the stack. In other words, after I push the numbers
> onto the stack, it would look something like..
>
> [1, 4, 10, 20]
>
> There is another stack, of type Stack, that is called framePointers.
> This holds the current offset. So if I have something like f(3) in the
> source code, the corresponding runTimeStack is supposed to go
> something like
>
> LIT 3 //private machine code
> [1, 4, 10, 20, 3]
>
> ARGS 1 //ditto
> [1, 4, 10, 20] [3]
>
> CALL F<<20>>
> [1, 4, 10, 20] [3]
>
>
>
> I don't see how to create the new "stack" when I'm only given one
> stack to hold the data and another to hold the offsets.



Well, pure stacks have only those operations:

(empty-stack) --> stack
(push element stack) --> stack
(pop stack) --> element
(is-empty-stack? stack) --> boolean

If you are considering this kind of pure stack, then you must indeed use
two stacks.


But when implementing programming languages, we don't use pure stacks
usually. We have a data structure that's more complex, with indeed
frame pointers, and ways to refer frame members below and above frame
pointers, in addition to elements below the top of the stack.

It's more like:

(empty-stack) --> stack
(push element stack) --> stack
(pop stack) --> element
(is-empty-stack? stack) --> boolean
(push-frame stack) --> stack-frame
(pop-frame stack-frame) --> stack
(stack-ref stack-frame offset) --> element
(stack-set! stack stack-frame offset value) --> stack

You can implement that with an array and an index to the "top of stack",
and represent the stack frames as indices inside this array.


--
__Pascal Bourguignon__
http://www.informatimago.com

Ben Bacarisse 11-04-2012 12:44 AM

Re: Creating a new stack from an exisiting one.
 
Chad <cdalten@gmail.com> writes:
<snip the old description>
> That what I thought. However, I don't think so. Let me elaborate. This
> is part of a much much larger software project. The part is question
> is the RunTimeStack module. In this module, we have one stack which is
> called runStack. This is an ArrayList that is supposed to hold the
> data pushed onto the stack. In other words, after I push the numbers
> onto the stack, it would look something like..
>
> [1, 4, 10, 20]
>
> There is another stack, of type Stack, that is called framePointers.
> This holds the current offset. So if I have something like f(3) in the
> source code, the corresponding runTimeStack is supposed to go
> something like
>
> LIT 3 //private machine code
> [1, 4, 10, 20, 3]
>
> ARGS 1 //ditto
> [1, 4, 10, 20] [3]
>
> CALL F<<20>>
> [1, 4, 10, 20] [3]
>
>
> I don't see how to create the new "stack" when I'm only given one
> stack to hold the data and another to hold the offsets.


That seems to be a different question. Thank goodness I was not able
to answer the old one!

I think you are probably confusing yourself by writing []s and calling
the contents a stack. I am still not sure what you want, but the new
words "runStack" and "framePointers" and the function call example put
this in a context I understand.

Why do think a new stack is needed? The conventional thing to do is to
push the function's arguments and the record the new top of stack in the
frame pointer. Since the previous frame pointer will need to be
restored when this function exits, it is reasonable to record these
frame pointers in a stack, though some implementations will use the main
stack for these as well (often just relying on the register save/restore
mechanism). Anyway, that aside, the effect is that the 3 won't be on a
new stack, just in a portion of the main stack identified by the frame
pointer for this function call.

If function G calls function F we get a stack that looks like this at
the point that F starts to run:

][args for G | G's locals][args for F |

Now the []s don't denote stacks. Each bracketed part is a stack
frame -- a region on the main stack. The |s mark the frame pointers.
Function arguments are to the left, and locals are to the right.

To be very explicit, let's assume that your stack uses plain integer
indexes and the functions look like this

function G(a) { c = 42; F(c, a) }
function F(a, b) { ... don't care about what's in F }

and G is called like this, G(99). If 66 stack cells have already been
used, we get the following situation:

index ... 67 68 69 70 71
content ... 99 42 99 42
corresponding to ... G:a G:C F:b F:a

frame pointer stack: ... 68 71

Top of stack: 71.

The two numbers in the frame pointer stack mark the |s in the previous
schematic. The code is now ready to allocate the first local variables
in F (if any).

All this excludes any mention of the return address. Maybe that's being
handled separately.

--
Ben.

Pascal J. Bourguignon 11-04-2012 12:14 PM

Re: Creating a new stack from an exisiting one.
 
Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> I think you are probably confusing yourself by writing []s and calling
> the contents a stack. I am still not sure what you want, but the new
> words "runStack" and "framePointers" and the function call example put
> this in a context I understand.
>
> Why do think a new stack is needed? The conventional thing to do is to
> push the function's arguments and the record the new top of stack in the
> frame pointer. Since the previous frame pointer will need to be
> restored when this function exits, it is reasonable to record these
> frame pointers in a stack, though some implementations will use the main
> stack for these as well (often just relying on the register save/restore
> mechanism). Anyway, that aside, the effect is that the 3 won't be on a
> new stack, just in a portion of the main stack identified by the frame
> pointer for this function call.
>
> If function G calls function F we get a stack that looks like this at
> the point that F starts to run:
>
> ][args for G | G's locals][args for F |
>
> Now the []s don't denote stacks. Each bracketed part is a stack
> frame -- a region on the main stack. The |s mark the frame pointers.
> Function arguments are to the left, and locals are to the right.
>
> To be very explicit, let's assume that your stack uses plain integer
> indexes and the functions look like this
>
> function G(a) { c = 42; F(c, a) }
> function F(a, b) { ... don't care about what's in F }
>
> and G is called like this, G(99). If 66 stack cells have already been
> used, we get the following situation:
>
> index ... 67 68 69 70 71
> content ... 99 42 99 42
> corresponding to ... G:a G:C F:b F:a
>
> frame pointer stack: ... 68 71
>
> Top of stack: 71.
>
> The two numbers in the frame pointer stack mark the |s in the previous
> schematic. The code is now ready to allocate the first local variables
> in F (if any).
>
> All this excludes any mention of the return address. Maybe that's being
> handled separately.


Well, I don't know of any processor that uses a separate stack for the
frame pointers. See for example the instructions LINK and UNLK of the
680x0 (there are similar instructions on X86 and others). The top frame
pointer is usually kept in A6, while the stack pointer is A7=SP.

At the entry point of functions, there's an instruction:

LINK A6,#-localSpace

and at the exit of them, there are:

UNLK A6
RTN


So for functions like:

> function G(a) { c = 42; F(c, a) }
> function F(a, b) { ... don't care about what's in F }


and starting with A7=SP=0xfff0 (stacks tend to grow downward in
processors, but it makes no differences, only the offsets are
opposites):

A7: 0xfff0
A6: 0xfff8

the caller pushes 99 for the argument of G, then calls G, with a JSR G,
which pushes the return address onto the stack:

0xfff0:
0xffec: 99
0xffe8: return-address-to-caller

A7: 0xffe8
A6: 0xfff8

then G executes LINK A6,#-4 since it needs one local variable.

0xfff0:
0xffec: 99
0xffe8: return-address-to-caller
0xffe4: 0xfff8 ; old fram pointer
0xffe0: random value for c

A7: 0xffe0
A6: 0xffe4 ; G frame pointer

c:=42 This writes into the local frame at the address -4(A6):

0xfff0:
0xffec: 99
0xffe8: return-address-to-caller
0xffe4: 0xfff8 ; old fram pointer
0xffe0: 42 ; c

A7: 0xffe0
A6: 0xffe4 ; G frame pointer


F(c,a) this reads the local frame: c is in the local variables at
-4(A6), and a is in the parameters at 8(A6). The arguments are pushed
on the stack:

0xfff0:
0xffec: 99
0xffe8: return-address-to-caller
0xffe4: 0xfff8 ; old fram pointer
0xffe0: 42 ; c
0xffdc: 42
0xffd8: 99

A7: 0xffd8
A6: 0xffe4 ; G frame pointer

then F is called.

0xfff0:
0xffec: 99
0xffe8: return-address-to-caller
0xffe4: 0xfff8 ; old fram pointer
0xffe0: 42 ; c
0xffdc: 42
0xffd8: 99
0xffd4: return address into G

A7: 0xffd4
A6: 0xffe4 ; G frame pointer

So F executes LINK A6,#-n (n depending on the local storage F needs):

And so on. When F returns, it calls:

UNLK A6

which restores the stack to:\

0xfff0:
0xffec: 99
0xffe8: return-address-to-caller
0xffe4: 0xfff8 ; old fram pointer
0xffe0: 42 ; c
0xffdc: 42
0xffd8: 99
0xffd4: return address into G

A7: 0xffd4
A6: 0xffe4 ; G frame pointer


and:

RTN

which returns to G

0xfff0:
0xffec: 99
0xffe8: return-address-to-caller
0xffe4: 0xfff8 ; old fram pointer
0xffe0: 42 ; c
0xffdc: 42
0xffd8: 99

A7: 0xffd8
A6: 0xffe4 ; G frame pointer

When G returns, it executes:

UNLK A6

which restores the stack to:

0xfff0:
0xffec: 99
0xffe8: return-address-to-caller

A7: 0xffe8
A6: 0xfff8

and then:

RTN

and we're back to the caller:

0xfff0:
0xffec: 99

A7: 0xffec
A6: 0xfff8


--
__Pascal Bourguignon__
http://www.informatimago.com


All times are GMT. The time now is 09:47 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.