Part V: Queue Manipulation (16 points) Assume I want to build a queue which can
ID: 3593433 • Letter: P
Question
Part V: Queue Manipulation (16 points) Assume I want to build a queue which can be implemented as either (a) standard array, (b) circular array or (c) circularly-linked list. We want to support the 2 functions of enqueue and dequeue. 1. Which approach is clearly the least efficient and why? 2. Explain, in English, the steps necessary to process the 2 functions using the circular array o- structure. 3. Explain, in English, the steps necessary to process the 2 functions using the circularly-linked list.Explanation / Answer
QUEUE:
First of all let us know what is mean by queue data structures?
Queue is a abstract data structure which has a FIFO(First In First Out) property. This means unlike stacks queue is not one ended operation. Queue has two pointers 'Front' and 'Rear'. At front end elements are inserted which means elements are enqueued and at rear end elements are removed or deleted which means elements are dequeued.
Queues can be implemented using:
i)Standard array
ii)Circular array
iii)Circular-linked list
1) The standard array approach is the least efficient to implement queues and this is because of few reasons:
a.Static in nature: The standard array's are the static data structures which means the size cannot be increased or decreased during the runtime. For example if the queue is implemented using standard array and if its size is to accomodate only 5 elements and if you want to enqueue another element into the queue then it is not possible this is because this queue is implemented using array's which size cannot be increased or decreased during the runtime.
b.Memory wastage: And another reason why it is least efficient is wastage of memory. Since arrays are static in nature then there is always a chance of wastage of memory. How much memory we want we cannot allocate during runtime. Everything is initialised at the beginnig of the program.
c. Accesing any element is very difficult and very time consuming.
2) The main steps necessary to process enqueue and dequeue operations using circular array can be explained as follows:
First of all in queue implemented using arrays we can insert(enqueue) the elements until queue becomes full. But once the queue becomes full we caanot insert the next element even if there is a space in front of queue.
a.Enqueue operation: We know that enqueue means inserting an element in the queue with the help of 'Rear' pointer and this can be done as follows:
step1: First of all both front and rear are initialised to -1 this can be written as (front==rear==-1)
step2: To insert any element in the queue it is important to check whether the queue is full
Check- ((rear==front-1) || (rear==SIZE-1 && front==0))
the above step means since all the elements is inserted at rear end then it keep on increasing and if it reaches before front end in circular array the queue is said to full. Another condition is for example queue size is 5 and since rear keep on increasing,if it reaches to SIZE-1 i.e.4 then queue is said to be full.
step3: If step-2 is true then display all elements in the queue, if it is not full then check-
(rear==SIZE-1 && front!=0)
step4: If the above condition is true then set rear=0 and insert the desired elements.
b.Dequeue operation: This means removing or deleting of elements from the queue with help of 'Front' pointer and this can be done as follows:
step1: Check whether the queue is empty or not i.e the condition to be checked is (front==-1)
step2: If the queue is empty then simply display that queue is empty and there is no matter of removing or deleting an elements from the queue. And if not then check step3.
step3: First of all check (front==rear) if it is true then set front=rear-1 else check (front==SIZE-1) if it true then set front=0 and return the element.
Time complexity of enqueue and dequeue operation is O(1).
3) The main steps necessary to process enqueue and dequeue operations using circular linked list can be explained as follows:
In this process of implementation the size of queue is dynamically created which means the size can be increased or decreased during the runtime. And also it saves memory wastage as compared to standard array implementation. And in this process the element is represented in terms of node and each node has two parts. First one is data part in which the elements are inserted or from which it is deleted and the second part is link part which is responsible for creating a link to the next nodes.
a.Enqueue operation: This function is used to insert an element in the queue and the element in queue is inserted at Rear end and this can be done as follows:
step1: Since it is a linked list representation the node is created during the runtime(dynamically) and the value is inserted into it.
step2: Next check whether the (front==NULL), if it is true then front=rear=newly created node
step3: And if the above step is found to be false then rear=newly created node and rear node contains the address of the front node.
b.Dequeue operation: This function is responsible for deleting the elements in the queue and this can be done with the help of front end. The main steps involved are:
step1: Check whether the queue is empty or not(front==NULL) because if it is empty then whats the point of deleting an element from the queue.
step2: If it is empty then display on screen stating that queue is empty or else check
front==rear
step3: If above condition is true then front=rear=NULL else increment the front by +1 in the queue and then update the address of the front in rear node and atlast return the element.
Time complexity of enqueue and dequeue operation is O(1).