Palindrome Using Stacks & Queues Hand up the solution to Q2 but not Q1 (which is
ID: 3727327 • Letter: P
Question
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 Java’s Character class to do this.
Submit a report with analysis/algorithm, implementation and testing, as you did for Assignments 1 and 2.
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());
}
}
//nodetest.java
//singley linked list implementation
//Singly Linked List Test Code
//defines a single node used in a Doubly Linked List
//Doubly Linked List Node
//Doubly Linked List Implementation
Explanation / Answer
Hello, I have already answered the same question before, so I’m referring my own solution here. There is no plagiarism.
// PalindromeCheck.java
import java.util.Scanner;
public class PalindromeCheck {
public static void main(String[] args) {
/**
* Defining an ArrayStack and ArrayQueue
*/
ArrayQueue queue;
ArrayStack stack;
/**
* Defining a Scanner for reading input
*/
Scanner scanner = new Scanner(System.in);
System.out.println("Enter a String: ");
String text = scanner.nextLine();
/**
* Initializing the stack and queue with max capacity = input string
* length
*/
queue = new ArrayQueue(text.length());
stack = new ArrayStack(text.length());
/**
* looping through all characters
*/
for (int i = 0; i < text.length(); i++) {
// getting the char at current position
char c = text.charAt(i);
// checking if it is an alphabet
if (Character.isLetter(c)) {
/**
* Adding to the queue and stack
*/
queue.enqueue(c);
stack.push(c);
}
}
/**
* characters are added to the stack and queue, now it is time to check
* if its palindrome or not. At this point,we assume that the text is
* palindrome
*/
boolean palindrome = true;
/**
* loops until the stack/queue is empty, we can use any of them as both
* of them will have the same size
*/
while (!stack.isEmpty()) {
/**
* popping the stack and dequeuing the queue
*/
Character c1 = (Character) stack.pop();
Character c2 = (Character) queue.dequeue();
/**
* comparing the two characters (case insensitive)
*/
if (Character.toLowerCase(c1) != Character.toLowerCase(c2)) {
/**
* mismatch found, the text is not palindrome, updating the
* variable and breaking the loop
*/
palindrome = false;
break;
}
}
/**
* if the palindrome variable is true after exiting the loop, it means
* that the text is palindrome, else not
*/
if (palindrome) {
System.out.println("'" + text + "' is a palindrome");
} else {
System.out.println("'" + text + "' is not a palindrome");
}
}
}
//Queue.java
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
}
// ArrayQueue.java
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];
}
}
// Stack.java
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)
}
// ArrayStack.java
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);
}
}
/*OUTPUT*/
Enter a String:
malayalam
'malayalam' is a palindrome
Enter a String:
some random text
'some random text' is not a palindrome
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.