The cnPtrQueue has member variable numItems (that keeps track of the number of items in the queue), which should be helpful for implementing the member function size() (for inspecting the number of items in the queue). ● Use the cnPtrQueue to perform a breadth-first (level) traversal of a linked list of linked lists data structure and process (print) the data items stored in the structure. Here is the input: y n n y y y 11 n n y y y 11 y 12 y 13 y 14 n n y y n y y 21 y 22 y 23 y 24 n n y y y 11 y 12 y 13 y 14 n y n n y y y 11 y 12 y 13 y 14 n y y 21 n y n y y 41 y 42 n n y y n y y 21 y 22 y 23 y 24 n y y 31 n y n y y 51 y 52 n n n The correct output should look as follows: Dynamic memory for 0 CNodes freed Dynamic memory for 1 PNodes freed 11 11 Dynamic memory for 1 CNodes freed Dynamic memory for 1 PNodes freed 11 12 13 14 11 12 13 14 Dynamic memory for 4 CNodes freed Dynamic memory for 1 PNodes freed 21 22 23 24 21 22 23 24 Dynamic memory for 0 CNodes freed Dynamic memory for 4 CNodes freed Dynamic memory for 2 PNodes freed 11 12 13 14 11 12 13 14 Dynamic memory for 4 CNodes freed Dynamic memory for 0 CNodes freed Dynamic memory for 2 PNodes freed 11 12 13 14 21 41 42 11 21 41 12 42 13 14 Dynamic memory for 4 CNodes freed Dynamic memory for 1 CNodes freed Dynamic memory for 0 CNodes freed Dynamic memory for 2 CNodes freed Dynamic memory for 4 PNodes freed 21 22 23 24 31 51 52 21 31 51 22 52 23 24 Dynamic memory for 0 CNodes freed Dynamic memory for 4 CNodes freed Dynamic memory for 1 CNodes freed Dynamic memory for 0 CNodes freed Dynamic memory for 2 CNodes freed Dynamic memory for 5 PNodes freed Fill in the "holes" intentionally left: ► Implementation of cnPtrQueue in cnPtrQueue.cpp. ► Function body of ShowAll_BF in nodes_LLoLL.cpp. #ifndef CN_PTR_QUEUE_H #define CN_PTR_QUEUE_H #include // for size_t #include // for STL stack template #include "nodes_LLoLL.h" // for CNode namespace CS3358_SP2023_A5P2 { class cnPtrQueue { public: typedef std::size_t size_type; cnPtrQueue(); bool empty() const; size_type size() const; // returns # of items in queue CNode* front(); void push(CNode* cnPtr); void pop(); private: std::stack inStack; std::stack outStack; size_type numItems; // # of items in queue }; } #endif #include "cnPtrQueue.h" #include using namespace std; namespace CS3358_SP2023_A5P2 { // to be implemented (part of assignment)

The cnPtrQueue has member variable numItems (that keeps track of the number of items in the queue), which should be helpful for implementing the member function size() (for inspecting the number of items in the queue). ● Use the cnPtrQueue to perform a breadth-first (level) traversal of a linked list of linked lists data structure and process (print) the data items stored in the structure. Here is the input: y n n y y y 11 n n y y y 11 y 12 y 13 y 14 n n y y n y y 21 y 22 y 23 y 24 n n y y y 11 y 12 y 13 y 14 n y n n y y y 11 y 12 y 13 y 14 n y y 21 n y n y y 41 y 42 n n y y n y y 21 y 22 y 23 y 24 n y y 31 n y n y y 51 y 52 n n n The correct output should look as follows: Dynamic memory for 0 CNodes freed Dynamic memory for 1 PNodes freed 11 11 Dynamic memory for 1 CNodes freed Dynamic memory for 1 PNodes freed 11 12 13 14 11 12 13 14 Dynamic memory for 4 CNodes freed Dynamic memory for 1 PNodes freed 21 22 23 24 21 22 23 24 Dynamic memory for 0 CNodes freed Dynamic memory for 4 CNodes freed Dynamic memory for 2 PNodes freed 11 12 13 14 11 12 13 14 Dynamic memory for 4 CNodes freed Dynamic memory for 0 CNodes freed Dynamic memory for 2 PNodes freed 11 12 13 14 21 41 42 11 21 41 12 42 13 14 Dynamic memory for 4 CNodes freed Dynamic memory for 1 CNodes freed Dynamic memory for 0 CNodes freed Dynamic memory for 2 CNodes freed Dynamic memory for 4 PNodes freed 21 22 23 24 31 51 52 21 31 51 22 52 23 24 Dynamic memory for 0 CNodes freed Dynamic memory for 4 CNodes freed Dynamic memory for 1 CNodes freed Dynamic memory for 0 CNodes freed Dynamic memory for 2 CNodes freed Dynamic memory for 5 PNodes freed Fill in the "holes" intentionally left: ► Implementation of cnPtrQueue in cnPtrQueue.cpp. ► Function body of ShowAll_BF in nodes_LLoLL.cpp. #ifndef CN_PTR_QUEUE_H #define CN_PTR_QUEUE_H #include // for size_t #include // for STL stack template #include "nodes_LLoLL.h" // for CNode namespace CS3358_SP2023_A5P2 { class cnPtrQueue { public: typedef std::size_t size_type; cnPtrQueue(); bool empty() const; size_type size() const; // returns # of items in queue CNode* front(); void push(CNode* cnPtr); void pop(); private: std::stack inStack; std::stack outStack; size_type numItems; // # of items in queue }; } #endif #include "cnPtrQueue.h" #include using namespace std; namespace CS3358_SP2023_A5P2 { // to be implemented (part of assignment)

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

