A queue is an ordered list in which all insertions take place at one end called the rear end, while all deletions take place at the other end called the front end. A queue is a pile in which items are added an one end and removed from the other. In this respect, a queue is like the line of customers waiting to be served by a bank teller.
As customers arrive, they join the end of the queue while the teller serves the customer at the head of the queue. 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 an element is added, all elements that were added before have to be removed before the new element can be invoked.
A minimal set of useful operations on queue includes the following.
Create ( ) :- Q;
Insertion (Q, e) :- updated Q;
Deletion (Q) :- Q, e;
Isfull (Q) :- Boolean;
Isempty (Q) :- Boolean;
Front (Q) :- e;
Back (Q);
Destroy (Q);
Following are the algorithms for some functions of queue.
Algorithm: Create
Output: Q, Queue created
Method:
Declare Q[SIZE] //Array with size=SIZE
Declare and Initialize F=0, R=0
//Front and Rear pointers to keep track of the front element and the rear element respectively
Algorithm ends
Algorithm: Isempty
Input: Q, Queue
Output: Boolean
Method:
If (F==0)
Return (yes)
Else
Return (no)
If end
Algorithm ends
Algorithm: Isfull
Input: Q, Queue
Output: Boolean
Method:
If (R==SIZE)
Return (yes)
Else
Return (no)
If end
Algorithm ends
Algorithm: Front
Input: Q, Queue
Output: element in the front
Method:
If (Isempty (Q))
Print 'no front element'
Else
Return (Q[F])
If end
Algorithm ends
Algorithm: Rear
Input: Q, Queue
Output: element in the rear
Method:
If (Isempty (Q))
Print 'no back element'
Else
Return (Q[R])
If end
Algorithm ends
Algorithm: Insertion
Input: (1) Q, Queue; (2) e, element to be inserted; (3) SIZE, size of the Queue;
(4) F, the front pointer; (5) R, the rear pointer
Output: (1) Q, updated; (2) F, updated; (3) R, updated
Method:
If (Isfull (Q)) then
Print ('overflow')
Else
R=R+1;
Q[R]=e
If (F==0)
F=1;
If end
If end
Algorithm ends
Algorithm: Deletion
Input: (1) Q, Queue; (2) SIZE, size of the Queue; (3) F, the front pointer; (4) R, the rear pointer
Output: (1) Q, updated; (2) F, updated; (3) R, updated; (4) e, element if deleted;
Method:
If (Isempty (Q)) then
Print ('Queue is empty')
Else
e = Q[F]
If (F==R)
F=R=0;
Else
F=F+1;
If end
If end
Algorithm ends
However, the linear queue makes less utilization of memory i.e., the 'return (isfull (Q)) = yes' does not necessarily imply that there are n elements in the queue. This can be overcome by the using an alternate queue called the circular queue.