QuestionQuestion

Assignment 7: Implementing Palindromes

Purpose:
The primary focus of Module Seven is the implementation of lists, stacks, queues, and priority. In programming terms, a queue is a data structure in which elements are added to one end and removed from another other end. The queue ADT is referred to as a FIFO (First In, First Out) data structure, meaning that elements are added to the queue's rear, one at a time, and are removed in the same order of which they were added. In other words, the queue ADT works like a lunch line in a cafeteria; people enter the rear of the line and must wait their turn to be served. The person at the very front of the line is served first and exits the line, allowing the next person in line to be served next. Whoever was the very last person to enter the line will be served last. As a matter of convention, the side of a queue in which objects are inserted is called the "rear" of the queue, and the side in which objects are removed is called the "front" of the queue; to "enqueue" an object means to insert it at the rear of a queue, and to "dequeue" an object means to remove it from the front of a queue.

As with the stack ADT, the queue is a very popular and widely used data structure. Every time you use a computer, you are seeing the queue in action. The Windows Operating System, for example, uses a queue to store input received from the keyboard and mouse, as well as messages that are posted from applications. Each time a key is pressed on the keyboard, or a button on the mouse is pressed, or a program posts an event to be processed, Windows enqueues the event onto the Windows Message Queue. As long as Windows is running, it cycles through a continuous loop that processes events in the queue. The purpose of this is to maintain a chronological order of events, so that those events are always processed in the same order that they occurred. In other words, even if the system becomes overwhelmed by a bombardment of messages, it can (at least) process those messages in the correct order, though the messages might be processed rather slowly. If Windows did not use a queue to store messages and, instead, tried to process every event as soon as it occurred, the system would quickly overwhelm itself. Think about it like this: if thirty people were standing around you, yelling chores for you to complete, how many of those chores would you even be able to remember? Alternately, if those thirty people each wrote their requests, one at a time, on a list, how much of a better chance would you have of completing the chores? Just like you, a computer has its limitations; if a computer is bombarded by a large amount of requests at the same time, it will not be able to process them all. However, if a computer stores each request onto a queue, it can at least respond to each request when it has the chance to do so. It is for this reason that operating systems, such as Windows, use a queue to process events. Without the queue ADT, computers would be outrageously unreliable.

In this assignment, students will use the version of the queue ADT in the form of a Java interface provided in the book in section 7.5 called GenericQueue which implements the queue ADT and provides queue functionality to a linked list data structure. Remember to add an "isEmpty()" function to check whether the queue is empty. Students will use the GenericQueue in combination with a stack-type data structure called GenericStack in order to solve a problem that requires both ADT's. Remember to add a function "isEmpty()" to check whether a stack is empty. Before attempting the assignment, students should carefully read and study Module 7 in the textbook. After the assignment has been completed, students should take the Module Seven Self Test, which can be found in the Content menu of the course web site. Students should complete the Self Test a number of times until they feel comfortable with the material and are prepared to complete the graded exam for Chapter Seven, which can be found in the Quizzes menu on the course web site.Students should note that the graded exam may be taken only twice, whereas the Self Test may be taken an infinite number of times, so be prepared!

Goals:

Through the completion of this assignment students should gain hands-on experience with the queue ADT -- its purpose and implementation. Students should learn how the fastest queue -- the linked list queue -- is designed and understand how this type of data structure combines the functionality of the queue ADT with the speed of linked list storage. Students should also understand that linked list technology can be applied to any data structure, including the stack ADT, in order to provide fast insertions and removals of objects.

Description:

The PEX7 class should be declared as a public class and should meet all the requirements listed below. Its purpose is to implement a main method which tests all of the files created in the Chapter Seven assignment. Basically, the main method should test an input string to determine whether the string is a palindrome. A palindrome is a sequence of characters that can be reversed to reveal the same sequence. For example, the word "racecar" is a palindrome; if you reverse the letters in the word "racecar", you end-up with the same word -- "racecar". The string "1234321" is also a palindrome, since the string can be reversed to reveal the same order of characters. However, the word, "cat" is not a palindrome, since the reversal of "cat" is "tac".

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

// Be sure to import java.util.Scanner at the top of the PEX7.java file.
import java.util.Scanner;

/**
*
* @author
*/
public class PEX7 {

    public static void main(String[] args) {
       String string;
       do {
            // Declare a Scanner object by passing System.in as a parameter to
            // the Scanner constructor.
            Scanner keyboard = new Scanner(System.in);
            //Declare an GenericStack, and instantiate it as a new GenericStack.
            GenericStack stack = new GenericStack();
            // Declare an QueueStack, and instantiate it as a new GenericQueue.
            GenericQueue queue = new GenericQueue();
            // Print a prompt to the user to enter a string that will be evaluated.
            System.out.println("Enter a string to be evaluated: ");
            // Get a String from the Scanner object by calling its nextLine() method.
            string = keyboard.nextLine();
            // Iterate through each character in the String,
            // placing each character onto the stack as well as onto the queue.
            for (int i = 0; i < string.length(); i++) {
                queue.enqueue(string.charAt(i));
                stack.push(string.charAt(i));
            }

            // Determine whether the String is a palindrome by comparing
            // each character popped off of the stack to each character
            // dequeued from the queue. Since the stack pops characters
            // in the reverse order of which they were added and the queue
            // dequeues characters in the same order in which they were added,
            // the characters from any normal String would not match;
            // only a perfect palindrome would pass the test.
            boolean isPalimdrome = true;
            while (stack.isEmpty() == false) {
                if (stack.pop() != queue.dequeue()) {
                   isPalimdrome = false;
                   break;
                }
            }...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$15.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats