Re: what is a stack

thufir.hawat_at_mail.com
Date: 07/17/04 

Date: Fri, 16 Jul 2004 19:00:38 -0700

err, some errors and clarifications:

On Thu, 15 Jul 2004 thufir.hawat@mail.com wrote:

> There's FILO and FIFO, they're both implemented as a regular old array (at
> least as I learned it in FORTRAN).

the acronyms:
-------------
First
In
Last
Out

First
In
First
out

>
> ////////////////////////////begin trivia///////////////////
> FILO
> if you enter [a,b,c,d] into a FILO array and then remove the elements,
> you'll remove them as [d,c,b,a], which'd be how they were entered. this is
> a stack. Consider a stack of plates in a cafeteria, plate "a" was put on
> the stack first so it's on the bottom, and is the last one off.

push(a), push(b), push(c), push(d) would result in stack [a,b,c,d]

pop(stack) would return d
pop(stack) would return c
etc..

> FIFO
> The reverse of a stack, aka a queue. If you enter [a,b,c,d] into a queue
> you'd access them by pop(queue) which'd return an element. the element's
> be returned in order of [a,b,c,d]. Think of standing in a queue at a bank
> (as lotsa foreigners use the word queue (no offense to you foreigners
> intended)): whoever's standing in line longest get's to the teller. The
> inverse function of pop(queue) is push(element); ie push(e) would put "e"
> at the end of the queue.
>
> It get's more interesting when you use a second array to keep the place of
> the nodes, which allows you to make circular lists, or even circular
> linked lists.

uh, the above paragraph is questionable. A circular list would have the
first array [a,b,c,d] with the second array [1,2,3,0] indicating that

[a,b,c,d]
[1,2,3,0]

"a" in position 0 is followed by element 1, which is "b"
"b" in position 1 is followed by element 2, which is "c"
"c" in position 2 is followed by element 3, which is "d"
"d" in position 3 is followed by element 0, which is "a"

it's circular. I may've invented or misused some terminology, see a
textbook as others suggest :)

> In java, nowadays, it's all academic. The collections do all this
> low-level stuff behind the scenes and use a consistent API to make it
> portable.
> /////////////////////////end trivia/////////////////
>
> I think you're not really referring to stacks and queues in java per se,
> but the heap and queue's in memory or something. AFAIK this is totally
> opaque in java, so, in a sense, isn't "necesarry" to know. I think it's
> related to garbage collection, which, in general, you're not supposed to
> have to deal with. OTOH the more you know the better.
>
> HTH,
>
> Thufir Hawat
>
>

Relevant Pages

  • Re: Statement on Schildt submitted to wikipedia today
    ... using memoization and a work queue: ...     take from the front of the queue ... Neither the cache nor the work queue can be construed as a stack. ... I'm NOT saying that Higher Math is a conspiracy. ...
    (comp.lang.c.moderated)
  • Re: Only one end of a stack is dynamic, the oldest item is the last removed.
    ... your stack is huge and C.P.U. intensive, just give it its own heap; ... Only one end of a stack is dynamic, the oldest item is the last removed. ... It's commonly used to refer to a LIFO queue. ... certainly done using linked lists, ...
    (microsoft.public.vc.language)
  • Re: max buffer for send?
    ... > queue system. ... you are asking the socket stack _only_ to queue the ... >> can accept that and move on, you will be a better network developer. ...
    (microsoft.public.win32.programmer.networks)
  • Re: IEnumerable semantics
    ... >Stack, Queue oder ArrayList using the IEnumerable interface - can I ... I would however be very surprised if ArrayList returned items in any ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: what is a stack
    ... There's FILO and FIFO, they're both implemented as a regular old array (at ... Consider a stack of plates in a cafeteria, ... aka a queue. ...
    (comp.lang.java.programmer)