Implementing a FIFO Linked Queue List

Question

Here is the code in which I am trying to implement a queue using a linked list:

#include <iostream> #include <cstdlib> using namespace std; template <class Item> class Queue{ public: struct node{ Item item;node *next; node (Item x){ item=x; next=0; } }; typedef node* link; link head, tail; public: Queue(int){ head=0;} int empty() const { return head==0; } void put(Item x){ node* t=tail; tail=new node(x); if (head==0) head=tail; else t->next=tail; } Item get(){ Item v=head->item;link t=head->next; delete head; head=tail return v; } }; int main(){ return 0; } 

but I have problems with pointers. For example, when I write Item v = head-> , it should show me an option to select an item, but it does not appear. Also elsewhere in the code after → this character code does not allow me to select an element or the next. Please, help.

Answer 1

ON: The → operator may be overloaded, so the development environment cannot be sure what to do with it. You can do the following (temporarily or permanently) if you really want to autocomplete.

 // IMPORTANT. Make sure "head" is not null before you do it! Node &headNode(*head); // Create a reference headNode.next = tail; // Use TAB or CTRL+SPACE or whatever here after dot 

OFF: I reviewed your code and made some corrections

 template <class Item> class Queue { public: Queue() : head(0) , tail(0) { } bool empty() const { return head==0; } void put(const Item& x) { Node* t = tail; tail = new Node(x); if (head==0) head = tail; else t->next = tail; } Item get() { Item v = head->item; Link t = head->next; delete head; head = t; if(head==0) tail = 0; return v; } private: struct Node { Item item; Node *next; Node(const Item& x) : item(x) , next(0) {} }; typedef Node* Link; Link head,tail; }; 

• Removed int typed nameless parameter from Queue constructor
• Renamed node to node and link to link , because Item is Item , not Item . Just to make it somewhat standardized.
• Initializing tail in the Queue constructor.
• Using a list of initializers instead of code where possible.
• Commit Queue::get() , set tail to zero if the queue becomes empty.
• Using permalinks in Queue::put() and Queue::Node::Node() parameter lists
• node , link , head and tail now closed.
• Queue::empty() now returns bool instead of int .

Answer 2

You would probably be better off reusing an existing container.

The STL explicitly contains, for example, a queue Container Adapter (based on deque by default, which is the most efficient choice).

If you don't need polymorphic behavior, std::queue<Item> is what you are looking for, it is extremely efficient (more than your list-based user queue), and you avoid memory management issues.

If you need polymorphic behavior, use std::queue< std::unique_ptr<Item> > .