Implementation of queue by using a single linked list, Data Structure & Algorithms

Q. Perform implementation of a queue using a singly linked list L. The operations INSER and DELETE should take O (1) time.                                                                           

Ans:

Implementation of queue by using a singly linked list:

When implement a queue as a single liked list, a queue q consists of a list and two pointers, q.front and the q.rear.

inserting an element is stated below:

insert(q,x)

{

p=getnode(); info(p) = x; next(p) = null; if(q.rear == null)

q.front = p;

else

next(q.rear) = p;

q.rear = p;

}

deletion is stated below:

remove(q)

{

if(empty(q))

{

printf("queue overflow");

exit(1);

}

p=q.front; x=info(p); q.front=next(p); if(q.front == null) q.rear = null; freenode(p); return(x);

}

Posted Date: 7/10/2012 3:53:23 AM | Location : United States







Related Discussions:- Implementation of queue by using a single linked list, Assignment Help, Ask Question on Implementation of queue by using a single linked list, Get Answer, Expert's Help, Implementation of queue by using a single linked list Discussions

Write discussion on Implementation of queue by using a single linked list
Your posts are moderated
Related Questions
What is complexity of an algorithm? What is the basic relation between the time and space complexities of an algorithm? Justify your answer by giving an example.

Worst Fit method:- In this method the system always allocate a portion of the largest free block in memory. The philosophy behind this method is that by using small number of a ve

What do you mean by hash clash? Hashing is not perfect. Occasionally, a collision occurs when two different keys hash into the same hash value and are assigned to the same arra

Q. Define a method for keeping two stacks within a single linear array S in such a way that neither stack overflows until entire array is used and a whole stack is never shifted to

#What is the pointer

Q. Let us consider a queue is housed in an array in circular fashion or trend. It is required to add new items to the queue. Write down a method ENQ to achieve this also check whet



Define the Carrier set of the Symbol ADT Carrier set of the Symbol ADT is the set of all finite sequences of characters over Unicode characters set (Unicode is a standard char

Q. Prove the hypothesis that "A tree having 'm' nodes has exactly (m-1) branches".      Ans: A tree having m number of nodes has exactly (m-1) branches Proof: A root