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
The time required to delete a node x from a doubly linked list having n nodes is O (1)

Limitation of Binary Search: - (i)  The complexity of Binary search is O (log2 n). The complexity is similar irrespective of the position of the element, even if it is not pres

Double Linked List In a doubly linked list, also known as 2 way lists, each node is separated into 3 parts. The first part is called last pointer field. It has the address of t

(a) Write (delay ) as a special form for (lambda () ) and (force ), as discussed in class. (b) Write (stream-cons x y) as a special form, as discussed in class. (c) Write

#why all the 4 operations i.e. insertion n deletion from rear end and front end is valid in input restricted DEQUE

Multilist Representation of graph

The Linked list is a chain of structures wherein each structure contains data in addition to pointer, which stores the address (link) of the next logical structure in the list.

Q. Define the terms data type and abstract data type. Comment upon the significance of both these.   Ans: We determine the total amount of memory to reserve by determining

The two famous methods for traversing are:- a) Depth first traversal b) Breadth first

Q. Describe what do you understand by the term array? How does an array vary from an ordinary variable? How are the arrays represented in the specific memory?