Here’s another fun simple data structure challenge.
The challenge:
To solve this challenge, we must first take each character in s, enqueue it in a queue, and also push that same character onto a stack. Once that’s done, we must dequeue the first character from the queue and pop the top character off the stack, then compare the two characters to see if they are the same; as long as the characters match, we continue dequeueing, popping, and comparing each character until our containers are empty (a non-match means s isn’t a palindrome).
I’ll start by reading up on this type of data structure. I thought this and this explained to me what I needed to know.
I can initialize both the stack and queue variables as lists.
class Solution:
def __init__(self):
self.stack = []
self.queue = []
# create the method that accept the characters in s
def pushCharacter(self, char):
# now we append the character to the top of the stack
self.stack.append(char)
# create another method that accept the characters in s
def enqueueCharacter(self, char):
# now we use insert (rather than append) so that the newest
# addition will always be at index 0
self.queue.insert(0, char)
# pop stack method
def popCharacter(self):
# simple method to return
return self.stack.pop()
# pop queue method
def dequeueCharacter(self):
# simple method to return
return self.queue.pop()
So this is the completed code without comments:
class Solution:
def __init__(self):
self.stack = []
self.queue = []
def pushCharacter(self, char):
self.stack.append(char)
def enqueueCharacter(self, char):
self.queue.insert(0, char)
def popCharacter(self):
return self.stack.pop()
def popCharacter(self):
return self.stack.pop()