Need Help With Class Assignment: Palindrome Stacks and Queues

[mysiarobin1987]

Assignment:
Goal: Stacks and Queues to implement a programming solution
Make sure you thoroughly read and understand the directions before you begin.
Problem Statement
A palindrome is a character string that is equal to its reverse. A simple palindrome would be a word that is
the same spelled forward or backward such as “level”. A palindrome can also be a phrase such as "Never
odd or even". This is not a simple palindrome, since making it the same as its reverse requires that we
ignore spaces and punctuation marks. For this assignment, a palindrome is defined to be a character string,
where all non-alphabetic characters are ignored, and upper-case and lower-case versions of the same letter
are viewed as equivalent. Alphabetic characters includes characters ’A’ through ’Z’ and ’a’ through ’z’
inclusive. Thus punctuation marks, digits, space, tab, carriage return, hyphens, underscores, and other nonalphabetic
characters are ignored in the palindrome decision process.
The assignment is to write a program that does the following. You will need to define extra functions to
complete some of these tasks such as the first two bullet items:
 Prompts the user to type in a character string
 Gets the characters and stores them in a stack data structure.
 Makes use of the stack and a queue data structure to check for a palindrome.
 Defines a function “isPalindrome” that determines whether the string is a palindrome. The function
“isPalindrome” returns 1 if x is a palindrome, and 0 if x is not a palindrome.
int isPalindrome(char *x)
 Displays an appropriate message on the screen that indicates the string and whether the string is a
palindrome or not.
Programming Hints
 Your program will involve three files: main.c, Palindrome.c, and Palindrome.h.
o The file Palindrome.h contains exactly one line, the prototype of your function isPalindrome.
o The file Palindrome.c contains the definition of your function isPalindrome. It should have your
name, the date, and #include "Palindrome.h". It should not contain a main function.
o Your file main.c contains your main function. That file should also specify any #include files,
including Palindrome.h. Your main program should thoroughly test the Palindrome program
 The following header files must be defined and included in the source code using the stacks and
queues.
o #include “stack.h”
o #include “queue.h”
You will need to submit these 2 files with your submission of the other 3 files mentioned above.
 The following functions may be helpful and are provided by the C Standard Library:
o int isalpha(char c) // returns non-zero integer if c is an alphabetic character, 0 if not
o char toupper(char c) // returns the upper-case version of an alphabetic character
Testing Suggestions
A list of examples is given below in a C++ variable declaration. Make sure that you test for the following
situations.
1. Test that your program returns a value of 1 on the examples.
2. Test that your program returns 0 if you change one of the characters in any of the examples.

****I'm just lost on what to do with the palindrome.cpp file. Not asking anyone to write the code for me, just any useful information/tips on where to start.****

[mysiarobin1987]

// Queue.h and Stack.h were provided by my instructor as follows:

// Queue.h
#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>
using namespace std;

// Stack template
template <class T>
class Queue
{
private:
T *queueArray; // Points to the queue array
int queueSize; // The queue size
int front; // Subscript of the queue front
int rear; // Subscript of the queue rear
int numItems; // Number of items in the queue
public:
// Constructor
Queue(int);

// Copy constructor
Queue(const Queue &);

// Destructor
~Queue();

// Queue operations
void enqueue(T);
void dequeue(T &);
bool isEmpty() const;
bool isFull() const;
void clear();
};

//***************************************************************
// This constructor creates an empty queue of a specified size. *
//***************************************************************
template <class T>
Queue<T>::Queue(int s)
{
queueArray = new T[s];
queueSize = s;
front = -1;
rear = -1;
numItems = 0;
}

//***************************************************************
// Copy constructor *
//***************************************************************
template <class T>
Queue<T>::Queue(const Queue &obj)
{
// Allocate the queue array.
queueArray = new T[obj.queueSize];

// Copy the other object's attributes.
queueSize = obj.queueSize;
front = obj.front;
rear = obj.rear;
numItems = obj.numItems;

// Copy the other object's queue array.
for (int count = 0; count < obj.queueSize; count++)
queueArray[count] = obj.queueArray[count];
}

//***************************************************************
// Destructor *
//***************************************************************
template <class T>
Queue<T>::~Queue()
{
delete [] queueArray;
}

//***************************************************************
// Function enqueue inserts a value at the rear of the queue. *
//***************************************************************
template <class T>
void Queue<T>::enqueue(T item)
{
if (isFull())
cout << "The queue is full.\n";
else
{
// Calculate the new rear position
rear = (rear + 1) % queueSize;
// Insert new item
queueArray[rear] = item;
// Update item count
numItems++;
}
}

