Q1) Implement the following non-member function which reverses a given string. String reversal must be done using stack-based logic. void ReverseString(string &); Q2) Implement the following function which determines whether a given string is the reverse of the second one; for example “test string” is the reverse of “gnirts tset”. Reverse detection must be done using stack-based logic. bool IsReverse(const string &, const string &);
Define a stack class called DLStack, in such a way that it can store any type of data. All data in a DLStack must be stored in a DoublyLinkedList instance. Implement the following member methods:
- push – Pushes a new element into the stack.
- pop – Removes the top element from the stack.
- top – Retrieves the top element from the stack.
- IsEmpty – Returns true if the stack is empty, and false otherwise.
Note: These operations should add or remove the element from the head of the DoublyLinkedList instance.
Q1) Implement the following non-member function which reverses a given string. String reversal must be done using stack-based logic.
void ReverseString(string &);
Q2) Implement the following function which determines whether a given string is the reverse of the second one; for example “test string” is the reverse of “gnirts tset”. Reverse detection must be done using stack-based logic.
bool IsReverse(const string &, const string &);
//////////////////////////////////////////////////genDLList.h////////////////////////////////////////////////////////////////////////////////////////
#ifndef DOUBLY_LINKED_LIST
#define DOUBLY_LINKED_LIST
template<class T>
class DLLNode {
public:
DLLNode() {
next = prev = 0;
}
DLLNode(const T& el, DLLNode<T> *n = 0, DLLNode<T> *p = 0) {
info = el; next = n; prev = p;
}
T info;
DLLNode<T> *next, *prev;
};
template<class T>
class DoublyLinkedList {
public:
DoublyLinkedList() {
head = tail = 0;
}
void addToDLLTail(const T&);
T deleteFromDLLTail();
~DoublyLinkedList() {
clear();
}
bool isEmpty() const {
return head == 0;
}
void clear();
void setToNull() {
head = tail = 0;
}
void addToDLLHead(const T&);
T deleteFromDLLHead();
T& firstEl();
T* find(const T&) const;
protected:
DLLNode<T> *head, *tail;
friend ostream& operator<<(ostream& out, const DoublyLinkedList<T>& dll) {
for (DLLNode<T> *tmp = dll.head; tmp != 0; tmp = tmp->next)
out << tmp->info << ' ';
return out;
}
};
template<class T>
void DoublyLinkedList<T>::addToDLLHead(const T& el) {
if (head != 0) {
head = new DLLNode<T>(el,head,0);
head->next->prev = head;
}
else head = tail = new DLLNode<T>(el);
}
template<class T>
void DoublyLinkedList<T>::addToDLLTail(const T& el) {
if (tail != 0) {
tail = new DLLNode<T>(el,0,tail);
tail->prev->next = tail;
}
else head = tail = new DLLNode<T>(el);
}
template<class T>
T DoublyLinkedList<T>::deleteFromDLLHead() {
T el = head->info;
if (head == tail) { // if only one DLLNode on the list;
delete head;
head = tail = 0;
}
else { // if more than one DLLNode in the list;
head = head->next;
delete head->prev;
head->prev = 0;
}
return el;
}
template<class T>
T DoublyLinkedList<T>::deleteFromDLLTail() {
T el = tail->info;
if (head == tail) { // if only one DLLNode on the list;
delete head;
head = tail = 0;
}
else { // if more than one DLLNode in the list;
tail = tail->prev;
delete tail->next;
tail->next = 0;
}
return el;
}
template <class T>
T* DoublyLinkedList<T>::find(const T& el) const {
DLLNode<T> *tmp = head;
for ( ; tmp != 0 && !(tmp->info == el); // overloaded ==
tmp = tmp->next);
if (tmp == 0)
return 0;
else return &tmp->info;
}
template<class T>
T& DoublyLinkedList<T>::firstEl() {
return head->info;
}
template<class T>
void DoublyLinkedList<T>::clear() {
for (DLLNode<T> *tmp; head != 0; ) {
tmp = head;
head = head->next;
delete tmp;
}
}
#endif
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
