Palindrome Using Stacks & Queues

Hand up the solution to Q2 but not Q1 (which is an optional warm-up exercise). When submitting your solution, you must include the code you wrote yourself along with your report, but not the unchanged Java files from Blackboard.

Q1 [Optional warm-up exercise: not for submission]

Write a program that reverses a piece of text that the user has input, by taking the following approach:

Create an empty stack

Get the user to input a String, then loop over each character in it

Push each character separately onto the stack until all are on it

Construct a new string by popping characters from the stack until the stack is empty, and adding each one to the end of the new string in turn.

The new string should end up as the reverse of the original string.

Q2 [Hand Up]

Inspired by Q1, write a program to check if a piece of text that the user enters is a palindrome. In this case, you add each character to both a stack and a queue as it is read.

After each character has been put onto both the stack and the queue, start removing characters from both the stack and the queue, and comparing them. If the word is a palindrome, the first character popped will be the same as the first character dequeued, and so on for the second and subsequent characters until the stack and queue are empty.

Notes:

You MUST follow the approach described here to test for palindromes; any other approach not using stacks and queues, will earn you 0 marks.

Palindrome comparisons are normally not case-sensitive, so you could convert all characters to uppercase first. Also, non-alphanumeric characters, such as punctuation and spaces, are usually ignored. For maximum marks, figure out how to use the appropriate method in Javas Character class to do this.

Submit a report with analysis/algorithm, implementation and testing, as you did for Assignments 1 and 2.

