0
Describe why it is a bad idea to implement a link list version a queue which used the head of the list as the rear of the queue?
Wiki User
∙ 15y ago
It isn't. In fact it is a very good idea. Since the list is circular, you need only maintain a reference to the tail (rather than the head), because the tail provides constant time access to both the head and the tail. In this way you get constant time insertions at the tail and constant time extractions at the head via a single reference -- exactly what you want from a queue. If the list were not circular, you would need two references, one to the head and one to the tail. That's a waste of memory when the tail has an otherwise redundant link that's always null. Point it at the head and refer to the tail instead of the head and you save memory.
Wiki User
∙ 9y ago
Wiki User
∙ 15y agoYou will have to traverse the entire list every time you dequeue an element.
Add your answer:
Earn +20 pts
How do you implement queue using singly linked list?
Queues are a first in first out structure (FIFO). This means all extractions occur at the head of the list and all insertions occur at the tail. This requires that you maintain pointers to the head and tail node to allow constant time insertion and extraction of nodes. The nodes themselves are singly linked, each pointing to the next node. The tail node always points to NULL until a new node is insert, which the tail points to. The new node then becomes the tail. When extracting a head node, its next node (which may be NULL if it is also the last node) becomes the new head of the list. If the head is NULL, the tail is also set to NULL.
Implement a queue using a singly linked list l the operations insert and delete should still take o1time?
Suppose we have a Queue as follows: E -> D -> C -> B We maintain a head pointer to E and a tail pointer to B. To add an element, we make a new queue item (say A), we set B->next = A, and set tail = A. To delete an element, we let a temp pointer to the head (say tempHead = head), set head = E->next and deallocate tempHead.
What is queue in c plus plus?
A queue is a FIFO data structure. The best way to implement this is to use two pointers, one to track the head and one to track the tail. During a push operation, the tail pointer will advance one spot as the data is entered into the list. During a pop operation, the head pointer will advance one spot as data is removed. When the two pointers are pointing to the same space, the queue is empty.
What is the difference between linear and circular queue?
What is the difference between linear and circular queue? In: http://wiki.answers.com/Q/FAQ/2545-37 [Edit categories]The Queue by Default is Linear, it would be termed as Circular if the Last Element of the Queue pointsto the first element of the List
Does a queue crawl through memory in the direction of its head or its tail?
A queue crawls through memory in the direction of its tail. This answer assumes that you push elements at the head and that you pop elements at the tail. This means that the set of active elements will migrate in memory towards the tail. It is also possible that the queue be circular, in which case the elements would still follow the tail, but that tail might jump back towards the initial head from time to time.
How do you implement queue using singly linked list?
Queues are a first in first out structure (FIFO). This means all extractions occur at the head of the list and all insertions occur at the tail. This requires that you maintain pointers to the head and tail node to allow constant time insertion and extraction of nodes. The nodes themselves are singly linked, each pointing to the next node. The tail node always points to NULL until a new node is insert, which the tail points to. The new node then becomes the tail. When extracting a head node, its next node (which may be NULL if it is also the last node) becomes the new head of the list. If the head is NULL, the tail is also set to NULL.
Implement a queue using a singly linked list l the operations insert and delete should still take o1time?
Suppose we have a Queue as follows: E -> D -> C -> B We maintain a head pointer to E and a tail pointer to B. To add an element, we make a new queue item (say A), we set B->next = A, and set tail = A. To delete an element, we let a temp pointer to the head (say tempHead = head), set head = E->next and deallocate tempHead.
How do you implement an ordinary queue in C?
An ordinary queue is a first-in, first-out structure -- analogous with a queue of people waiting to be served. The simplest implementation employs a singly-linked circular list. This is like an ordinary singly-linked list, but the tail node points "down" to the head node rather than to NULL. By keeping track of the tail node (rather than the head node), we gain constant-time access to both the head and the tail through a single pointer. The basic implementation details of the push and pop methods are as follows: void push (Node* n) { if (tail==NULL) { // the queue is empty n->next = n; // the new node becomes the head (point to self) } else { // the queue has one or more nodes n->next = tail->next; // point to the current head of queue } tail = n; // the new node becomes the tail } void pop () { if (tail==NULL) return; { // can't pop an empty queue Node* head = tail->next; // temporarily point to the current head if (head == tail) { // special case: a queue of 1 node (tail points to self) free (head); tail = NULL; // the queue is now empty } else { // general case: a queue of 2 or more nodes tail->next = head->next; // set the new head free (head); // release the old head } }
What is a queue computer data structure?
A queue is a data structure that allows adding elements at one end (the tail of the queue), and removing them from the other end (the head).Adding at the tail is sometimes called enqueueing, and removing from the head is dequeueing.Inserting or removing elements at other places is not permitted.There may also be operations to examine the element at the head of the queue without removing it (peeking), and to find out how many elements there are in the queue.
What is queue in c plus plus?
A queue is a FIFO data structure. The best way to implement this is to use two pointers, one to track the head and one to track the tail. During a push operation, the tail pointer will advance one spot as the data is entered into the list. During a pop operation, the head pointer will advance one spot as data is removed. When the two pointers are pointing to the same space, the queue is empty.
How the singly Linked List related with Circular Linked List?
With a singly linked list you will typically maintain a pointer to the head node and perform all insertions and extractions at the head because it is the only node you have constant time access to. If you need to insert at the tail node as well then you must maintain a separate pointer to the tail. You would typically do this to implement a queue (first in, first out), where all insertions occur at the tail and all extractions at the head. But with a circular linked list, the tail node points to the head node thus you no longer need to maintain a separate pointer to the head in order to implement a queue, you only need to maintain a pointer to the tail.
Explain how circular queue differs from linear queue?
Both linear and circular queues are constructed from nodes: struct node { T data; // the node's value (of type T) node* next; // refers to the next node in the sequence }; To implement a queue efficiently, we need to keep track of both the front and back of the queue. This is because all insertions occur at the back of the queue while all extractions occur at the front of the queue, and both operations must be performed in constant time. struct queue { node* head; // refers to the front of the queue node* tail; // refers to the back of the queue }; Initially, the queue is empty, so both the head and tail must be set to NULL. We use the following function to insert some data at the back of the queue: node* push (queue* q, T value) { node* n = malloc (sizeof (node)); n->data = value; n->next = NULL; if (q->tail == NULL) { q->head = n; q->tail = n; } else { q->tail->next = n; q->tail = n; } return n; } The following function extracts the head node: void pop (queue* q) { node* n = q->head; if (q->head) { q->head = q->head->next; // may be NULL if (!q->head) q->tail = NULL; } free n; } In a circular queue, we don't need to keep track of the head because tail->next always points to the head unless tail is NULL. So we can eliminate the head pointer from the queue structure: struct queue { node* tail; }; The insertion function therefore changes as follows: node* push (queue* q, T value) { node* n = malloc (sizeof (node)); n->data = value; if (q->tail == NULL) { n->next = n; q->tail = n; } else { n->next = q->tail->next; q->tail->next = n; q->tail = n; } return n; } And the extraction function changes as follows: void pop (queue* q) { if (q->tail == NULL) return; // empty list node* n = q->tail; if (q->tail == q->tail->next) // a list of one q->tail = NULL; else q->tail->next = q->tail->next->next; // adjust the head free n; }
What is the difference between linear and circular queue?
What is the difference between linear and circular queue? In: http://wiki.answers.com/Q/FAQ/2545-37 [Edit categories]The Queue by Default is Linear, it would be termed as Circular if the Last Element of the Queue pointsto the first element of the List
What is the name of the ticket that allows you to go to the head of a queue at Disneyland?
fast pass
Does a queue crawl through memory in the direction of its head or its tail?
A queue crawls through memory in the direction of its tail. This answer assumes that you push elements at the head and that you pop elements at the tail. This means that the set of active elements will migrate in memory towards the tail. It is also possible that the queue be circular, in which case the elements would still follow the tail, but that tail might jump back towards the initial head from time to time.
What does cutting someone's head off means?
It means to separate their head from their body with a sharp implement.
Write a program in c language to reverse elements of a queue?
There are many ways to reverse the order of the elements in a queue. Provided that you have access to the implementation of the queue, it is of course easy to read the elements from the tail end rather than the front end, thus reversing the elements. However, considering the queue as a black box, and assuming the queue only allows for its characteristic operations (removal of head element, addition to tail), the best method to reverse the elements in a queue to engage a stack. You'd remove the elements from the queue (always reading the head of the queue), and push each element onto the stack. When the queue is empty, you reverse that process: pop each element from the stack until it is empty, and add each element in this order to the end of the queue. Your queue will have the exact same elements as in the beginning, but in reverse order. The exact implementation of this in C, or in any other programming language, is trivial, but the exact source code depends on the implementation of queue and stack containers. Following is pseudocode: Queue<Item> reverse (Queue<Item> queue) { Stack<Item> stack; Item item; while (queue.remove(&item)) { stack.push(item); } while(stack.pop(&item)) { queue.add(item); } return queue; }
