Question
In: Computer Science
b. Implement StackFromList, a templated stack class backed by the above singlylinked list. The stack should...
b. Implement StackFromList, a templated stack class backed by the above singlylinked list. The stack should have a private linked list member, and utilize the linked list methods to implement its functionality. The stack should include a constructor, a destructor, a push, a pop, and an isEmpty method (which returns a bool).
c. Implement, QueueFromList, a templated queue class backed by the above singlylinked list. The queue should have a private linked list member, and utilize the linked list methods to implement its functionality. The queue should include a constructor, a destructor, an enqueue (insert to head), a deque (remove from tail), and an isEmpty method (which returns a bool).
LinkList.h:
#ifndef LinkedList_h
#define LinkedList_h
#include <iostream>
using namespace std;
template <class T = int>
class Node {
public:
Node(); // default constructor
Node(const T& data, Node<T>* next = nullptr); // donstructor
T data; // node data
Node<T>* next; // node next pointer
};
template <class T = int>
class LinkedList {
public:
LinkedList(); // constructor
~LinkedList(); // destructor
T deleteFromHead(); // removes and returns content of head
T deleteFromTail(); // removes and returns content of tail
void deleteNode(T data); // removes node with specified data
void InsertToHead(T data); // insert node with data at the head
void InsertToTail(T data); // insert node with data at the tail
int getSize(); // returns size of linked list
void print(); // prints linked list
private:
Node<T>* head; // head of linked list
};
/******* From here down is the content of the LinkedList.cpp file: ***********************/
/* Implementation of Node */
// default constructor
template<class T>
Node<T>::Node()
{
}
// constructor
template<class T>
Node<T>::Node(const T& data, Node<T>* next)
{
this->data = data;
this->next = next;
}
/* Implementation of linked list */
// constructor
template <class T>
LinkedList<T>::LinkedList()
{
head = nullptr;
}
// destructor
template <class T>
LinkedList<T>::~LinkedList()
{
Node<T>* current = head;
while (current != 0) {
Node<T>* next = current->next;
delete current;
current = next;
}
head = nullptr;
}
template <class T>
T LinkedList<T>::deleteFromHead()
{
T data;
if (head != nullptr)
{
if (head->next == nullptr)
{
data = head->data;
delete(head);
head = nullptr;
return data;
}
else
{
Node<T> *temp = head;
data = temp->data;
head = head->next;
}
}
return data;
}
template <class T>
T LinkedList<T>::deleteFromTail()
{
if (head == nullptr)
return 0;
if (head->next == nullptr)
{
T data = head->data;
delete(head);
head = nullptr;
return data;
}
Node<T> *temp = head;
while (temp->next->next != nullptr)
{
temp = temp->next;
}
T data = temp->next->data;
// Delete last node
delete (temp->next);
// Change next of second last
temp->next = nullptr;
return data;
}
template <class T>
void LinkedList<T>::InsertToHead(T data)
{
Node<T> * newNode = new Node<T>(data, nullptr);
if (head == nullptr)
head = newNode;
else
{
newNode->next = head;
head = newNode;
}
}
template <class T>
void LinkedList<T>::InsertToTail(T data)
{
Node<T> * newNode = new Node<T>(data, nullptr);
if (head == nullptr)
head = newNode;
else
{
Node<T> *temp = head;
while (temp->next != nullptr)
temp = temp->next;
temp->next = newNode;
}
}
template <class T>
int LinkedList<T>::getSize()
{
int size = 0;
Node<T> *temp = head;
while (temp != nullptr)
{
size++;
temp = temp->next;
}
return size;
}
template <class T>
void LinkedList<T>::deleteNode(T data)
{
if (head == nullptr)
return;
if (head->next == nullptr && head->data == data)
{
head->next = nullptr;
return;
}
if (head->data == data)
{
head = head->next;
return;
}
Node<T> *curr = head;
Node<T> *prev = head;
while (curr != nullptr)
{
if (curr->data == data)
{
break;
}
prev = curr;
curr = curr->next;
}
if (curr == nullptr)
return;
if (curr->next == nullptr)
{
prev->next = nullptr;
delete curr;
return;
}
prev->next = curr->next;
}
template <class T>
void LinkedList<T>::print()
{
if (head == nullptr)
{
cout << "Linked list is empty" << endl;;
return;
}
cout << head->data << " ";
if (head->next == nullptr)
{
cout << endl;
return;
}
Node<T>* currNode = head->next;
Node<T>* prevNode = head;
while (currNode->next != nullptr)
{
cout << currNode->data << " ";
prevNode = currNode;
currNode = currNode->next;
}
cout << currNode->data << endl;
return;
}
#endif
main.cpp:
//
// main.cpp
//
// Copyright 穢 Tali Moreshet. All rights reserved.
//
#include <iostream>
#include <string>
#include "LinkedList.h"
using namespace std;
int main(int argc, const char * argv[]) {
/*** For part (b): Testing of stack: ***/
cout << endl << endl << "*** Int stack: ***" << endl;
StackFromList<int> intStack;
cout << "Pushing to the stack: 1 2 3 4" << endl;
intStack.push(1);
intStack.push(2);
intStack.push(3);
intStack.push(4);
cout << "The top of the stack was " << intStack.pop() << endl;
cout << "The top of the stack was " << intStack.pop() << endl;
cout << "Pushing to the stack: 5 6" << endl;
intStack.push(5);
intStack.push(6);
cout << "The stack is ";
if (!intStack.isEmpty())
cout << "not ";
cout << "empty" << endl;
cout << "The top of the stack was " << intStack.pop() << endl;
cout << "The top of the stack was " << intStack.pop() << endl;
cout << "The top of the stack was " << intStack.pop() << endl;
cout << "The top of the stack was " << intStack.pop() << endl;
cout << "The stack is ";
if (!intStack.isEmpty())
cout << "not ";
cout << "empty" << endl;
/*** For part (c): Testing of queue: ***/
cout << endl << endl << "*** Char queue: ***" << endl;
QueueFromList<char> charQueue;
cout << "Enqueueing to the queue: a b c d" << endl;
charQueue.enqueue('a');
charQueue.enqueue('b');
charQueue.enqueue('c');
charQueue.enqueue('d');
cout << "The head of the queue was " << charQueue.dequeue() << endl;
cout << "The head of the queue was " << charQueue.dequeue() << endl;
cout << "Enqueueing to the queue: e" << endl;
charQueue.enqueue('e');
cout << "The queue is ";
if (!charQueue.isEmpty())
cout << "not ";
cout << "empty" << endl;
cout << "The head of the queue was " << charQueue.dequeue() << endl;
cout << "The head of the queue was " << charQueue.dequeue() << endl;
cout << "The head of the queue was " << charQueue.dequeue() << endl;
cout << "The queue is ";
if (!charQueue.isEmpty())
cout << "not ";
cout << "empty" << endl;
return 0;
}Solutions
Expert Solution
Code:
StackFromList.h
#ifndef STACKFROMLIST_H
#define STACKFROMLIST_H
#include"LinkedList.h"
template<class T=int>
class StackFromList{
private:
LinkedList<T> list;
public:
StackFromList(){};
~StackFromList();
void push(T data);
T pop();
bool isEmpty();
};
template<class T>
StackFromList<T>::~StackFromList(){
list.~LinkedList();
}
template<class T>
void StackFromList<T>::push(T data){
list.InsertToHead(data);
}
template<class T>
T StackFromList<T>::pop(){
return list.deleteFromHead();
}
template<class T>
bool StackFromList<T>::isEmpty(){
return (list.getSize()==0);
}
#endifQueueFromList.h
#ifndef QUEUEFROMLIST_H
#define QUEUEFROMLIST_H
#include"LinkedList.h"
template<class T=int>
class QueueFromList{
private:
LinkedList<T> list;
public:
QueueFromList(){};
~QueueFromList();
void enqueue(T data);
T dequeue();
bool isEmpty();
};
template<class T>
QueueFromList<T>::~QueueFromList(){
list.~LinkedList();
}
template<class T>
void QueueFromList<T>::enqueue(T data){
list.InsertToHead(data);
}
template<class T>
T QueueFromList<T>::dequeue(){
return list.deleteFromTail();
}
template<class T>
bool QueueFromList<T>::isEmpty(){
return (list.getSize()==0);
}
#endifLinkedList.h: same as provided in question
#ifndef LinkedList_h
#define LinkedList_h
#include <iostream>
using std::cout;
using std::endl;
template <class T = int>
class Node {
public:
Node(); // default constructor
Node(const T& data, Node<T>* next = nullptr); // donstructor
T data; // node data
Node<T>* next; // node next pointer
};
template <class T = int>
class LinkedList {
public:
LinkedList(); // constructor
~LinkedList(); // destructor
T deleteFromHead(); // removes and returns content of head
T deleteFromTail(); // removes and returns content of tail
void deleteNode(T data); // removes node with specified data
void InsertToHead(T data); // insert node with data at the head
void InsertToTail(T data); // insert node with data at the tail
int getSize(); // returns size of linked list
void print(); // prints linked list
private:
Node<T>* head; // head of linked list
};
/******* From here down is the content of the LinkedList.cpp file: ***********************/
/* Implementation of Node */
// default constructor
template<class T>
Node<T>::Node()
{
}
// constructor
template<class T>
Node<T>::Node(const T& data, Node<T>* next)
{
this->data = data;
this->next = next;
}
/* Implementation of linked list */
// constructor
template <class T>
LinkedList<T>::LinkedList()
{
head = nullptr;
}
// destructor
template <class T>
LinkedList<T>::~LinkedList()
{
Node<T>* current = head;
while (current != 0) {
Node<T>* next = current->next;
delete current;
current = next;
}
head = nullptr;
}
template <class T>
T LinkedList<T>::deleteFromHead()
{
T data;
if (head != nullptr)
{
if (head->next == nullptr)
{
data = head->data;
delete(head);
head = nullptr;
return data;
}
else
{
Node<T> *temp = head;
data = temp->data;
head = head->next;
}
}
return data;
}
template <class T>
T LinkedList<T>::deleteFromTail()
{
if (head == nullptr)
return 0;
if (head->next == nullptr)
{
T data = head->data;
delete(head);
head = nullptr;
return data;
}
Node<T> *temp = head;
while (temp->next->next != nullptr)
{
temp = temp->next;
}
T data = temp->next->data;
// Delete last node
delete (temp->next);
// Change next of second last
temp->next = nullptr;
return data;
}
template <class T>
void LinkedList<T>::InsertToHead(T data)
{
Node<T> * newNode = new Node<T>(data, nullptr);
if (head == nullptr)
head = newNode;
else
{
newNode->next = head;
head = newNode;
}
}
template <class T>
void LinkedList<T>::InsertToTail(T data)
{
Node<T> * newNode = new Node<T>(data, nullptr);
if (head == nullptr)
head = newNode;
else
{
Node<T> *temp = head;
while (temp->next != nullptr)
temp = temp->next;
temp->next = newNode;
}
}
template <class T>
int LinkedList<T>::getSize()
{
int size = 0;
Node<T> *temp = head;
while (temp != nullptr)
{
size++;
temp = temp->next;
}
return size;
}
template <class T>
void LinkedList<T>::deleteNode(T data)
{
if (head == nullptr)
return;
if (head->next == nullptr && head->data == data)
{
head->next = nullptr;
return;
}
if (head->data == data)
{
head = head->next;
return;
}
Node<T> *curr = head;
Node<T> *prev = head;
while (curr != nullptr)
{
if (curr->data == data)
{
break;
}
prev = curr;
curr = curr->next;
}
if (curr == nullptr)
return;
if (curr->next == nullptr)
{
prev->next = nullptr;
delete curr;
return;
}
prev->next = curr->next;
}
template <class T>
void LinkedList<T>::print()
{
if (head == nullptr)
{
cout << "Linked list is empty" << endl;;
return;
}
cout << head->data << " ";
if (head->next == nullptr)
{
cout << endl;
return;
}
Node<T>* currNode = head->next;
Node<T>* prevNode = head;
while (currNode->next != nullptr)
{
cout << currNode->data << " ";
prevNode = currNode;
currNode = currNode->next;
}
cout << currNode->data << endl;
return;
}
#endifmain.cpp
//
// main.cpp
//
// Copyright ? Tali Moreshet. All rights reserved.
//
#include <iostream>
#include <string>
#include "LinkedList.h"
#include "StackFromList.h"
#include "QueueFromList.h"
using namespace std;
int main(int argc, const char * argv[]) {
/*** For part (b): Testing of stack: ***/
cout << endl << endl << "*** Int stack: ***" << endl;
StackFromList<int> intStack;
cout << "Pushing to the stack: 1 2 3 4" << endl;
intStack.push(1);
intStack.push(2);
intStack.push(3);
intStack.push(4);
cout << "The top of the stack was " << intStack.pop() << endl;
cout << "The top of the stack was " << intStack.pop() << endl;
cout << "Pushing to the stack: 5 6" << endl;
intStack.push(5);
intStack.push(6);
cout << "The stack is ";
if (!intStack.isEmpty())
cout << "not ";
cout << "empty" << endl;
cout << "The top of the stack was " << intStack.pop() << endl;
cout << "The top of the stack was " << intStack.pop() << endl;
cout << "The top of the stack was " << intStack.pop() << endl;
cout << "The top of the stack was " << intStack.pop() << endl;
cout << "The stack is ";
if (!intStack.isEmpty())
cout << "not ";
cout << "empty" << endl;
/*** For part (c): Testing of queue: ***/
cout << endl << endl << "*** Char queue: ***" << endl;
QueueFromList<char> charQueue;
cout << "Enqueueing to the queue: a b c d" << endl;
charQueue.enqueue('a');
charQueue.enqueue('b');
charQueue.enqueue('c');
charQueue.enqueue('d');
cout << "The head of the queue was " << charQueue.dequeue() << endl;
cout << "The head of the queue was " << charQueue.dequeue() << endl;
cout << "Enqueueing to the queue: e" << endl;
charQueue.enqueue('e');
cout << "The queue is ";
if (!charQueue.isEmpty())
cout << "not ";
cout << "empty" << endl;
cout << "The head of the queue was " << charQueue.dequeue() << endl;
cout << "The head of the queue was " << charQueue.dequeue() << endl;
cout << "The head of the queue was " << charQueue.dequeue() << endl;
cout << "The queue is ";
if (!charQueue.isEmpty())
cout << "not ";
cout << "empty" << endl;
return 0;
}Output: compiled and run using g++ compiler(Put all files in single directory and then compile and run)
venereology answered 7 months agoRelated Solutions
In simple Java language algorithm: Implement a static stack class of char. Your class should include...
In simple Java language algorithm:
Implement a static stack class of char. Your class should
include
two constructors. One (no parameters) sets the size of the
stack to 10. The other constructor accepts a single parameter
specifying the desired size of the stack
a push and pop operator
an isEmpty and isFull method . Both return Booleans indicating
the status of the stack
Using the stack class you created in problem 1), write a static
method called parse that parses...
Implement our own stack class patterned after Java's Stack class. Start with a generic class that...
Implement our own stack class patterned after Java's Stack
class. Start with a generic class that uses an ArrayList for
storage of the elements:
public class StackBox<E>
{
ArrayList<E> stack = new ArrayList<E>();
}
Implement the following methods in StackBox:
boolean empty()
Tests if this stack is empty.
E push(E item)
Pushes an item onto the top of this stack. Returns item
pushed.
E pop()
Removes the object at the top of this stack and returns that object
as the...
StackBox Implement our own stack class patterned after Java's Stack class. Start with a generic class...
StackBox
Implement our own stack class patterned after Java's Stack
class. Start with a generic class that uses an ArrayList for
storage of the elements:
public class StackBox<E>
{
ArrayList<E> stack = new ArrayList<E>();
}
Implement the following methods in StackBox:
boolean empty()
Tests if this stack is empty.
E push(E item)
Pushes an item onto the top of this stack. Returns item
pushed.
E pop()
Removes the object at the top of this stack and returns that object
as...
Java programming! Implement a static stack class of char. Your class should include two constructors. One...
Java programming!
Implement a static stack class of char. Your class should
include
two constructors. One (no parameters) sets the size of the
stack to 10. The other constructor accepts a single parameter
specifying the desired size of the stack
a push and pop operator
an isEmpty and isFull method . Both return Booleans indicating
the status of the stack
Change this cods according to instructions please:
public class Stack {
int stackPtr;
int data[];
public Stack() //constructor
{
stackPtr=0;...
Write a code to implement a python stack class using linked list. use these operations isEmpty...
Write a code to implement a python stack class using linked
list. use these operations
isEmpty • push. • pop. • peek. •
size
Time and compare the performances ( this is optional but I would
appreciate it)
All code should be in Python 3. Implement the Stack Class, using the push, pop, str,...
All code should be in Python 3. Implement the Stack
Class, using the push, pop, str, init methods, and the insurance
variable 'list'.
1. Implement the stack abstract data type. Write it as a separate class called Stack. For...
1. Implement the stack abstract data type. Write it as a
separate class called Stack. For simplicity the data type to be
stored in the stack is String but you can also use generic
type.
2. Test your class implementation by calling push() and pop().
If the stack is empty (size equals zero) pop() should return null
and print that “stack is empty”. If stack is full (size equals max)
push() returns false and prints that “stack is full”.
This...
Implement a class named stack pair that provides a pair of stacks. Make the class a...
Implement a class named stack pair that provides a pair of
stacks. Make the class a template class. So, you will have two
files: stack pair.h and stack pair.template, following the style of
the text. The basic idea is that two stacks can share a single
static array. This may be advantageous if only one of the stacks
will be in heavy use at any one time.
• The class should have various methods to manipulate the
stack:
T pop...
0. Introduction. In this assignment you will implement a stack as a Java class, using a...
0. Introduction.
In this assignment you will implement a stack as a Java class,
using a linked list of nodes. Unlike the stack discussed in the
lectures, however, your stack will be designed to efficiently
handle repeated pushes of the same element. This shows that there
are often many different ways to design the same data structure,
and that a data structure should be designed for an anticipated
pattern of use.
1. Theory.
The most obvious way to represent a...
Using STL stack class, implement in C++ a function that checks for balanced braces { },...
Using STL stack class, implement in C++ a function that checks
for balanced braces { }, in a given string / arithmetic
expressions.
ADVERTISEMENT
ADVERTISEMENT
Latest Questions
- You are interested in buying a house and renting it out. You expect to receive a...
- A C corporation earns $10 per share before taxes. After it has paid taxes, it will...
- Using Hirschi’s Social Bond theory as your frame of reference, discuss the major ideas behind this...
- A research center survey of 2 comma 375 adults found that 1 comma 942 had bought...
- Hello math expert... plz answer clearly. Is Virus Covid-19 (exponential function), or is it only (doubled...
- On January 1, 2021, the general ledger of Dynamite Fireworks includes the following account balances: Accounts...
- 1. Suppose that Lexi preferences are given by the utility function u(x1; x2) = x12x2, where...
ADVERTISEMENT