undefined | unit 6 queue

FDS

UNIT 6

QUESTIONS

Q1 Explain queue and its applications?

Queue

Queue is additionally an abstract data type or a linear arrangement , a bit like stack arrangement , during which the primary element is inserted from one end called the REAR(also called tail), and therefore the removal of existing element takes place from the opposite end called as FRONT(also called head).

This makes queue as FIFO(First in First Out) arrangement, which suggests that element inserted first are going to be removed first.

For e.g. If you attend a ticket counter to shop for movie tickets, and are first within the queue, then you'll be the primary one to urge the tickets. Right? Same is that the case with Queue arrangement.

Data inserted first, will leave the queue first.

The process to feature a component into queue is named Enqueue.

The process of removal of a component from queue is named Dequeue.

Basic features of Queue

Queue is an ordered list of elements of comparable data types.

Queue may be a FIFO (First in First Out) structure.

Once a replacement element is inserted into the Queue, all the weather inserted before the new element within the queue must be removed, to get rid of the new element.

peek ( ) function is often want to return the worth of first element without dequeuing it.

Applications of Queue

Queue is used to manage any group of objects in an order during which the primary one coming in, also gets out first while the others await their turn, like within the following scenarios:

Serving requests on one shared resource, sort of a printer, CPU task scheduling etc.

In real world scenario, call centre phone systems uses Queues to carry people calling them in an order, until a service representative is free.

Handling of interrupts in real-time systems. The interrupts are handled within the same order as they arrive i.e. First come first served.

Implementation of Queue arrangement

Queue are often implemented using an Array, Stack or Linked List. The simplest way of implementing a queue is by using an Array.

Initially the head (FRONT) and therefore the tail (REAR) of the queue points at the primary index of the array (starting the index of array from 0). As we add elements to the queue, the tail keeps on moving ahead, always pointing to the position where subsequent element are going to be inserted, while the top remains at the primary index.

$C:\Users\Kilua Zoldyck\Pictures\s.png$

When we remove a component from Queue, we will follow two possible approaches (mentioned [A] and [B] in above diagram). In [A] approach, we remove the element at head position, then one by one shift all the opposite elements in forward position.

In approach [B] we remove the element from head position then move head to subsequent position.

In approach [A] there's an overhead of shifting the weather one position forward whenever we remove the primary element.

In approach [B] there's no such overhead, but whenever we move head one position ahead, after removal of first element, the dimensions on Queue is reduced by one space whenever

Q2 Explain queue operations?

Algorithms for basic primitive operations on queue

1. Insertion at rear

Function: QINSERT_REAR (Q, F, R, N,Y)

Given F and R tips that could the front and rear elements of a queue respectively. Queue Q consisting of N elements. This procedure inserts Y at rear end of Queue.

[Overflow]

IF R >= N

2. Then write (‘OVERFLOW’)

Return

[Increment REAR pointer]

R ←R + 1

3. [Insert element ]

Q[R] ←Y

