Blog

Checking for Musical Palindromes using Queues

Continuing with the discussion on queues, one easy type of question is Valid Palindrome. We can check if a string is a palindrome using a queue. The palindrome is defined as a string that, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, reads the same forward and backward. We can check if a string has alphanumeric characters using isalnum() and we can convert a string to lowercase letters using lower(). Additionally, we can use the deque class of queues (double-ended queues) to literally check both ends of the string.

Welcome to My Corner of the Internet

Hey, I’m Jami Nishelle — and this is my little corner of the internet.

I built this site because I believe in transparency, community, and sharing the creative process openly. That’s what the Open Source Artist movement is all about.

You’ll find my music here, updates on shows, and honest reflections on what it means to create independently. I hope it inspires you to make something of your own.

Peace and joy,

Queues with One Stack using Recursion and Generating Recursive Fractal Melodies

Photo by Daria Durand on Unsplash

Continuing with the discussion of interchanging stacks and queues, I want to dive into how to implement a queue with one stack. This implementation is a little tricky because it requires recursion. Recursion is an important computer science concept that is used in many divide-and-conquer strategies to solve hard problems. Recursion occurs when a function calls itself. To prevent having an infinite loop, every recursive function has a base case and a recursive case. The base case tells when to stop recursing and calling itself again. It’s usually some kind of if statement with the stopping condition and is the simplest version of the problem that you can solve directly without recursing further. The recursive case is the function calling itself.

Interchanging Stacks and Queues and Why it Might be Useful

Continuing with the discussion on queues, this is a good opportunity to talk about the key differences between stacks and queues since they have similar operations. In fact, you can implement a stack using queues, and you can implement a queue using stacks. Let’s walk through this in more detail.

To summarize the differences between stacks and queues:

Coding questions like implementing a stack using queues and implementing a queue using stacks can be done with one or two queues, or stacks, respectively.

Cue the queues

Photo by Xiangkun ZHU on Unsplash

Queues are data structures that follow the same principle as joining a line, which is “First-in, First-out,” or FIFO. Just like waiting in line, the first item in the queue is the first to leave the queue. It is the data structure that ensures fairness. We have the same three operations for queues that we use for stacks but what’s different are the locations of these operations:

Solving Min Stack to Find the Root of a Chord

Photo by freestocks on Unsplash

So far, in my previous posts on stacks, I have been discussing array-based stacks. Array-based stacks use a fixed size of memory. They are simple to create, but you can run into memory problems. One example is stack overflow. Max for Live is a platform to build your own instruments and effects in Ableton Live, a digital audio workstation (DAW). Max for Live is based on Max, a visual programming language used by musicians, artists, and designers to create interactive installations and performance tools. With Max, you connect objects with patch cords to process data, audio, and video. Stack overflow happens when you overload Max with the list of things (aka a stack) that Max has to do, eventually overflowing the amount of memory space available. One way that this can happen is through an infinite loop. It causes Max to shut down its internal scheduler and stop performing operations. What we need is dynamic memory for these stacks, so that memory can expand as needed. How might we do this? Using linked lists! Check out my previous posts on linked lists to learn more about them.