Exercise at the end 01 this chapter asks you to consider the emiciency or tnis I
ID: 3748400 • Letter: E
Question
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-2Explanation / Answer
// LLADTQ.cpp : This file contains the 'main' function. Program execution begins and ends there.
//The queue abstract data type is defined by the following structure and operations
//-enqueue(item) adds a new item to the rear of the queue.It needs the item and returns nothing.
//-dequeue() removes the front item from the queue.It needs no parameters and returns the item.The queue is modified.
//-isEmpty() tests to see whether the queue is empty.It needs no parameters and returns a boolean value.
//the below program is written in C++, As getch() is deprecatd _getch() function has been used
#include "pch.h"
#include <iostream>
#include <stdio.h>
#include <conio.h>
using namespace std;
struct node
{
int data;
node *next;
}
//pointers for frontptr and backptr
*front = NULL, *rear = NULL, *p = NULL, *np = NULL;
//method for enqueue
void push(int x)
{
np = new node;
np->data = x;
np->next = NULL;
if (front == NULL)
{
front = rear = np;
rear->next = NULL;
}
else
{
rear->next = np;
rear = np;
rear->next = NULL;
}
}
//method for dequeue
int remove()
{
int x;
if (front == NULL)
{
cout << "empty queue ";
}
else
{
p = front;
x = p->data;
front = front->next;
delete(p);
return(x);
}
}
//method for isEmpty()
bool isEmpty()
{
if (front == NULL)
return true;
else
return false;
}
int main()
{
int n, c = 0, x;
cout << "Enter the number of values to be pushed into queue ";
cin >> n;
while (c < n)
{
cout << "Enter the value to be entered into queue ";
cin >> x;
push(x);
c++;
}
cout << " Removed Values ";
while (true)
{
if (front != NULL)
cout << remove() << endl;
else
break;
}
_getch();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.