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

Groups > comp.programming > #919

Re: Understanding Sequential Allocation - Knuth TAoCP

Show all headers | View raw

On 2011-10-13, arnuld <sunrise@invalid.address> wrote:
>> Queue (insert at R; increment R):
>> 
>>   +-+-+-+-+-+-+
>>   |1| | | | | |
>>   +-+-+-+-+-+-+
>>    F = 0
>>      R = 1
>
> I thought that when a Queue has only one element then both front and rear 
> (or head and tail) point to same element (from my practical experience of 
> writing many Queues in C). What I am missing here ?

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

Of course one can define the front and rear pointers in another
way; like in your experience, the front pointer can point
*to* the front element, and the rear pointer can point *to* the
rear element. If you follow that convention, then, indeed, for
a queue that contains one element, front and rear point to that
element.

     ---+---+---+---+---
        |   | X |   |
     ---+---+---+---+---
              ^
             F=R

Yet another convention is to let the front pointer point *to*
the front element, and let the rear pointer point *just after*
the rear element. Then the front and rear pointers are, just like
in Knuth's case, not the same for a queue that contains a
single element.

     ---+---+---+---+---
        |   | X |   |
     ---+---+---+---+---
              ^   ^
              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