Functions for inserting and deleting at either of the end, Data Structure & Algorithms

Q. Develop a representation for a list where insertions and deletions can be done at either end. Such a structure is known as a Deque (Double ended queue). Write functions for inserting and deleting at either of the end.

Ans.

There are number of ways of representing dequeue in a computer. We will suppose that dequeue is maintained by a circular array DEQUE with pointer FRONT and REAR, which point to the 2 ends of dequeue. We suppose that the element extend from the left end to the right end in the array. The condition FRONT = NULL will be used to indicate that dequeue is blank.

Algorithm for inserting in dequeue is written below

Step 1:  [check overflow condition] If rear ≥  n and front = 0

Output :overflow and return"

Step 2:  [check front pointer value] If front > 0

Front = front -1

Else

Return

Step 3:  [insert element at the front end] Q[front ] = value

Step 4:  [check rear pointer value] If rear < n

Rear = rear +1

Else

Return

Step 5:  [insert element at the rear end] Q [rear] = value

Step 6:  Return

Deletion Algorithm for dequeue is given below

Step 1:  [check for underflow] If front = 0 and rear = 0

Output "underflow" and return

Step 2:  [delete element at front end] If front > 0

Value = q [front] Return [value]

Step 3:  [check queue for empty]

If front = rear

Front = rear = 0

Else

Front = front +1

Step 4:  [delete element at the rear end] If rear > 0

Value = Q [rear] Return (rear)

Step 5:  [check queue for empty] If front = rear

Front = rear = 0

Else

Rear = rear - 1

Step 6:   Return

Posted Date: 7/13/2012 2:40:17 AM | Location : United States







Related Discussions:- Functions for inserting and deleting at either of the end, Assignment Help, Ask Question on Functions for inserting and deleting at either of the end, Get Answer, Expert's Help, Functions for inserting and deleting at either of the end Discussions

Write discussion on Functions for inserting and deleting at either of the end
Your posts are moderated
Related Questions
Program segment for the deletion of any element from the queue delmq(i)  /* Delete any element from queue i */ { int i,x; if ( front[i] == rear[i]) printf("Queue is

Which sorting algorithm is best if the list is already sorted? Why? Insertion sort as there is no movement of data if the list is already sorted and complexity is of the order

Q. Enumerate number of operations possible on ordered lists and arrays.  Write procedures to insert and delete an element in to array.

Write a program that uses the radix sort to sort 1000 random digits. Print the data before and after the sort. Each sort bucket should be a linked list. At the end of the sort, the

Q. Assume that we have separated n elements in to m sorted lists. Explain how to generate a single sorted list of all n elements in time O (n log m )?

Q. Explain the technique to calculate the address of an element in an array. A  25 × 4  matrix array DATA is stored in memory in 'row-major order'. If base  address is 200 and

creation,insertion,deletion of header linked list using c.

What is an algorithm?  What are the characteristics of a good algorithm? An algorithm is "a step-by-step process for accomplishing some task'' An algorithm can be given in many

Q. The degree of a node is defined as the number of children it has. Shear show that in any binary tree, the total number of leaves is one more than the number of nodes of degree 2

RGB Model The RGB model is based on the assumption that any desired shade of colour can be obtained by mixing the correct amounts of red, green, and blue light. The exact hues