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
If a node in a binary tree is not containing left or right child or it is a leaf node then that absence of child node can be represented by the null pointers. The space engaged by

Ans. An algorithm for the quick sort is as follows: void quicksort ( int a[ ], int lower, int upper ) { int i ; if ( upper > lower ) { i = split ( a, lower, up

Explain about greedy technique The  greedy  method  suggests  constructing  a   solution  to  an  optimization  problem   by  a sequence of steps, every expanding a partially c

Explain the bubble sort algorithm. Answer This algorithm is used for sorting a list. It makes use of a temporary variable for swapping. It compares two numbers at an insta

Example 1:  Following are Simple sequence of statements Statement 1;  Statement 2; ... ... Statement k; The entire time can be found out through adding the times for

Explain the term - Branching There are two common ways of branching: case of ..... otherwise ...... endcase  if ..... then ..... else ..... endif   case of

What is bubble sort? Bubble Sort: The basic idea in bubble sort is to scan the array to be sorted sequentially various times. Every pass puts the largest element in its corr

write a algorithsm in c to perform push and pop operations stastic implementation using array ?

Define the term array. An array is a way to reference a series of memory locations using the same name. Each memory location is represented by an array element. An  array eleme

HEAP  A heap is described to be a binary tree with a key in every node, such that  1-All the leaves of the tree are on 2 adjacent levels. 2- All leaves on the lowest leve