public interface Queue { // most important methods public void enqueue(Object n); // add an object at the rear of the queue public Object dequeue(); // remove an object from the front of the queue // others public boolean isEmpty(); // true if queue is empty public boolean isFull(); // true if queue is full (if it has limited storage) public Object front(); // examine front object on queue without removing it } 

import javax.swing.JOptionPane; public class ArrayQueue implements Queue { protected Object Q[]; // array used to implement the queue protected int rear = -1; // index for the rear of the queue protected int capacity; // The actual capacity of the queue array public static final int CAPACITY = 1000; // default array capacity public ArrayQueue() { // default constructor: creates queue with default capacity this(CAPACITY); } public ArrayQueue(int cap) { // this constructor allows you to specify capacity capacity = (cap > 0) ? cap : CAPACITY; Q = new Object[capacity]; } public void enqueue(Object n) { if (isFull()) { JOptionPane.showMessageDialog(null, "Cannot enqueue object; queue is full."); return; } rear++; Q[rear] = n; } public Object dequeue() { // Can't do anything if it's empty if (isEmpty()) return null; Object toReturn = Q[0]; // shuffle all other objects towards 0 int i = 1; while (i <= rear) { Q[i-1] = Q[i]; i++; } rear--; return toReturn; } public boolean isEmpty() { return (rear < 0); } public boolean isFull() { return (rear == capacity-1); } public Object front() { if (isEmpty()) return null; return Q[0]; } } 

public interface Stack { // most important methods public void push(Object n); // push an object onto top of the stack public Object pop(); // pop an object from top of the stack // others public Object top(); // examine top object on stack without removing it public boolean isEmpty(); // true if stack is empty public boolean isFull(); // true if stack is full (if it has limited storage) } 

import javax.swing.JOptionPane; public class ArrayStack implements Stack { protected int capacity; // The actual capacity of the stack array protected static final int CAPACITY = 1000; // default array capacity protected Object S[]; // array used to implement the stack protected int top = -1; // index for the top of the stack public ArrayStack() { // default constructor: creates stack with default capacity this(CAPACITY); } public ArrayStack(int cap) { // this constructor allows you to specify capacity of stack capacity = (cap > 0) ? cap : CAPACITY; S = new Object[capacity]; } public void push(Object element) { if (isFull()) { JOptionPane.showMessageDialog(null, "ERROR: Stack is full."); return; } top++; S[top] = element; } public Object pop() { Object element; if (isEmpty()) { JOptionPane.showMessageDialog(null, "ERROR: Stack is empty."); return null; } element = S[top]; S[top] = null; top--; return element; } public Object top() { if (isEmpty()) { JOptionPane.showMessageDialog(null, "ERROR: Stack is empty."); return null; } return S[top]; } public boolean isEmpty() { return (top < 0); } public boolean isFull() { return (top == capacity-1); } public int size() { return (top + 1); } } 

import javax.swing.JOptionPane;

public class QueueCircularArray implements Queue

{

protected Object Q[]; // array used to implement the queue

protected int rear = 0; // index for the rear of the queue

protected int front = 0; // index for the from of the queue

protected int capacity; // The actual capacity of the queue array

public static final int CAPACITY = 1000; // default array capacity

protected int currentSize; // current circular queue size

public QueueCircularArray() {

// default constructor: creates queue with default capacity

this(CAPACITY);

}

public QueueCircularArray(int cap) {

// this constructor allows you to specify capacity

capacity = (cap > 0) ? cap : CAPACITY;

Q = new Object[capacity];

currentSize = 0;

}

public void enqueue(Object n)

{

if (isFull()) {

JOptionPane.showMessageDialog(null, "Cannot enqueue object; queue is full.");

return;

}

Q[rear] = n;

rear = (rear+1)%Q.length;

currentSize++;

}

public Object dequeue()

{

// Can't do anything if it's empty

if (isEmpty())

return null;

Object toReturn = Q[front];

Q[front] = null;

front = (front+1)%Q.length;

currentSize--;

return toReturn;

}

public boolean isEmpty() {

return (currentSize == 0);

}

public boolean isFull() {

return (currentSize == Q.length);

}

public Object front()

{

if (isEmpty())

return null;

return Q[front];

}

}

package answe;

import javax.swing.JOptionPane;

public class QueueTest {

public static void main(String[] args) {

// Create a Queue

Queue q = new QueueCircularArray();

// Put some strings onto the queue

JOptionPane.showMessageDialog(null, "About to enqueue words onto queue: The end is nigh!");

q.enqueue("The");

q.enqueue("end");

q.enqueue("is");

q.enqueue("nigh!");

// Now dequeue them from the queue

JOptionPane.showMessageDialog(null, "About to dequeue the words ...");

while(!q.isEmpty()) {

String word = (String)q.dequeue(); // Note: have to cast Objects popped to String

JOptionPane.showMessageDialog(null, "Word dequeued: " + word);

}

System.exit(0);

}

}

package answe;

public interface Queue {

// most important methods

public void enqueue(Object n); // add an object at the rear of the queue

public Object dequeue(); // remove an object from the front of the queue

// others

public boolean isEmpty(); // true if queue is empty

public boolean isFull(); // true if queue is full (if it has limited storage)

public Object front(); // examine front object on queue without removing it

}

//linked list implementation of queue

public class LLQueue implements Queue{

private SLinkedList queue;

public LLQueue() {

queue = new SLinkedList();

}

@Override

public void enqueue(Object n) {

queue.gotoTail();

queue.insertNext(n);

}

@Override

public Object dequeue() {

queue.gotoHead();

Object o = queue.getCurr();

queue.deleteHead();

return o;

}

@Override

public boolean isEmpty() {

return queue.isEmpty();

}

@Override

public boolean isFull() {

return false;

}

@Override

public Object front() {

queue.gotoHead();

return queue.getCurr();

}

}

/////////////////////Test.java//////////////////////////////

public class Test {

public static void main(String []args) {

LLQueue l = new LLQueue();

System.out.println("IsEmpty: "+l.isEmpty());

l.enqueue("one");

l.enqueue("two");

l.enqueue("three");

l.enqueue("four");

l.enqueue("five");

l.enqueue("six");

System.out.println("After Inserting elements");

System.out.println("IsEmpty: "+l.isEmpty());

while(!l.isEmpty()){

String s = (String)l.dequeue();

System.out.println(s);

}

System.out.println("After Deleting elements");

System.out.println("IsEmpty: "+l.isEmpty());

}

}

import javax.swing.JOptionPane; public class StackTest { public static void main(String[] args) { // Create a Stack Stack s = new ArrayStack(20); // NOTE: If I had a different stack implementation, // I could substitute it for ArrayStack. // Put some strings onto the stack JOptionPane.showMessageDialog(null, "About to push words onto stack: Once upon a time"); s.push("Once"); s.push("upon"); s.push("a"); s.push("time"); // Now pop them from the stack JOptionPane.showMessageDialog(null, "About to pop words from stack ..."); while(! s.isEmpty()) { String word = (String)s.pop(); // Note: have to cast Objects popped to String JOptionPane.showMessageDialog(null, "Word popped: " + word); } System.exit(0); } } 

import javax.swing.JOptionPane; public class QueueTest { public static void main(String[] args) { // Create a Queue Queue q = new ArrayQueue(); // Put some strings onto the queue JOptionPane.showMessageDialog(null, "About to enqueue words onto queue: The end is nigh!"); q.enqueue("The"); q.enqueue("end"); q.enqueue("is"); q.enqueue("nigh!"); // Now dequeue them from the queue JOptionPane.showMessageDialog(null, "About to dequeue the words ..."); while(! q.isEmpty()) { String word = (String)q.dequeue(); // Note: have to cast Objects popped to String JOptionPane.showMessageDialog(null, "Word dequeued: " + word); } System.exit(0); } }