Thursday, October 06, 2005

Queue

Two mark Questions:

1) Define Queue.
A queue is an ordered collection of items from which items may be inserted at one end called rear end and into which items may be deleted at the other end called the front end.
2) Why queue is called FIFO list?
In a queue, the first element inserted at rear end will be the first element to be deleted at front end. So, queue is called First-in First-out list.

3) What are the difference between Stack and Queue?
Stack: The basic operations like Push and Pop can be done at only one end called top of stack.
Queue: The insertion can be done at rear end and deletion at front end.
Stack: The last element inserted will be the first to be deleted. Hence stack is LIFO list.
Queue: The First element inserted will be the first to be deleted. Hence, Queue is FIFO list.

4) What are the basic operations that could be performed on a Queue?
i) Insertion – insert(q,x) inserts x at the rear end.
ii) Removal – x=remove(q) remove the element in front end.
iii) Empty(q) – Checks whether queue has any elements or not.

5) What are the limitations of linear queue? How they can be rectified?
When an element is removed from linear queue, the location remains unused. Even if the queue is empty, new elements cannot be inserted. To avoid this, consider queue as a circle, having the first element immediately following the last element.

6) Define Priority Queue.
Priority queue is a data structure in which the intrinsic ordering of the elements determine the results of the basic operations like insertion and removal.

7) What are the two types of priority queues? Briefly explain.
Two types of priority queues are,
i) Ascending priority queue – In this queue, the items can be inserted arbitrarily and only the smallest item will be removed.
ii) Descending priority queue- This allows insertion of items arbitrarily, and only the maximum element from queue will be removed first.
8) What is the difference between queue and priority queue?
In queue the elements can be inserted only at rear end and can be removed only at front end. But in priority queue, elements can be arbitrarily inserted. But the complete queue is searched for removal of high priority element.

9) What are the limitations in priority queue? How it could be rectified?
Deletion of elements make a location empty. The search of items include the empty spaces too. This takes more time. To avoid this, use an empty indicator or shift elements forward when each element is deleted. We can also maintain priority queue as an array of ordered elements, to avoid risk in searching.

Other questions:
1) Define queue and explain the basic operations in Queue with algorithm(8)
2) Write a C program to create queue and to implement its basic operations using array(16)
3) Explain about priority queue (8)

Works for you….
1) Write a C program to implement the basic operations on Circular queue.
2) Define Deque. Write the algorithm for input restricted deque and output restricted deque.

3 comments:

Unknown said...

Well

SHRUTI SARKAR said...

Thanks for writing this article, great job. It really helped me in preparing for semester end exams. 😊

nikkisa889 said...

There are certainly quite a lot of particulars like that to take into consideration. That may be a great level to carry up. I provide the thoughts above as general inspiration but clearly there are questions just like the one you deliver up the place an important thing will be working in honest good faith. I don?t know if greatest practices have emerged around things like that, however I am certain that your job is clearly recognized as a fair game. Both girls and boys really feel the affect of only a second’s pleasure, for the remainder of their lives. casino real money