Data Structures and Algorithms - Old Questions
1. Define Queue as ADT. Describe its primitive operation on array implementation and linked list implementation.
10 marks
|
Asked in 2069
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).
Queue follows First-In-First-Out (FIFO) methodology, i.e. the first element inserted into the queue is the first element to be removed.
Queue as an ADT
A queue q of type T is a finite sequence of elements with the operations:
- MakeEmpty(q): To make q as an empty queue
- IsEmpty(q): To check whether the queue q is empty. Return true if q is empty, return false otherwise.
- IsFull(q): To check whether the queue q is full. Return true in q is full, return false otherwise.
- Enqueue(q, x): To insert an item x at the rear of the queue, if and only if q is not full.
- Dequeue(q): To delete an item from the front of the queue q. if and only if q is not empty.
- Traverse (q): To read entire queue that is display the content of the queue.
Thus by using a queue we can perform above operations thus a queue acts as an ADT.
Operations of queue
The operations that can be performed on the queue are as follows:
- MakeEmpty(q): To make q as an empty queue
- Enqueue(q, x): To insert an item x at the rear of the queue, this is also called by names add, insert.
- Dequeue(q): To delete an item from the front of the queue q. this is also known as Delete, Remove.
- IsFull(q): To check whether the queue q is full.
- IsEmpty(q): To check whether the queue q is empty
- Traverse (q): To read entire queue that is display the content of the queue.
E.g.
fig: Enqueue and Dequeue operations