4. [Is front pointer properly set

IF F=0

Then F ←1

Return

2. Deletion from front

Function: QDELETE_FRONT (Q, F, R)

•Given F and R tips that could the front and rear elements of a queue respectively. Queue Q consisting of N elements. This function deleted and element from front of the Queue.

[Underflow]

IF F= 0

Then write (‘UNDERFLOW’)

Return (0) (0 denotes an empty Queue)

2. [Decrement element]

Y ←Q[F]

3. [Queue empty?]

IF F=R

Then F←R←0

Else F←F+1 (increment front pointer)

4. [Return element]

Return (Y)

Q3 Explain dequeue and its operations?

Double Ended Queue

Double ended queue may be a more generalized sort of queue arrangement which allows insertion and removal of elements from both the ends, i.e , front and back.

The enqueue operation takes place only at the rear, but the dequeue operation takes place at both rear and front

$C:\Users\Kilua Zoldyck\Pictures\d1.png$

An input-restricted queue is useful when we need to remove an item from the rear of the queue

The enqueue operation takes place at both rear and front, but the dequeue operation takes place only at the front:

$C:\Users\Kilua Zoldyck\Pictures\d2.png$

An output-restricted queue is handy when we need to insert an item at the front of the queue

Implementation of Double ended Queue

Here we'll implement a double ended queue employing a circular array. It’ll have the subsequent methods:

push_back : inserts element at back

push_front : inserts element at front

pop_back : removes last element

pop_front : removes first element

get_back : returns last element

get_front : returns first element

empty : returns true if queue is empty

full : returns true if queue is full

1. Insert Elements at Front

First we check if the queue is full. If it’s not full we insert a component at front by following the given conditions

If the queue is empty then initialize front and rear to 0. Both will point to the primary element.

When one element is added- 10

$C:\Users\Kilua Zoldyck\Pictures\q1.png$

Else we decrement front and insert the element. Since we are using circular array, we've to stay in mind that if front is adequate to 0 then rather than decreasing it by 1 we make it adequate to SIZE-1.

Now insert 12 at front

$C:\Users\Kilua Zoldyck\Pictures\q2.png$

Now insert 14 at front

$C:\Users\Kilua Zoldyck\Pictures\q3.png$

2. Insert Elements at back

Again first we check if the queue is full. If it’s not full we insert a component at back by following the given conditions:

If the queue is empty then initialize front and rear to 0. Both will point to the primary element.

Else we increment rear and insert the element. Since we are using circular array, we've to stay in mind that if rear is adequate to SIZE-1 then rather than increasing it by 1 we make it adequate to 0.

Insert 21 at rear

$C:\Users\Kilua Zoldyck\Pictures\q4.png$

3. Delete First Element

In order to try to this, we first check if the queue is empty. If it’s not then delete the front element by following the given conditions :

If just one element is present we once more make front and rear adequate to -1.

Else we increment front. But we've to stay in mind that if front is adequate to SIZE-1 then rather than increasing it by 1 we make it adequate to 0.

Delete from front

$C:\Users\Kilua Zoldyck\Pictures\q4.png$ $C:\Users\Kilua Zoldyck\Pictures\q6.png$

4. Delete Last Element

In order to try to this, we again first check if the queue is empty. If its not then we delete the last element by following the given conditions :

If just one element is present we make front and rear adequate to -1.

Else we decrement rear. But we've to stay in mind that if rear is adequate to 0 then rather than decreasing it by 1 we make it adequate to SIZE-1.

$C:\Users\Kilua Zoldyck\Pictures\q7.png$

Q4 Explain operations in circular queue

Circular Queue

A more suitable method of representing simple queue which prevents an excessive use of memory is to rearrange the weather Q[1], Q[2]….,Q[n] during a circular fashion with Q[1] following Q[n], this is often called circular queue

In a typical queue arrangement re-buffering problem occurs for every dequeue operation. to unravel this problem by joining the front and rear ends of a queue to form the queue as a circular queue

Circular queue may be a linear arrangement. It follows FIFO principle.

In circular queue the last node is connected back to the primary node to form a circle.

Circular linked list fallow the primary In First Out principle.

Elements are added at the buttocks and therefore the elements are deleted at front of the queue

Both the front and therefore the rear pointers points to the start of the array

It is additionally called as “Ring buffer”.

Algorithms for basic primitive operations in Circular Queue

1. Insertion in circular queue

Function: CQINSERT (F, R, Q, N, Y)

Given F and R tips that could the front and rear elements of a circular queue respectively. Circular queue Q consisting of N elements. This procedure inserts Y at buttocks of Circular queue.

[Reset Rear Pointer]

If R = N

Then R← 1

Else R ← R + 1

2. [Overflow]

If F = R

Then Write (‘Overflow’)

Return

3. [Insert element]

Q[R] ← Y

4. [Is front pointer properly set?]

If F = 0

Then F ← 1

Return

2. Deletion in circular queue

Function CQDELETE (F, R, Q, N)

Given F and R tips that could the front and rear elements of a Circular queue respectively. Circular Queue Q consisting of N elements. This function deleted and element from front of the Circular Queue. Y is temporary pointer variable.

[Underflow?]

If F = 0

Then Write (‘UNDERFLOW’)

Return (0)

2. [Delete Element]

Y ←Q[F]

3. [Queue Empty?]

If F = R

Then F ← R ← 0

Return (Y)

4. [Increment front pointer]

If F = N

Then F ← 1

Else F ← F + 1

Return (Y)

Q5 Explain priority queue?

PriorityQueue

A priority queue may be a special quite queue during which each item features a predefined priority of service. During this queue, the enqueue operation takes place at the rear within the order of arrival of the things, while the dequeue operation takes place at the front supported the priority of the things.

In a priority queueweareabletoinsertdeleteitemsfromanypositionbasedonsomeproperty (suchas giving preference to priority oftheprocessing task).

An item with a high priority are going to be dequeued before an item with a coffee priority.

Priority Queue is an extension of queue with following properties.

Every item features a priority related to it.

An element with high priority is dequeued before a component with low priority.

If two elements have an equivalent priority, they're served consistent with their order within the queue.

$C:\Users\Kilua Zoldyck\Pictures\a.png$ Figure:-Priority Queue viewed as a single queue with insertion allowed at any position

$C:\Users\Kilua Zoldyck\Pictures\b.png$

Figure: - Priority Queue viewed as a Viewed as a set of queue

Priority Queues

Priority queue arrangement is an abstract data type that gives how to take care of a group of elements, each with an associated value called key.

There are two sorts of priority queues: a max-priority queue and a min-priority queue. In both kinds, the priority queue stores a set of elements and is usually ready to provide the foremost “extreme” element, which is that the only due to interact with the priority queue.

Operations

A max-priority queue provides the subsequent operations:

insert: add a component to the priority queue.

maxElement: return the most important element within the priority queue.

removeMaxElement: remove the most important element from the priority queue.

A max-priority queue also can provide these additional operations:

size: return the amount of elements within the priority queue.

increaseKey: updates the key of a component to a bigger value.

updatePriorities: assume the values of the keys are changed and reorder the interior state of the priority queue.

Implementations

1) Unordered array,a simple, yet inefficient implementation, as retrieving the max element would require searching the whole array.