//***************************************************************
// Function dequeue removes the value at the front of the queue *
// and copies t into num. *
//***************************************************************
template <class T>
void Queue<T>::dequeue(T &item)
{
if (isEmpty())
cout << "The queue is empty.\n";
else
{
// Move front
front = (front + 1) % queueSize;
// Retrieve the front item
item = queueArray[front];
// Update item count
numItems--;
}
}

//***************************************************************
// isEmpty returns true if the queue is empty, otherwise false. *
//***************************************************************
template <class T>
bool Queue<T>::isEmpty() const
{
bool status;

if (numItems)
status = false;
else
status = true;

return status;
}

//***************************************************************
// isFull returns true if the queue is full, otherwise false. *
//***************************************************************
template <class T>
bool Queue<T>::isFull() const
{
bool status;

if (numItems < queueSize)
status = false;
else
status = true;

return status;
}

//*****************************************************************
// clear sets the front and rear indices, and sets numItems to 0. *
//*****************************************************************
template <class T>
void Queue<T>::clear()
{
front = queueSize - 1;
rear = queueSize - 1;
numItems = 0;
}
#endif

//Stack.h
#ifndef STACK_H
#define STACK_H
#include <iostream>
using namespace std;

// Stack template
template <class T>
class Stack
{
private:
T *stackArray;
int stackSize;
int top;

public:
//Constructor
Stack(int);

// Copy constructor
Stack(const Stack&);

// Destructor
~Stack();

// Stack operations
void push(T);
void pop(T &);
bool isFull();
bool isEmpty();
};

//***************************************************
// Constructor *
//***************************************************

template <class T>
Stack<T>::Stack(int size)
{
stackArray = new T[size];
stackSize = size;
top = -1;
}

//***************************************************
// Copy constructor *
//***************************************************

template <class T>
Stack<T>::Stack(const Stack &obj)
{
// Create the stack array.
if (obj.stackSize > 0)
stackArray = new T[obj.stackSize];
else
stackArray = NULL;

// Copy the stackSize attribute.
stackSize = obj.stackSize;

// Copy the stack contents.
for (int count = 0; count < stackSize; count++)
stackArray[count] = obj.stackArray[count];

// Set the top of the stack.
top = obj.top;
}

//***************************************************
// Destructor *
//***************************************************

template <class T>
Stack<T>::~Stack()
{
if (stackSize > 0)
delete [] stackArray;
}

//*************************************************************
// Member function push pushes the argument onto *
// the stack. *
//*************************************************************

template <class T>
void Stack<T>::push(T item)
{
if (isFull())
{
cout << "The stack is full.\n";
}
else
{
top++;
stackArray[top] = item;
}
}

//*************************************************************
// Member function pop pops the value at the top *
// of the stack off, and copies it into the variable *
// passed as an argument. *
//*************************************************************

template <class T>
void Stack<T>::pop(T &item)
{
if (isEmpty())
{
cout << "The stack is empty.\n";
}
else
{
item = stackArray[top];
top--;
}
}

//*************************************************************
// Member function isFull returns true if the stack *
// is full, or false otherwise. *
//*************************************************************

template <class T>
bool Stack<T>::isFull()
{
bool status;

if (top == stackSize - 1)
status = true;
else
status = false;

return status;
}

//*************************************************************
// Member function isEmpty returns true if the stack *
// is empty, or false otherwise. *
//*************************************************************

template <class T>
bool Stack<T>::isEmpty()
{
bool status;

if (top == -1)
status = true;
else
status = false;

return status;
}
#endif

// palindrome.h
#ifndef _PALINDROME
#define _PALINDROME

int isPalindrome(char *x);

#endif

[dhayden]

When posting code, please use code tags. Edit your post, highlight the code and click the <> button to the right of the edit window.

It's odd to use a stack and queue to check for a palindrome, but I guess the point is just to get you used to using these data structures. I guess you could check for a palindrome like this:

for each character in the string
    if it's a letter then
        convert letter to upper case
        push it on the stack
        enqueue it in the queue.

// Now check for a palindrome
while (stack not empty)
    char ch1, ch2
    pop a letter from stack to ch1
    dequeue a letter from queue to ch2
    if (ch1 != ch2) then it is NOT a palindrome
}

// If you got here then it's a palindrome

This works because of the key properties of a stack and queue. When you pop items off the stack, you're getting them in reverse order. When queue dequeue items from the queue, you're getting them in forward order.