Queue Data Structure
Queue Data Structure
Queue data structure is a linear data structure in which addition and deletion takes place at dofferent ends as a Rear and Front end respectively.The end at which new elements added is called rear. And from which elements are deleted is called the front. A queue is a collection of items organized in a structure with the First-In-First-Out property.
Basic Operations of Queue
- Enqueue: Insert element at end of queue.
- Dequeue: Delete the first element at the enc of queue.
- IsEmpty: Returns true if and only if queue is empty
- IsFull: Return true if the queue is full
- Peek: Return the value of the front of the queue without removing the element
Enqueue Operation
We can use the following steps to insert an element into queue.
- Step 1 − Check whether the queue is full(rear==SIZE-1)
- Step 2 − If the queue is full,then display “Queue is Full Insertion is not possible” and terminate the function.
- Step 3 − If the queue is not full, ithen ncrement rear value by one (rear++)and set queue[rear]=value
Algorithm for enqueue operation
procedure enqueue(data) if queue is full return overflow endif rear ← rear + 1 queue[rear] ← data return true end procedure
Dequeue Operation
- Step 1 − Check whether the queue is empty.(front==rear)
- Step 2 − If the queue is empty, then display “Queue is Empty.Deletion is not possible” and terminate the function.
- Step 3 − If the queue is not empty, then increment the front value by one(front++).then display queue[front]as deleted element.Then check whether both front and rear are equal(front==rear), if it True, then set both front and rear to “-1″(front=rear=-1)
Algorithm for dequeue operation
procedure dequeue if queue is empty return underflow end if data = queue[front] front ← front + 1 return true end procedure
Complexity of Queue
Data Structure | Time Complexity | Space Compleity | |||||||
---|---|---|---|---|---|---|---|---|---|
Average | Worst | Worst | |||||||
Access | Find(search) | Insertion | Deletion | Access | Search | Insertion | Deletion | ||
Queue | θ(n) | θ(n) | θ(1) | θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
Applications of Queue
- Queues are frequently used in operating system and networking software modules.
- Job-Scheduling
- Processor queue
- Network router queues of outgoing packets,etc.
- Simulate retail or bank operations such as withdrawing cash from an ATM machine.
Read more, Stack Data Structure