Question about queues

Question

A queue is implemented with a sequence $Q[1\ldots n]$ and two indices $\def\head{\operatorname{head}}\head[Q]$ and $\def\end{\operatorname{end}}\end[Q]$ such that the elements of the queue are the following:

$$Q[\head[Q]], Q[\head[Q]+1], \ldots , Q[\end[Q]-1]$$

Initial $\head[Q]=\end[Q]=1$

When $\head[Q]=\end[Q]+1$ the queue is complete.

Does ”Initial $\head[Q]=\end[Q]=1$” stand when there is one element in the queue?
Could you explain me what the following means?

”When $\head[Q]=\end[Q]+1$ the queue is complete.”

This is a new question. You should ask it in a separate topic. — Ehsan M. Kermani, Aug 24 '14 at 20:00

Ehsan M. Kermani · Answer 1 · 2014-08-24T18:17:32.107

3

1) When the two pointers (indices) head[Q], end[Q] are equal that means the queue is empty (which is what we want initially) and when head[Q]=end[Q]=1 that means they both point to the first element of our array to start the queue.

2) When head[Q] -1 = end[Q], the queue is full and there is no other place to put an element there. head[Q] points to the first element of the queue and end[Q] points to the first empty place that a new element can go there. Note that, the pointer end[Q] is cyclic, i.e. after Q[n] was used, it starts from the first position Q[1] of the array.

edited Aug 24 '14 at 18:17

answered Aug 24 '14 at 18:06

Ehsan M. Kermani

9,228

I got stuck right now..You said that "When the two pointers (indices) head[Q], end[Q] are equal that means the queue is empty ". But when head[Q]=end[Q]=1 why does this mean that they both point to the first element of the array ?? The pointer end[Q] shows to the first empty position, or not? Should it maybe be head[Q]=end[Q]-1 when there is one element in the queue?

Mary Star

Aug 25 '14 at 16:50

1

Because head[Q]=1 and end[Q]=1 at the same time. Yes, end[Q] shows the first empty position. When there's one element in the queue, say at position $i,$ then head[Q]=i and end[Q]=i + 1 $\text{mod} ; n$ where $n=\text{length}(Q).$ So head[Q]=end[Q] + 1 ($\text{mod} ; n$). – Ehsan M. Kermani Aug 25 '14 at 16:57

So, head[Q]=end[Q]=1 stands when there are no elements in the queue?? – Mary Star Aug 25 '14 at 17:02

1

right! that's only because head[Q]=end[Q] and note that you should start from somewhere, say at Q[1]. – Ehsan M. Kermani Aug 25 '14 at 17:11

Great!!! Thanks a lot!!! – Mary Star Aug 27 '14 at 00:30

score 1 · Accepted Answer · answered Aug 24 '14 at 20:14

1

When $head=end$ we consider the queue empty.

If there is 1 element in the queue, the queue looks like: $$-\ \ - \ - \underset{\stackrel\uparrow{head}}o \underset{\stackrel\uparrow{end}}- \ \ -$$ That means that: $$head+1 \equiv end\pmod{n}$$

At some point in time the queue might look like: $$o \underset{\stackrel\uparrow{end}}- - \underset{\stackrel\uparrow{head}}o o \ \ o$$

If we add one more element at the end, we get: $$o\ \ o \underset{\stackrel\uparrow{end}}- \underset{\stackrel\uparrow{head}}o o\ \ o$$

At this point we cannot add any more elements, because if $head=end$, that means we consider this an empty queue. In other words, the queue is full or complete when: $$end+1 \equiv head \pmod{n}$$

answered Aug 24 '14 at 20:14

Klaas van Aarsen

5,908

If there is 1 element in the queue, why does the queue look like $$-\ \ - \ - \underset{\stackrel\uparrow{head}}o \underset{\stackrel\uparrow{end}}- \ \ -$$ and not $$\underset{\stackrel\uparrow{head}}o \underset{\stackrel\uparrow{end}} - \ \ - \ - \ - \ \ -$$
?? Why isn't the first elememt at the beginning of the queue??
– Mary Star Aug 25 '14 at 16:18
1

That's because it is a queue. We add new elements at the end of the queue, and we take elements from the beginning of the queue for processing. Initially the queue looks as you suggest, but after adding and removing a couple of elements, it looks like I suggested. – Klaas van Aarsen Aug 25 '14 at 18:23
1

Ahaa!!! I understand!! Thank you for your answer!!! – Mary Star Aug 27 '14 at 00:29

Question about queues

2 Answers2

Linked