Queue Data Structure – An Ultimate Guide 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).
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.
- 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.
- 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: