young nebula
my journey through computer science
Day 18: Queues and Stacks
How to Find Palindromes
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.
First Objective
- Create two instance variables: one for your stack, and one for your queue.
I can initialize both the stack and queue variables as lists.
class Solution:
def __init__(self):
self.stack = []
self.queue = []
Second Objective
- A pushCharacter() method that pushes a character onto a stack.
# 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)
Third Objective
- A enqueueCharacter() method that enqueues a character in the queue instance variable.
# 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)
Fourth Objective
- A enqueueCharacter() method that enqueues a character in the stack instance variable.
# pop stack method
def popCharacter(self):
# simple method to return
return self.stack.pop()
Fifth Objective
- A dequeueCharacter() method that dequeues and returns the first character in the queue instance variable.
# 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()