2) Sorted array,this is not a really efficient implementation either. Inserting a replacement element requires linearly searching the array for the right position. Removing similarly requires a linear time: the remainder of the weather got to be adjusted (shifted) into correct positions.

3) Hash table,although inserting into a hash table takes constant time (given an honest hash function), finding the max element takes linear time. Therefore, this is able to be a poor choice for the underlying arrangement.

4) Heap, it seems that that a heap makes an efficient priority queue.

Q6 Explain circular queue and its advantages?

Circular Queue and its advantage

In a typical queue arrangement re-buffering problem occurs for every dequeue operation. to unravel this problem by joining the front and rear ends of a queue to form the queue as a circular queue

Circular queue may be a linear arrangement. It follows FIFO principle.

In circular queue the last node is connected back to the primary node to form a circle.

Circular linked list fallow the primary In First Out principle.

Elements are added at the buttocks and therefore the elements are deleted at front of the queue

Both the front and therefore the rear pointers points to the start of the array

It is additionally called as “Ring buffer”.

$C:\Users\Kilua Zoldyck\Pictures\r.png$

Figure: -Circular queue

Basic features of Circular Queue

1) In case of a circular queue, head pointer will always point to the front of the queue, and tail pointer will always point to the top of the queue.

2) Initially, the top and therefore the tail pointers are going to be pointing to an equivalent location, this is able to mean that the queue is empty.

$C:\Users\Kilua Zoldyck\Pictures\2.png$

3) New data is usually added to the situation pointed by the tail pointer, and once the info is added, tail pointer is incremented to point to subsequent available location.

$C:\Users\Kilua Zoldyck\Pictures\3.png$

4) In a circular queue, data isn't actually faraway from the queue. Only the top pointer is incremented by one position when dequeue is executed. Because the queue data is merely the info between head and tail, hence the info left outside isn't a neighborhood of the queue anymore, hence removed.

$C:\Users\Kilua Zoldyck\Pictures\4.png$

