Queue Data Structure – Best Guide 2021
In everyday life, we encounter queues everywhere – a line of people waiting to buy a ticket or waiting to be served in a bank, all such lines of people are queues. The first person in line is the next one served, and when another person arrives, he/she joins the queue at the rear.
- A Queue is a chronologically ordered list.
- The difference between a stack and a queue is that, in a stack, elements are added and removed at the same end (the top), whereas in a queue, values are added at one end (the rear) and removed from the other end (the front).
Queue Definition
A Queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (the rear of the queue).
- The Queue ADT stores arbitrary objects
- Insertions and deletions follow the first-in first-out (FIFO) scheme
- Insertions are at the rear of the queue and removals are at the front of the queue.
Main Queue operations
- enqueue(object o): inserts element o at the end of the queue
- dequeue(): removes and returns the element at the front of the queue.
Auxiliary Queue operations:
- front(): returns the element at the front without removing it
- size(): returns the number of elements stored
- isEmpty(): returns a Boolean value indicating whether no elements are stored.
Exceptions:
- Attempting the execution of dequeue or front on an empty queue throws an EmptyQueueException.
Operations of Queue
The following operations can be applied to a queue
- InitQueue(Queue): creates an empty queue.
- append(Item): inserts an item to the rear of the queue.
- remove(Queue): removes an item from the front of the queue. Elements can only be added to the rear of the queue and removed from the front of the queue.
- isEmpty(Queue): returns true if the queue is empty.
Array Implementation
- data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority Queues are a subclass of Linear Lists, which maintain the First-In-First-Out order of elements. Insertion of elements is carried out at the ‘Tail‘ of the queue and deletion is carried out at the ‘Head‘ of the queue.
- A queue is an ordered by position, not by value collection of data, with the following operations defined on it:
Operations
- An array-based queue requires us to know two values a priori: the type of data contained in the queue, and the size of the array.
- The queue itself is a structure containing three elements: Data, the array of data, Head, an index that keeps track of the first element in the queue (location where data is removed from the queue), and Tail, an index that keeps track of the last element in the queue (location where elements are inserted into the queue).
The operations that can be performed in a Queue are:
Initialize: Initialize internal structure; create an empty queue.
Pseudo-Code:
Set Head to 1
Set Tail to 1
Return the Queue to the user.
Enqueue: Add new element to the tail of the queue. This operation adds a new element at
the rear end of the queue.
Pseudo-Code:
If Queue is Full (Tail = Size of Queue + 1) Then
Output ―Overflow, Queue is full, cannot Enqueue.‖
Else
Place Element in Queue (Tail)
Increment Tail (Tail = Tail + 1)
Return the queue to the user.
Dequeue : Remove an element from the head of the queue. This operation removes an element only from the front of the queue.
Pseudo-Code:
If Queue is Empty (Head = Tail) Then
Output ―Underflow, Queue is empty, cannot dequeue.‖
Else
Element: = Queue(Head);
Move all the elements from head+1 to Size of Queue one step to the left
Return Element
Applications of Queues:
- CPU Scheduler
- Round-Robin Scheduling
- Serving Requests
- Buffers
- Simulation of an Airport
Reference: