How can you use the link lists as queue?

Answer 1

If you already have a linked list implementation, you can use it as a queue by making a few changes:

* Add a queue() function to add a node to the end of the list * Add a dequeue() function to remove and return the first node

Answer 2

You wouldn't use an array to implement either a stack or a queue. By their nature, queues and stacks are variable length, thus are better suited to linked lists which can dynamically expand and contract.

In both cases, a singly-linked list suffices, where each element points to the next element and the last element points to NULL.

A stack is a last in, first out structure (LIFO structure), where all insertions and extractions occur at the head of the list. Therefore you only need to maintain a pointer to the head of the list.

A queue is a first in, first out structure (FIFO structure), where all insertions occur at the tail while all extractions occur at the head. Therefore you need to maintain two pointers, one at the head and one at the tail.

The head and tail pointers are required to permit constant time access to the head and tail of the list.

Priority queues are a variation on the standard queue, such that elements are prioritised. This is achieved by giving each element a weighted value and sorting by that value. Lower values have higher priority than larger values, thus you must traverse the list until you locate an element with a greater weight than the new element, and insert the new element in front of the greater element. Insertions of this type are not constant time (they are linear time), however if the number of weights is finite, the number of insertion points are also finite, therefore separate pointers can be maintained in an array thus permitting constant time access to each insertion point.