C++

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.

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 110 HOOD frontPtr backPtr 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 many external pointers it has. Such a chain does have a node whose next pointer is nullptr. 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. pienellaLIULIS UILE ADI Queue 401 FIGURE 14-3 A circular chain of linked nodes with one external pointer backPtr Note: If you use a linear chain with only a head pointer to implement a queue, the enqueue operation will be inefficient. Each addition to the queue requires a traversal to the end of the chain. As the queue increases in length, the traversal time and hence enqueue's time requirementwill increase. Listing 14-3 shows the header file for our class definition. LISTING 14-3 The header file for the class LinkedQueue /** ADT queue: Link-based implementation. @file LinkedQueue. */ #ifndef LINKED_QUEUE #define _LINKED_QUEUE #include "Queue Interface.h" #include "Node.h" #include "PrecondViolatedExcep.h" template class LinkedQueue : public Queue Interface private: // The queue is implemented as a chain of linked nodes that has // two external pointers, a head pointer for the front of the queue // and a tail pointer for the back of the queue. Node* backPtr; Node* frontPtr; public: LinkedQueue O; LinkedQueue (const LinkedQueue& aQueue); LinkedQueue ; bool isEmpty const; bool enqueue (const ItemType& newEntry); bool dequeue O; (continues) 402 CHAPTER 14 Queue and Priority Queue Implementations /** @throw PrecondViolatedExcep if the queue is empty / ItemType peek Front const throw (PrecondViolatedExcep); }; // end LinkedQueue #include "LinkedQueue.cpp" #endif The method enqueue. Inserting a new node, to which newNodePtr points, at the back of the chain that represents the queue requires three pointer changes: the next pointer in the new node, the next pointer in the current back node, and the external pointer backPtr. Figure 14-4 illustrates these changes during the addition of an item to a nonempty queue and indicates the order in which they can occur. The statements to perform this addition are newNodePtr->setNext(nullptr); backPtr->setNext (newNodePtr); backPtr = newNode Ptr; FIGURE 14-4 Adding an item to a nonempty queue S o 6 : 0 7 1. newNodePtr->setNext(nullptr); . nanloderer->sekert(mal lei); frontPtr backPtr newNodePtr 19-06-06-10- 2 2. backPtr->setNext(newNodePtr): belPersekere (verkotorite); frontPtr backPtr newNodePtr 46-6-6--20: 3. backPtr = newNodePtr: bare vakantie frontPtr backPtr newNodePtr The addition of an item to an empty queue is a special case, as Figure 14-5 illustrates. If newNode Ptr points to the new node, the following statements add the node to the empty chain: frontPtr = newNodePtr; backPtr = newNodePtr These statements easily follow from the realization that the chain has only one node, which is both the first and last node in the chain