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 2 months agoRelated Solutions
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...
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...
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.
(a) Write a stack class that is based on a linked list. It can be just...
(a) Write a stack class that is based on a linked list. It can
be just pop(), push(), and anything you need for those methods or
testing.
(b) Write a queue class that is based on a linked list. As
above, it can be just enqueue() and dequeue(), as well as anything
you need for those methods or testing.
(c) Write some test cases, trying to include edge cases. Why did
you choose those tests? Did you get the results...
"""stack.py implements stack with a list""" class Stack(object): def __init__(self): #creates an empty stack. O(1) self.top...
"""stack.py implements stack with a list"""
class Stack(object):
def __init__(self): #creates an empty stack. O(1)
self.top = -1 #the index of the top element of the stack. -1: empty
stack
self.data = []
def push(self, item): # add item to the top of the stack.
O(1)
self.top += 1
self.data.append(item)
def pop(self): # removes and returns the item at the top
O(1)
self.top -=1
return self.data.pop()
def peek(self): # returns the item at the top O(1)
return self.data[len(self.data)-1]
def isEmpty(self):...
Using STL stack class, implement in C++ the following pseudocodefunctioncheckBraces(aString: string) that checks for...
Using STL stack class, implement in C++ the following pseudocode
functioncheckBraces(aString: string) that checks for balanced braces { }
in a given string /arithmetic expressions. Write a main() program to test the
function.// Checks the string aString to verify that braces match.// Returns true if aString contains matching braces, false
otherwise.checkBraces(aString: string): boolean{aStack = a new empty stackbalancedSoFar = truei =0// Tracks character position in stringwhile (balancedSoFar and i < length of aString) {ch = character at position i in...
ADVERTISEMENT
ADVERTISEMENT
Latest Questions
- I want important notes and equations in chapter 4 physics 1 Related topics: 1. contact forces...
- Having read chapter 7, discuss how web sites are being promoted. Also, explain what is monetization?...
- Explain the difference between a necessary and a sufficient condition, and their relation to conditional statements....
- 1. A ball is thrown from the top of a 50 m high cliff with a...
- dont use loops for it and each problem solving process needs a seperate statement within a...
- Accreditation for hospitals in Saudi Arabia. Your opinion regarding: Its impact (at all different system level)...
- 8. Your company's beta is 1.5 and market is 9%. In the same time treasury bill...
ADVERTISEMENT