Okay, welcome to the Section 20, Challenge 4 – Solution.
This is the challenge where we're trying to determine whether a string is
a palindrome using a stack and a queue.
So, before I go into the code, let's talk about the process
that we can use to do this.
Suppose we have a word like RADAR, that's the string,
obviously, that is a palindrome.
What we can do is we can have a queue over here, and we
can have a stack over here.
We can take these letters and push them to the queue.
So, it's going to be the r, the a, the d, the a, and the r,
that's the order we're putting them in.
So, this is the front of the queue here.
And then we can take the same word and push it on the stack.
So, in this case, we've got r, a, d, a, r,
so I think you know what's happening now.
This is the top of the stack, this is the front of the queue.
What we can do is we can take those elements and compare them.
If they're the same, we can knock them off.
Then we can go to the next one.
If they're the same, we move on to the next one.
And as you can see, it's pretty easy, right.
At the end, we're done.
If everything matched, we've got a palindrome.
So, that's it, let's take a look at another example.
So, let's say that the word is rear, r, e, a, r, obviously,
that is not a palindrome.
So, we can have our queue over here and we can have our stack over here.
And what we'll do is we 'll, in queue, rear.
So, it's r, e, a, r, this is the front.
And then we'll push rear onto the stack.
So, again, we'll say.
And I'll separate those, so make clear.
R, e, a, r, we'll look at the front of the queue and the top of the stack,
they match, so we can get rid of those.
Then we'll look at the front of the queue, top of the stack, they don't
match, that's not a palindrome.
Okay, so that's it, that's the solution.
It's pretty straightforward.
Now let's see how we do this in code.
Here is the function.
And let me walk you through it really quickly.
So, what I'm doing here is I'm using a range based for loop
to iterate over that string s that's being passed into me.
And for each character, I'm checking is it an alpha character, I'm
not interested in anything else.
If it is, I'm converting it to uppercase.
I'm pushing it on the queue, and then pushing it on the stack.
That's it, that's going to set up those two data structures, so that
I can process them easily now.
Now I'll scroll up and there's the rest of the code, you can see that I've got
two variables here, c1 and c2, that's where I'm reading the characters into.
And all iI'm doing is while the queue is not empty, I could have
used the stack as well here.
It doesn't really matter because they both have the same number of elements.
So, while the queue is not empty, I'm assigning the front of the queue
to c1, and then I'm getting rid of that character from the queue.
I'm assigning the top of the stack to c2 and I'm popping that off the stack.
Then I'm comparing the two characters.
If they're not the same, I'm out.
It's not a palindrome.
When I finish this, if I loop, and everything is done.
And I've got, I've processed all the characters, it must be
a palindrome, I return true.
That's it, and we'll run it just to be, let's build and run.
And there you go, those are the results.
You can see the a is true, the aa is true, abc here is false.
A bunch of these phrases are true.
And then obviously, this is a palindrome, and palindrome are
not palindrome, so we get a false.
So, that's it, you can see a whole bunch of different ways to
solve this palindrome problem.
We did it with a deque earlier.
We did it with a stack and a queue now.
And there's other solutions as well.
So, I hope you had fun doing this.
You can see that using stacks, and queues, and deques, and
all kinds of data structures are pretty fun actually.
Alright, so I'll see you in the next video.