Queues

queues
a queue is an ordered collection of items which items may be deletingd at one end (collect the front of the queue) and inserted at the other end called the rear of the queue). the figure (a) illustrates a queue containing 4 elements 20, 5, 12 and 17. the number 20 is at the front of the queue and 17 is at the rear. like the stack, the queue is a list-like structure that provides restricted access to its elements.
queues operate like standing in line at a movie theater ticket counter. if nobody cheats, then newcomers go to the back of the line. the person at the front of the line is the next to be served. thus, queues release their elements in order of arrival. a queue called a “fifo” list, which stands for “first-in, first-out.”. there are two implementations for queues: the array-based queue and the linked queue.
array-based queues
the array-based queue is somewhat tricky to implement effectively. there are two types of queue: simple and circular queue.
simple queue: to illustrated the work of simple queue we take the figure bellow.

(a) the queue after the initial four numbers 20, 5, 12, and 17
have been inserted. (b) the queue after elements 20 and 5 are deletingd, following which 3, 30, and 4 are inserted.
if we insert 5 elements to queue, then we cannot insert one more new element to this queue, because of the overflow case is notified when
rear = = size -1
simple queue operations algorithms:
algorithm 1: insertq
inputs: q: array as integer, f: front pointer, r: rear pointer, n: size of queue, x: the new element
outputs: insert x to q.
begin
if ( r = n-1 ) then
write ("queue is over flow")
else
r = r + 1
q[r]=x
if ( f = -1) then
f=0
end
-
algorithm 2: deletq
inputs: q: array as integer, f: front , r: rear , n: queue size
outputs: x : the deletingd element
begin
if ((( f = -1)&&(r=-1)) || ( f>r) ) then
write ("queue is empty")
else
z = q[f]
f = f + 1
end
exercise: suppose q is a queue , the size of queue is 5. show q after all of the following operation have been completed assuming the queue is empty to start with. show how the front, rear and elements change.
q.enqueue(39)
q.enqueue(22)
item1 = q.dequeue()
q.enqueue(59)
item2 = q.dequeue()
item3 = q.dequeue()

circular queue: a more efficient queue representation is to treat the array of the queue as a circuited rather than a straight line. that means even if the last element of the array is occupied, a new value can be inserted in the first element of the array as long as that element is empty. figure bellow illustrates the work of circular queue.

front=2 front=2
rear=4 rear=0
circular queue operations algorithms:
algorithm 3: insertqc
inputs: q: array as integer, f: front pointer, r: rear pointer, n: size of queue, x: the new element
outputs: insert x to q.
begin
if (f==0 && r ==size-1)|| (r+1==f)
cout<<" the queue full"
else
{ if(r== size-1)
r=0
else
r=r+1
q[r]=x
}
if ( f = -1)
f=0
end
algorithm 4: deletingqc
inputs: q: array as integer, f: front pointer, r: rear pointer, n: size of queue
outputs: x : deletingd element from queue.
begin
if ((f = -1)&&(r=-1))
write (" queue is empty ")
else
x = q[f]
if ( f == r )
f = r = -1
else
if (f == n-1)
f = 0
else
f = f + 1
end