5) The head and therefore the tail pointer will get reinitialized to 0 whenever they reach the top of the queue.

$C:\Users\Kilua Zoldyck\Pictures\5.png$

6) Also, the top and therefore the tail pointers can cross one another. In other words, head pointers are often greater than the tail. This may happen once we dequeue the queue a few of times and therefore the tail pointer gets reinitialized upon reaching the top of the queue.

$C:\Users\Kilua Zoldyck\Pictures\6.png$

Q7 What is multiqueue and how it is implemented?

Multiple line queue

Creates flexibility. The customer has greater flexibility during a multiple-line queue because they get to pick the road during which they need to face. Providing they’re not of the jockeying nature, having the facility to settle on can make a customer happier because they’ve selected where they need to be and aren’t feeling forced to face during a single line.

Deters balking. When there's one line, serpentine or straight, long or short, a customer can feel trapped by the thought of being at the mercy of just one waiting option. Multiple-line queues maintain the illusion that there's more service available and, therefore, well worth the wait.

Implementation of k queues

Create a knowledge structure kQueues that represents k queues. Implementation of kQueues should use just one array, i.e., k queues should use an equivalent array for storing elements. Following functions must be supported by kQueues.

enqueue(int x, intqn) –> adds x to queue number ‘qn’ where qn is from 0 to k-1

dequeue(intqn) –> deletes a component from queue number ‘qn’ where qn is from 0 to k-1

Method 1 (Divide the array in slots of size n/k)

A simple thanks to implement k queues is to divide the array in k slots of size n/k each, and fix the slots for various queues, i.e., use arr[0] to arr[n/k-1] for the primary queue, and arr[n/k] to arr[2n/k-1] for queue2 where arr[] is that the array to be wont to implement two queues and size of array be n.

The problem with this method is an inefficient use of array space. An enqueue operation may end in overflow albeit there's space available in arr[]. Forinstance, consider k as 2 and array size n as 6. Let we enqueue 3 elements to first and don't enqueue anything to the second queue.

Once we enqueue the 4th element to the primary queue, there'll be overflow albeit we've space for 3 more elements within the array.

Method 2 (A space efficient implementation)

The idea is analogous to the stack post, here we'd like to use three extra arrays. In stack post, we would have liked two extra arrays, another array is required because in queues, enqueue() and dequeue() operations are done at different ends.

Following are the three extra arrays are used:

front[]: this is often of size k and stores indexes of front elements altogether queues.

rear[]: this is often of size k and stores indexes of rear elements altogether queues.

next[]: this is often of size n and stores indexes of next item for all items in array arr[].

Here arr[] is that the actual array that stores k stacks.

Together with k queues, a stack of free slots in arr[] is additionally maintained. The highest of this stack is stored during a variable ‘free’.

All entries in front[] are initialized as -1 to point that each one queues are empty

All entries next[i] are initialized as i+1 because all slots are free initially and pointing to subsequent slot. Top of the free stack, ‘free’ is initialized as 0.

Q8 Write algorithm to insert and delete elements from dequeue?

Insert Elements at Front

First we check if the queue is full. If it’s not full we insert a component at front by following the given conditions

If the queue is empty then intialize front and rear to 0. Both will point to the primary element.

When one element is added- 10

$C:\Users\Kilua Zoldyck\Pictures\q1.png$

Now insert 12 at front

$C:\Users\Kilua Zoldyck\Pictures\q2.png$

Now insert 14 at front

$C:\Users\Kilua Zoldyck\Pictures\q3.png$

2. Insert Elements at back

Again first we check if the queue is full. If it’s not full we insert a component at back by following the given conditions:

If the queue is empty then initialize front and rear to 0. Both will point to the primary element.

Insert 21 at rear

$C:\Users\Kilua Zoldyck\Pictures\q4.png$

3. Delete First Element

In order to try to this, we first check if the queue is empty. If it’s not then delete the front element by following the given conditions :

If just one element is present we once more make front and rear adequate to -1.

Else we increment front. But we've to stay in mind that if front is adequate to SIZE-1 then rather than increasing it by 1 we make it adequate to 0.

