Topics: Data Structure
A queue is linear data structure in which we operate through its two ends. We insert elements through one end and delete them through the other.
The first element in a queue is the first one that’s going out. This is why queues are also known as FIFO-type structures (first in, first out).
Like lists and stacks, queues can be contiguous or linked. Queues have two special fields: a head field and a tail field:
| Head | … | Tail |
|---|
Stacks have the following operations:
- Iteration through the stack
- Element insertion (push)
- Element deletion (pop)
- Element search
Biqueue
Biqueues are a special type of queues from which we can insert/delete elements through *both *the head or the tail.
There are two types of biqueues:
- Restricted entry biqueue: this biqueue allows deletions to be carried out from any of its two ends, but insertions can only be carried out from the tail
- Restricted exit biqueue: this biqueue allows insertions from any of its two ends, but deletions can only be carried out from the tail
Priority Queue
A priority queue is a special type of queue in which every element has an integer attached to it to indicate its processing priority.
The way in which a given element is inserted or deleted is:
- The element with the highest priority is the first one processed
- Two elements with the same priority are processed according to the order in which they were inserted to the queue
- The lower the priority integer, the higher the proirity.