●

Use the cnPtrQueue to perform a breadth-first (level) traversal of a linked list of linked lists data structure and process (print) the data items stored in the structure.

Here is the input:

y
n
n
y

y
y 11 n
n
y

y
y 11 y 12 y 13 y 14 n
n
y

y
n
y
y 21 y 22 y 23 y 24 n
n
y

y
y 11 y 12 y 13 y 14 n
y
n
n
y

y
y 11 y 12 y 13 y 14 n
y
y 21 n
y
n
y
y 41 y 42 n
n
y

y
n
y
y 21 y 22 y 23 y 24 n
y
y 31 n
y
n
y
y 51 y 52 n
n
n

The correct output should look as follows:

Dynamic memory for 0 CNodes freed
Dynamic memory for 1 PNodes freed
11
11
Dynamic memory for 1 CNodes freed
Dynamic memory for 1 PNodes freed
11 12 13 14
11 12 13 14
Dynamic memory for 4 CNodes freed
Dynamic memory for 1 PNodes freed
21 22 23 24
21 22 23 24
Dynamic memory for 0 CNodes freed
Dynamic memory for 4 CNodes freed
Dynamic memory for 2 PNodes freed
11 12 13 14
11 12 13 14
Dynamic memory for 4 CNodes freed
Dynamic memory for 0 CNodes freed
Dynamic memory for 2 PNodes freed
11 12 13 14 21 41 42
11 21 41 12 42 13 14
Dynamic memory for 4 CNodes freed
Dynamic memory for 1 CNodes freed
Dynamic memory for 0 CNodes freed
Dynamic memory for 2 CNodes freed
Dynamic memory for 4 PNodes freed
21 22 23 24 31 51 52
21 31 51 22 52 23 24
Dynamic memory for 0 CNodes freed
Dynamic memory for 4 CNodes freed
Dynamic memory for 1 CNodes freed
Dynamic memory for 0 CNodes freed
Dynamic memory for 2 CNodes freed
Dynamic memory for 5 PNodes freed

Fill in the "holes" intentionally left:

►

Implementation of cnPtrQueue in cnPtrQueue.cpp.

►

Function body of ShowAll_BF in nodes_LLoLL.cpp.

#ifndef CN_PTR_QUEUE_H
#define CN_PTR_QUEUE_H

#include <cstdlib> // for size_t
#include <stack> // for STL stack template
#include "nodes_LLoLL.h" // for CNode

namespace CS3358_SP2023_A5P2
{
class cnPtrQueue
{
public:
typedef std::size_t size_type;
cnPtrQueue();
bool empty() const;
size_type size() const; // returns # of items in queue
CNode* front();
void push(CNode* cnPtr);
void pop();
private:
std::stack<CNode*> inStack;
std::stack<CNode*> outStack;
size_type numItems; // # of items in queue
};
}

#endif

#include "cnPtrQueue.h"
#include <cassert>
using namespace std;

namespace CS3358_SP2023_A5P2
{
// to be implemented (part of assignment)
}

#ifndef NODES_LLOLL_H
2 #define NODES_LLOLL_H
3
HEMATOGRA
1
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream> // for ostream
namespace CS3358_SP2023_A5P2
// child node
struct CNode
{
}
int data;
CNode* link;
};
// parent node
struct PNode
CNode* data;
PNode* link;
};
// toolkit functions for LLOLL based on above node definitions
void Destroy_clist (CNode*& cListHead);
void Destroy_pList (PNode* & pListHead);
void ShowA11_DF (PNode* pListHead, std::ostream& outs);
void ShowA11_BF (PNode* plistHead, std::ostream& outs);
#endif

#include "nodes_LLOLL.h"
#include "cnPtrQueue.h"
#include <iostream>
using namespace std;
namespace CS3358_SP2023_A5P2
{
// do breadth-first (level) traversal and print data
void ShowA11_BF (PNode* plistHead, ostream& outs)
// to be implemented (part of assignment)
// (put at near top to facilitate printing and grading)
}
void Destroy_clist (CNode*& cListHead)
{
int count = 0;
CNode* cNodePtr = cListHead;
while (cListHead != 0)
{
cListHead = cListHead->link;
delete cNodePtr;
cNodePtr = cListHead;
++count;
}
cout << "Dynamic memory for " << count << "CNodes freed"
<< endl;
}
void Destroy_pList (PNode* & pListHead)
{
int count = 0;
PNode* pNodePtr pListHead;
while (plistHead != 0)
{
plistHead = plistHead->link;
Destroy_clist (pNodePtr->data);
delete pNodePtr;
pNodePtr = plistHead;
++count;
}
cout << "Dynamic memory for " << count << " PNodes freed"
<< endl;
// do depth-first traversal and print data
void ShowA11_DF (PNode* plistHead, ostream& outs)
{
while (plistHead != 0)
{
CNode* cListHead = pListHead->data;
while (clistHead != 0)
{
outs <<clistHead->data <<
cListHead cListHead->link;
plistHead = plistHead->link;

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 4 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.