Question

Suppose we have two String objects and treat the characters in each string from beginning to end in the following way: With one string, we push each character on a stack. With the other string, we add each character to a queue. After processing both strings, we then pop one character from the stack and remove one character from the queue, and compare the pair of characters to each other. We do this until the stack and the queue are both empty. What does it mean if all the character pairs match?

Answer 1

If all the character pairs match after processing both strings, one string in stack and the other in queue, then this means one string is the reverse of the other.

Step-by-step explanation:

Lets take an example of two strings abc and cba which are reverse of each other.

string1 = abc

string2 = cba

Now push the characters of string1 in stack. Stack is a LIFO (last in first out) data structure which means the character pushed in the last in stack is popped first.

Push abc each character on a stack in the following order.

c

b

a

Now add each character of string2 in queue. Queue is a FIFO (first in first out) data structure which means the character inserted first is removed first.

Insert cba each character on a stack in the following order.

a b c

First c is added to queue then b and then a.

Now lets pop one character from the stack and remove one character from queue and compare each pair of characters of both the strings to each other.

First from stack c is popped as per LIFO and c is removed from queue as per FIFO. Then these two characters are compared. They both match

c=c. Next b is popped from stack and b is removed from queue and these characters match too. At the end a is popped from the stack and a is removed from queue and they both are compared. They too match which shows that string1 and string2 which are reverse of each other are matched.