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
Algo rithm to Insert a Node p at the End of a Linked List is explained below Step1:   [check for space] If new1= NULL output "OVERFLOW" And exit Step2:   [Allocate fr

P os t - o r d e r T r av er sal :  This can be done by both iteratively and recursively. The iterative solution would require a modification or alteration of the in-

Comparison Techniques There are several techniques for determining the relevancy and relative position of two polygons. Not all tests may be used with all hidden-surface algori

File organisation might be described as a method of storing records in file. Also, the subsequent implications approaching these records can be accessed. Given are the factors invo

I=PR/12 numbers of years : Interest Rate up to 1 years : 5.50 Up to 5 years : 6.50 More than 5 year : 6.75 please design an algorithm based on the above information

Define about the inheritance hierarchy Languages Eiffel and D provide constructs in language for invariants and pre- and post conditions which are compiled into the code and ar

b) The user will roll two (six-sided) dices and the user will lose the game if (s)he gets a value 1 on either any of the two dices & wins otherwise. Display a message to the user w

padovan string

1. Use the Weierstrass condition, find the (Strongly) minimizing curve and the value of J min for the cases where x(1) = 0, x(2) = 3. 2. The system = x 1 + 2u; where