Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #935

Re: Understanding Sequential Allocation - Knuth TAoCP

Show all headers | View raw

On 2011-10-17, arnuld <sunrise@invalid.address> wrote:
>> > On Thu, 13 Oct 2011 14:06:29 +0000, Ike Naar wrote:
>
>
>> Let's re-quote your Knuth quote:
>> 
>> # Then inserting an element at the rear of the queue would be: #
>> #  R <-- R + 1;   X[R] <-- Y.
>> #
>> # Removing the front node(F points just below the front) would be: #
>> #  F <-- F + 1;   Y <-- X[F];    if F = R, then set F <-- R <-- 0.
>> 
>> so R points *to* the rear, F points *just below* the front.
>
>> So, if the queue has one element, R points to it, and F points just
>> below it.
>> 
>>      ---+---+---+---+---
>>         |   | X |   |
>>      ---+---+---+---+---
>>           ^   ^
>>           F   R
>
> I don't see any above or below in array (may be our definitions are 
> different). I see just before or after an element and array index. e.g. 
> if array has one element then R points to first element (at index 0 in a 
> C array) while F points where ? , in between index 0 and 1 ? and how its 
> feasible ?

Start with an empty queue, F = R = 0

     +---+---+---+---+---
     |   |   |   |   |
     +---+---+---+---+---
       0   1   2   3   4
      F=R

Insert an element 'A' (at the rear), R <- R+1, X[R] <- 'A'

     +---+---+---+---+---
     |   | A |   |   |
     +---+---+---+---+---
       0   1   2   3   4
       F   R

Insert an element 'B' (at the rear), R <- R+1, X[R] <- 'B'

     +---+---+---+---+---
     |   | A | B |   |
     +---+---+---+---+---
       0   1   2   3   4
       F       R

Insert an element 'C' (at the rear), R <- R+1, X[R] <- 'C'

     +---+---+---+---+---
     |   | A | B | C |
     +---+---+---+---+---
       0   1   2   3   4
       F           R

Remove the front node (the 'A'),
F <- F + 1, Y <-- X[F]; if F = R, then set F <-- R <-- 0.

     +---+---+---+---+---
     |   |   | B | C |
     +---+---+---+---+---
       0   1   2   3   4
           F       R

Insert an element 'D' (at the rear), R <- R+1, X[R] <- 'D'

     +---+---+---+---+---
     |   |   | B | C | D
     +---+---+---+---+---
       0   1   2   3   4
           F           R

Remove the front node (the 'B'),
F <- F + 1, Y <-- X[F]; if F = R, then set F <-- R <-- 0.

     +---+---+---+---+---
     |   |   |   | C | D
     +---+---+---+---+---
       0   1   2   3   4
               F       R

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Understanding Sequential Allocation - Knuth TAoCP arnuld <sunrise@invalid.address> - 2011-10-10 14:38 +0000
  Re: Understanding Sequential Allocation - Knuth TAoCP Azazel <azazel@remove.azazel.net> - 2011-10-10 10:21 -0500
    Re: Understanding Sequential Allocation - Knuth TAoCP arnuld <sunrise@invalid.address> - 2011-10-13 12:27 +0000
      Re: Understanding Sequential Allocation - Knuth TAoCP Ike Naar <ike@sverige.freeshell.org> - 2011-10-13 14:06 +0000
        Re: Understanding Sequential Allocation - Knuth TAoCP arnuld <sunrise@invalid.address> - 2011-10-17 11:48 +0000
          Re: Understanding Sequential Allocation - Knuth TAoCP Ike Naar <ike@sverige.freeshell.org> - 2011-10-17 22:28 +0000
            Re: Understanding Sequential Allocation - Knuth TAoCP "io_x" <a@b.c.invalid> - 2011-10-20 10:22 +0200
              Re: Understanding Sequential Allocation - Knuth TAoCP "io_x" <a@b.c.invalid> - 2011-10-20 14:14 +0200
  Re: Understanding Sequential Allocation - Knuth TAoCP Patricia Shanahan <pats@acm.org> - 2011-10-10 09:58 -0700
    Re: Understanding Sequential Allocation - Knuth TAoCP arnuld <sunrise@invalid.address> - 2011-10-17 11:41 +0000
  Re: Understanding Sequential Allocation - Knuth TAoCP Robin Vowels <robin.vowels@gmail.com> - 2011-10-16 17:24 -0700

csiph-web