Delete from front

$C:\Users\Kilua Zoldyck\Pictures\q4.png$ $C:\Users\Kilua Zoldyck\Pictures\q6.png$

4. Delete Last Element

In order to try to this, we again first check if the queue is empty. If it’s not then we delete the last element by following the given conditions :

If just one element is present we make front and rear adequate to -1.

Else we decrement rear. But we've to stay in mind that if rear is adequate to 0 then rather than decreasing it by 1 we make it adequate to SIZE-1.

$C:\Users\Kilua Zoldyck\Pictures\q7.png$

Q9 What are the types of queues?

Queues

Queue

A linear list which allows deletion to be performed at one end of the list and insertion at the opposite end is named queue.

The information in such an inventory is processed FIFO (first in first out) of FCFS (first come first served) pattern.

Front is that the end of queue from that deletion is to be performed

Rear is that the end of queue at which new element is to be inserted

2. Circular Queue

In a typical queue arrangement re-buffering problem occurs for every dequeue operation. to unravel this problem by joining the front and rear ends of a queue to form the queue as a circular queue

Circular queue may be a linear arrangement. It follows FIFO principle.

In circular queue the last node is connected back to the primary node to form a circle.

Circular linked list fallow the primary In First Out principle.

Elements are added at the buttocks and therefore the elements are deleted at front of the queue

Both the front and therefore the rear pointers points to the start of the array

It is additionally called as “Ring buffer”.

3. Multi-queues

Studies have proven that a single-line queue resulting in multiple servers is more efficient and leads to less variation within the amount of your time customers are kept waiting.

Still, the single-line queue can appear overwhelming customers who fail to know that one longer line is really a far better bet than taking their chances with one among many lines.

4. Double Ended Queue

Double ended queue may be a more generalized sort of queue arrangement which allows insertion and removal of elements from both the ends, i.e., front and back.

The enqueue operation takes place only at the rear, but the dequeue operation takes place at both rear and front

An input-restricted queue is useful when we need to remove an item from the rear of the queue

The enqueue operation takes place at both rear and front, but the dequeue operation takes place only at the front:

An output-restricted queue is handy when we need to insert an item at the front of the queue

Q10 How queue can be used as linked list?

Queue using link list

To implement queue using linked list,

Step 1 - Include all the header files which are used in the program. And declare all the user defined functions.

Step 2 - Define a 'Node' structure with two members data and next.

Step 3 - Define two Node pointers 'front' and 'rear' and set both to NULL.

Step 4 - Implement the main method by displaying Menu of list of operations and make suitable function calls in the main method to perform user selected operation.

$C:\Users\Kilua Zoldyck\Pictures\asa.png$

1. To insert a new node into the queue...

enQueue(value) - Inserting an element into the Queue

Step 1 - Create a newNode with given value and set 'newNode→ next' to NULL.

Step 2 - Check whether queue is Empty (rear == NULL)

Step 3 - If it is Empty then, set front = newNode and rear = newNode.

Step 4 - If it is Not Empty then, set rear → next = newNode and rear = newNode.

$C:\Users\Kilua Zoldyck\Pictures\swq.png$

2. To delete a node from the queue

deQueue() - Deleting an Element from Queue

Step 1 - Check whether queue is Empty (front == NULL).

Step 2 - If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and terminate from the function

Step 3 - If it is Not Empty then, define a Node pointer 'temp' and set it to 'front'.

Step 4 - Then set 'front = front → next' and delete 'temp' (free(temp)).

$C:\Users\Kilua Zoldyck\Pictures\aqawq.png$

3. To display the elements (nodes) of a queue...

display() - Displaying the elements of Queue

Step 1 - Check whether queue is Empty (front == NULL).

Step 2 - If it is Empty then, display 'Queue is Empty!!!' and terminate the function.

Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with front.

Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same until 'temp' reaches to 'rear' (temp →next != NULL).

Step 5 - Finally! Display 'temp → data ---> ‘NULL’

$C:\Users\Kilua Zoldyck\Pictures\asa.png$

Sign Up