Path: csiph.com!usenet.pasdenom.info!news.albasani.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: "Pascal J. Bourguignon" <pjb@informatimago.com>
Newsgroups: comp.lang.java.programmer,comp.programming
Subject: Re: Creating a new stack from an exisiting one.
Date: Sun, 04 Nov 2012 00:49:12 +0100
Organization: Informatimago
Lines: 127
Message-ID: <874nl6memf.fsf@informatimago.com>
References: <f6d6cbfd-8152-4d92-92b5-89a18ac989a5@tr7g2000pbc.googlegroups.com> <0.73472d82415d5353822e.20121103155132GMT.87mwyyvg57.fsf@bsb.me.uk> <b227ba50-ccbc-4da0-9f6a-31bb809f329d@ah9g2000pbd.googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: individual.net C6Cu8V2p+XCuZpaTMZY1cA3z1kmKgnZGt92dpL9EkR2pXZu/7L3M+y6mQEN6QW6DZl
Cancel-Lock: sha1:ZGIwZTJlYjRkZTk4NGU5N2E0YTFjY2Y5OTA5MzA2ZThiYTNiM2YzNw== sha1:vlFlHhl+gDS/kQlXs8Wu50NPGB0=
Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwAQMAAABtzGvEAAAABlBMVEUAAAD///+l2Z/dAAAA oElEQVR4nK3OsRHCMAwF0O8YQufUNIQRGIAja9CxSA55AxZgFO4coMgYrEDDQZWPIlNAjwq9 033pbOBPtbXuB6PKNBn5gZkhGa86Z4x2wE67O+06WxGD/HCOGR0deY3f9Ijwwt7rNGNf6Oac l/GuZTF1wFGKiYYHKSFAkjIo1b6sCYS1sVmFhhhahKQssRjRT90ITWUk6vvK3RsPGs+M1RuR mV+hO/VvFAAAAABJRU5ErkJggg==
X-Accept-Language: fr, es, en
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.4 (darwin)
Xref: csiph.com comp.lang.java.programmer:19613 comp.programming:2456

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