1

I am looking at the following two functions of two operations of a queue:

Insert(Q,x)
 Q[end[Q]] <- x
 if end[Q]=length[Q] then 
    end[Q] <- 1
 else
    end[Q] <- end[Q]+1


Delete(Q)
 x <- Q[head[Q]]
 if head[Q]=length[Q] then 
    head[Q] <- 1
 else
    head[Q] <- head[Q]+1
 return x

Could you explain me the "if-else" statements??

Asaf Karagila
  • 393,674
Mary Star
  • 13,956
  • 1
    Did you mean to tag this with [tag:queueing-theory] (existing tag with 100+ questions and 14 followers) as opposed to [tag:queue] (brand new tag, no other questions and no followers)? –  Aug 28 '14 at 17:16
  • I added this tag.. – Mary Star Aug 28 '14 at 17:34

2 Answers2

1

1) As I described here, the end[Q] pointer is cyclic (works $\text{mod} \; n$ where $n$ is length[Q]), so when you get to the end of the array (end[Q]=length[Q]), you should come back to the first position of the array (end[Q] <- 1). Otherwise, you move it one step forward (end[Q] <- end[Q] + 1).

2) The queue data structure implements first-in, first-out notion. So when you delete, the first element gets deleted which is located where the head pointer points to by moving the head pointer one step forward. Thus, if we get to the end of the array (head[Q] = length[Q]), we should come back to the first position of the array (head[Q] <- 1), else move one step forward (head[Q] <- head[Q] + 1).

Community
  • 1
Ehsan M. Kermani
  • 9,228
1

Let's start with the queue: $$-\ \ -\ - \underset{\stackrel\uparrow{head}}o \underset{\stackrel\uparrow{end}}-\ -$$

Now we add an element at the end of the queue: $$-\ \ -\ - \underset{\stackrel\uparrow{head}}o\ o \underset{\stackrel\uparrow{end}}-$$ As you can see, we increment end by 1.

When we add another element at the end of the queue, we get: $$\underset{\stackrel\uparrow{end}}-\ \ -\ - \underset{\stackrel\uparrow{head}}o\ o\ \ o$$

In other words, we assign the new element where end was.

If end is at the end of the array, we need to change it to point to the beginning of the array instead of incrementing it.

Klaas van Aarsen
  • 5,908