Question: Write an implementation of the ADT queue that uses linked nodes to represent the queue items. Hint: you can take a look at chapter 14.1.2 of your textbook.

Exercise at the end 01 this chapter asks you to consider the emiciency or tnis Implementation. 14.1.2 A Link-Based Implementation A link-based implementation of a queue uses a chain of linked nodes, much like the other link-based implementations that you have seen. However, the queue presents a challenge, since we must be able to not only remove entries from its front but also add them to its back. Removing a node from the beginning of a linked chain is easy, but to add a new node to the chain's end, we need a pointer to the chain's last node. One way to accomplish this is to begin at the first node and traverse the chain until we reach the last one. A much more efficient approach uses a tail pointer to reference the end of the chain just as the head pointer references the beginning of the chain. Figure 14-2 illustrates a chain of linked nodes that has both head and tail pointers. Like the head pointer frontPtr, backPtr is exter nal to the chain. FIGURE 14-2 A chain of linked nodes with head and tail pointers 4. frontPtr backPtr A linear linked chain or a circular linked Figure 14-3 shows that you can actually get by with one external pointer to the back-if you make the last node point to the first one. This data structure is a circular chain of linked nodes. Notice that the nodes in a circular chain have next pointers that never contain nullptr. We will refer to a chain like the one in Figure 14-2 as a linear chain, regardless of how has. Such a chain does have a node whose next pointer is nullptr a queu many external pointers it Programming Problem 1 at the end of the chapter asks you to consider the details of the circular chain implementation. Here we will develop an implementation of the ADT queue using a chain that has both head and tail pointers, as illustrated in Figure 14-2