Header Ads

Seo Services

Queue : Working of Enqueue, Dequeue, Circular and Priority Queues

In computer science, a queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. Use gcc compiler on Ubuntu and Turbo C Compiler on Windows to program below algorithms. Make use of the animation videos to understand the concept in a fruitful way.

Addition into a queue

procedure addq (item : items);
{add item to the queue q}
begin
    if rear=n then queuefull
    else begin
         rear :=rear+1;
         q[rear]:=item;
    end;
end;{of addq}

Deletion in a queue

procedure deleteq (var item : items);
{delete from the front of q and put into item}
begin
    if front = rear then queueempty
    else begin
         front := front+1
         item := q[front];
    end;
end; {of deleteq}



Circular Queue

1) Algorithm for checking whether the queue is full or not. 

isfull (queue *q)
{
If ((q−>rear is equals to MAXSIZE −1 AND q−>front is equals to 0) OR (q−>front is equals to q−>rear + 1 AND q−>front is not equals to 0)) return true;
Else return false;
}

2) Algorithm for inserting an element into the queue.

[QUOTE][COLOR="red"]
Insert (queue *q, item)
{
If (! isfull (queue))
{
Update q−>rear by (q−>rear + 1) % MAXSIZE;
Assign item into q−>arr [q−>rear];
}
}

3) Algorithm for checking whether the queue is empty or not.

isempty (queue *q)
{
If (q−>rear is equals to −1 AND q−>front is equals to 0) return true;
Else return false;
}

4) Algorithm for deleting an element from the queue.

Item Delete (queue *q)
{
If (! isempty (stack))
{
Assign q−>arr [q−>front] into item;
If (q−>rear is equals to q−>front)
{
Update q−>rear by −1;
Update q−>front by 0;
}
Else update q−>front by (q−>front + 1) % MAXSIZE;
}
Return item;
}

Priority Queues


Animations Courtsey: Yashwant Kanetkar Data Structures Through C.


No comments:

Powered by Blogger.