In: Computer Science
C++:
Write a program using Stacks-Array and Queue-Array data structure we did in class to check whether a given string is a palindrome. (50 points)
This is an exercise in Stacks and Queues. So you need to use both datastructures to test :
In the main you can test whether a string is a palindrome using the method
bool palindromeTest( string test) and should include “QueArr.h” and “StackArr.h”
QueArr.h
#include <iostream>
using namespace std;
template <class ItemType>
class QueArr
{
private:
int maxSize;
int front;
int rear;
ItemType * items;
public:
QueArr();
QueArr(int size);
~QueArr();
void makeEmpty();
bool isEmpty() const;
bool isFull() const;
void add(ItemType item);
void remove(ItemType& item);
void print() const;
};
template <class ItemType>
QueArr<ItemType>::QueArr()
{
maxSize = 100;
front = maxSize - 1;
rear = maxSize - 1;
items = new ItemType [maxSize];
}
template <class ItemType>
QueArr<ItemType>::QueArr( int size )
{
maxSize = size;
front = maxSize - 1;
rear = maxSize - 1;
items = new ItemType[maxSize];
}
template <class ItemType>
QueArr<ItemType>::~QueArr()
{
delete[] items;
}
template <class ItemType>
void QueArr<ItemType>::makeEmpty()
{
front = maxSize - 1;
rear = maxSize - 1;
}
template <class ItemType>
bool QueArr<ItemType>::isEmpty() const
{
return (rear == front);
}
template <class ItemType>
bool QueArr<ItemType>::isFull() const
{
return ((rear + 1) % maxSize == front);
}
template <class ItemType>
void QueArr<ItemType>::add(ItemType item)
{
if (isFull())
cout << "Queue is Full"
<< endl;
else
{
rear = (rear + 1) % maxSize;
items[rear] = item;
}
}
template <class ItemType>
void QueArr<ItemType>::remove(ItemType& item)
{
if (isEmpty())
cout << "Queue is empty"
<< endl;
else
{
front = (front + 1) %
maxSize;
item = items[front];
}
}
template <class ItemType>
void QueArr<ItemType>::print() const
{
if (isEmpty())
cout << "Que is empty"
<< endl;
else
{
//cout << front << ", "
<< length << endl;
int temp = front;
while(temp != rear)
{
temp = (temp +
1) % maxSize;
cout <<
items[temp] << " ";
}
cout << endl;
}
}
StackArr.h
#include <iostream>
using namespace std;
template <class ItemType>
class StackArr
{
public:
StackArr();
//Empty constructor
StackArr(int max); //Constructor which takes a
size
bool IsEmpty() const;
bool IsFull() const;
void Push(ItemType item);
void Pop();
ItemType Top() const;
void PrintStack();
private:
int top;
int maxStack;
ItemType* items;
int length;
};
template <class ItemType>
StackArr<ItemType>::StackArr()
{
maxStack = 100;
top = -1;
items = new ItemType[maxStack];
length = 0;
}
template <class ItemType>
StackArr<ItemType>::StackArr( int max)
{
maxStack = max;
top = -1;
items = new ItemType[maxStack];
length = 0;
}
template <class ItemType>
bool StackArr<ItemType>::IsEmpty() const
{
return (top == -1);
}
template <class ItemType>
bool StackArr<ItemType>::IsFull() const
{
return (top == maxStack - 1);
}
template <class ItemType>
void StackArr<ItemType>::Push(ItemType item)
{
if (IsFull())
{
cout << "The stack is full
and item cannot be pushed";
}
else
{
top++;
items[top] = item;
length++;
}
}
template <class ItemType>
void StackArr<ItemType>::Pop()
{
if(IsEmpty())
{
cout << "The stack is empty
and item cannot be popped";
}
else
{
top--;
length--;
}
}
template <class ItemType>
ItemType StackArr<ItemType>::Top() const
{
if (IsEmpty())
{
cout << "The stack is empty
and no item on top";
}
else
return items[top];
}
template <class ItemType>
void StackArr<ItemType>::PrintStack()
{
if (length == 0)
cout << "Stack is empty"
<< endl;
else
{
for (int i = 0; i < length;
i++)
cout <<
items[i] << ", ";
cout << endl;
}
}
Note : There were a few mistakes in your Queue Class. I’ve fixed them and posted all the code below including main.cpp which checks for palindrome.
Code:
//QueArr.h:
#include <iostream>
using namespace std;
template <class ItemType>
class QueArr
{
private:
int maxSize;
int front;
int rear;
ItemType * items;
public:
QueArr();
QueArr(int size);
~QueArr();
void makeEmpty();
bool isEmpty() const;
bool isFull() const;
void add(ItemType item);
void remove();
ItemType Front() const;
void print() const;
};
template <class ItemType>
QueArr<ItemType>::QueArr()
{
maxSize = 100;
front = -1;
rear = -1;
items = new ItemType [maxSize];
}
template <class ItemType>
QueArr<ItemType>::QueArr( int size )
{
maxSize = size;
front = maxSize - 1;
rear = maxSize - 1;
items = new ItemType[maxSize];
}
template <class ItemType>
QueArr<ItemType>::~QueArr()
{
delete[] items;
}
template <class ItemType>
void QueArr<ItemType>::makeEmpty()
{
front = maxSize - 1;
rear = maxSize - 1;
}
template <class ItemType>
bool QueArr<ItemType>::isEmpty() const
{
return (rear == -1);
}
template <class ItemType>
bool QueArr<ItemType>::isFull() const
{
return ((rear + 1) % maxSize == front);
}
template <class ItemType>
void QueArr<ItemType>::add(ItemType item)
{
if (isFull())
cout << "Queue is Full" << endl;
else if(rear == -1)
{
front = 0;
rear = 0;
items[rear] = item;
}
else
{
rear = (rear + 1) % maxSize;
items[rear] = item;
}
}
template <class ItemType>
void QueArr<ItemType>::remove()
{
if (isEmpty())
cout << "Queue is empty" << endl;
else
{
front = (front + 1) % maxSize;
}
}
template <class ItemType>
ItemType QueArr<ItemType>::Front() const
{
if (isEmpty())
{
cout << "The stack is empty and no item on top";
}
else
return items[front];
}
template <class ItemType>
void QueArr<ItemType>::print() const
{
if (isEmpty())
cout << "Que is empty" << endl;
else
{
//cout << front << ", " << length << endl;
int temp = front;
while(temp != rear)
{
temp = (temp + 1) % maxSize;
cout << items[temp] << " ";
}
cout << endl;
}
}
//StackArr.h:
#include <iostream>
using namespace std;
template <class ItemType>
class StackArr
{
public:
StackArr(); //Empty constructor
StackArr(int max); //Constructor which takes a size
bool IsEmpty() const;
bool IsFull() const;
void Push(ItemType item);
void Pop();
ItemType Top() const;
void PrintStack();
private:
int top;
int maxStack;
ItemType* items;
int length;
};
template <class ItemType>
StackArr<ItemType>::StackArr()
{
maxStack = 100;
top = -1;
items = new ItemType[maxStack];
length = 0;
}
template <class ItemType>
StackArr<ItemType>::StackArr( int max)
{
maxStack = max;
top = -1;
items = new ItemType[maxStack];
length = 0;
}
template <class ItemType>
bool StackArr<ItemType>::IsEmpty() const
{
return (top == -1);
}
template <class ItemType>
bool StackArr<ItemType>::IsFull() const
{
return (top == maxStack - 1);
}
template <class ItemType>
void StackArr<ItemType>::Push(ItemType item)
{
if (IsFull())
{
cout << "The stack is full and item cannot be pushed";
}
else
{
top++;
items[top] = item;
length++;
}
}
template <class ItemType>
void StackArr<ItemType>::Pop()
{
if(IsEmpty())
{
cout << "The stack is empty and item cannot be popped";
}
else
{
top--;
length--;
}
}
template <class ItemType>
ItemType StackArr<ItemType>::Top() const
{
if (IsEmpty())
{
cout << "The stack is empty and no item on top";
}
else
return items[top];
}
template <class ItemType>
void StackArr<ItemType>::PrintStack()
{
if (length == 0)
cout << "Stack is empty" << endl;
else
{
for (int i = 0; i < length; i++)
cout << items[i] << ", ";
cout << endl;
}
}
//main.cpp:
#include<iostream>
#include<string>
#include "QueArr.h"
#include "StackArr.h"
using namespace std;
bool palindromeTest(string testStr)
{
StackArr <char> stk;
QueArr <char> que;
int loop;
for (loop = 0; loop < testStr.length(); loop++) {
que.add(testStr[loop]);
stk.Push(testStr[loop]);
}
bool isPalindrome = true;
while ((!que.isEmpty()) && (!stk.IsEmpty()) && isPalindrome) {
if (que.Front() != stk.Top()) {
isPalindrome = false;
} else {
que.remove();
stk.Pop();
}
}
if (isPalindrome) {
cout << "\nEntered String is a Palindrome !" << endl;
return true;
} else {
cout << "\nEntered String is NOT a Palindrome !" << endl;
return false;
}
}
int main() {
// declare variables
string testStr;
cout << "Please Enter the String to be tested for Palindrome: ";
getline(cin, testStr);
if (testStr.empty())
{
return 0;
}
palindromeTest(testStr);
}
Output #1:
Output #2: