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
When there is requirement to access records sequentially by some key value and also to access records directly by the similar key value, the collection of records may be organized

What are stacks? A stack is a data structure that organizes data similar to how one organizes a pile of coins. The new coin is always placed on the top and the oldest is on the

The controversy of RISC versus CISC never ends. Suppose that you represent an advocate for the RISC approach; write at least a one-page critic of the CISC approach showing its disa

What is Efficiency of algorithm? Efficiency of an algorithm can be precisely explained and investigated with mathematical rigor.  There are two types of algorithm efficiency

Program will demonstrate the insertion of an element at desired position /* Inserting an element into contiguous list (Linear Array) at particular position */ /* contiguous_

Q. Which sorting algorithm can be easily adaptable for singly linked lists? Explain your answer as well.        Ans: The simple Insertion sort is sim

Representation of data structure in memory is known as: Abstract data type

#questionalgorithm for implementing multiple\e queues in a single dimensional array

Sorting Algorithm A sorting algorithm is an algorithm which puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Eff

1.  Using the traditional method of CPM: a.  What activities are on the critical path? b.  What is the expected total lead time of the project? 2.  Using CCPM: a.  What