{

nextChar = i

th character of someString

aQueue.enqueue(nextChar)

aStack.push(nextChar)

}

// Compare the queue characters with the stack characters

charactersAreEqual = true

while (aQueue is not empty and charactersAreEqual)

{

queueFront = aQueue.peekFront()

stackTop = aStack.peek()

if (queueFront equals stackTop)

{

aQueue.dequeue()

aStack.pop()

}

else

charactersAreEqual = false

}

return charactersAreEqual

Question 3

Trace the palindrome-recognition algorithm described in this section for each of the following strings of characters:

a. abcda

b. radar

Question 4

Improve the palindrome-recognition algorithm described in this section by adding the first length / 2 characters to the queue and then pushing the remaining characters onto the stack.
 

Transcribed Image Text:

Recall from Section 5.1.2 in Chapter 5 that a palindrome is a string of characters that reads the same from left to right as it does from right to left. In Chapter 6 you learned that you could use a stack to reverse the order of occurrences. You should realize by now that you can use a queue to preserve the order of occurrences. Thus, you can use both a queue and a stack to see whether a string is a palindrome. As you traverse a string from left to right, you can add each character to both a queue and a stack. Figure 13-3 illustrates the result of this action for the string "abcbd which is not a FIGURE 13-3 The results of inserting the characters a, b, c, b, d into both a queue and a stack String: Queue: Stack: abcbd abcbd Top Front Back palindrome. You can see that the first character in the string is at the front of the queue and the last character in the string is at the top of the stack. Thus, characters removed from the queue will occur in the order in which they appear in the string, and characters removed from the stack will occur in the opposite order. Knowing this, you can compare the characters at the front of the queue and the top of the stack. If the characters are the same, you can remove them. You repeat this process until the stack and the queue become empty, in which case the original string is a palindrome, or the two characters are not the same, in which case the string is not a palindrome. The following is a pseudocode version of a nonrecursive recognition algorithm for the language of palindromes: // Tests whether a given string is a palindrome... isPalindromelsomeString: string): boolean // Create an empty queue and an empty stack aQueue = a new empty queue aStack = a new empty stack // Add each character of the string to both the queue and the stack length = length of someString for (i=1 through length) Recall from Section 5.1.2 in Chapter 5 that a palindrome is a string of characters that reads the same from left to right as it does from right to left. In Chapter 6 you learned that you could use a stack to reverse the order of occurrences. You should realize by now that you can use a queue to preserve the order of occurrences. Thus, you can use both a queue and a stack to see whether a string is a palindrome. As you traverse a string from left to right, you can add each character to both a queue and a stack. Figure 13-3 illustrates the result of this action for the string "abcbd which is not a FIGURE 13-3 The results of inserting the characters a, b, c, b, d into both a queue and a stack String: Queue: Stack: abcbd abcbd Top Front Back palindrome. You can see that the first character in the string is at the front of the queue and the last character in the string is at the top of the stack. Thus, characters removed from the queue will occur in the order in which they appear in the string, and characters removed from the stack will occur in the opposite order. Knowing this, you can compare the characters at the front of the queue and the top of the stack. If the characters are the same, you can remove them. You repeat this process until the stack and the queue become empty, in which case the original string is a palindrome, or the two characters are not the same, in which case the string is not a palindrome. The following is a pseudocode version of a nonrecursive recognition algorithm for the language of palindromes: // Tests whether a given string is a palindrome... isPalindromelsomeString: string): boolean // Create an empty queue and an empty stack aQueue = a new empty queue aStack = a new empty stack // Add each character of the string to both the queue and the stack length = length of someString for (i=1 through length)