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 senqueue 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

  • 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

  • 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

  • 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

  • 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()

Day 15: Linked List – 30 Days of Code

I’ve been doing the 30 Days of Code challenge at HackerRank. My python skills are being tested and it’s helping use the language to the fullest. On this day, I’ve come across linked lists. This is in data structure/algorithm territory and that means it’s scary. I wont be scared though.


Task
Complete the insert function in your editor so that it creates a new Node (pass data as the Node constructor argument) and inserts it at the tail of the linked list referenced by the head  parameter. Once the new node is added, return the reference to the head node.

And this is the code given to me:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None 
class Solution: 
    def display(self, head):
        current = head
        while current:
            print(current.data, end=' ')
            current = current.next

    def insert(self, head, data): 
        #Complete this method

mylist= Solution()
T = int(input())
head = None
for i in range(T):
    data = int(input())
    head = mylist.insert(head,data)    
mylist.display(head)

Where to start?

This video helped me a lot!

What is known?

  • class Node
    – Two attributes (data, next)
  • class Solution
    – Two functions (display, insert)

How to insert a new node into a linked list?

I started by looking if there was a preexisting head. If not, it becomes the head.

def insert(self, head, data): 
    # if the head doesn't exist
    if (head == None):
        # the head becomes a new object (the first!)
        head = Node(data)

Now there is a head. What happens next?

Well now I can use the nifty instance variable ‘next’ to see if it’s vacant. If so, this code will make the next node in the list

def insert(self, head, data):   
    if (head == None):
        head = Node(data)

    # if the next head doesn't exist
    elif (head.next == None):
        # make this new input a new Node object
        head.next = Node(data)

I just need to add a nice recursive else clause as a catch-all and a return to tidy it all up.

def insert(self, head, data):   
    if (head == None):
        head = Node(data)
    elif (head.next == None):
        head.next = Node(data)

    else: 
        # if there are already multiple nodes
        # shift the head to the next head and restart
        # until one of the if statements apply
        self.insert(head.next, data)

    # when there is no more input data
    return head

Linked lists are pretty much the beginning of data structures for me. They seem to be extremely important in the field I’m studying for: computer science. So I want to be prepared for future interviews. I’ve heard they ask many questions involving that data structures/algorithms.