Computer Science Educators Stack Exchange is a question and answer site for those involved in the field of teaching Computer Science. It only takes a minute to sign up.
Sign up to join this community
When teaching computer programming, occasionally students who are interested in music ask instructors for how a double ended queue could be useful in the music industry.
What is a "real-world" or "real-life" application of double-ended queues and computer programming for people interested in music?
occasionally students who are interested in music ask instructors for how a double ended queue could be useful in the music industry.
This is a rather unusual situation and I'm surprised it arises for you often enough to ask about it here. You might want to elaborate more on why this particular question comes up so often (I'd expect it to come up, say, once in a teaching career). Do your culinary students ask where double-ended queues ("deques") show up in that field?
If there's no obvious application you can think of for deques in music, it's OK to say "there are no obvious applications I can think of for deques in music" rather than scraping around a mostly empty barrel and stretching the truth to come up with something.
Linked lists in general are low-level data structures primarily used in systems-level applications. Double-ended queues are even more specialized. They're basically unnecessary for most day to day, business application-level development. Most of the time, a simple array is sufficient, and most languages don't have deques built-in to the standard library (Java, Python and I think C++ and C# are exceptions that come to mind).
With that in mind, the operating system running your musical applications is very probably using them, as well as potentially the software running whatever audio system you're using, but that's low-level and perhaps unsatisfying, since the data structure is probably not doing anything obviously musical here.
Scoping appears to be necessary. "Music programming" is a large expanse ranging from extremely low-level DSP engineering all w to extremely high-level music creation applications like Audacity, Lilypond, Ableton, Cubase, Reaktor, etc. Middle-level applications like Max/MSP, Tidalcycles and Supercollider exist as well. Zooming out to "the music industry" is even broader, and linked lists and deques surely appear in operating systems of people working in the music industry (again, unsatisfying and vague, probably not what the asker wanted to hear).
If your students are asking about music-making techniques that could use linked lists or deques, you could probably treat a linear song structure as a sequence of linked nodes, but this isn't too helpful or interesting (and would probably involve duplicate nodes). Deques can be used for rotating purposes, which might imply a looping structure of some sort, but since this is so unusual and we're breaking a sweat to come up with something, we'd better just admit it. An array would be just as useful for storing, looping and forward/reversing a musical piece, with the bonus of constant-time random access. A deque is appropriate when you want to dequeue or prepend nodes to the front of a structure in constant time.
I'd suffice to say that deques are a fundamental data structure in the low-level systems world, and then ask the student which level of abstraction and what domain they're interested in (it could be they don't even care about music production, and just want to know whether a deque could be used in a playlist app, or something like that).
When a strange, overly-broad question arises, it's important to follow up and ask for clarification to understand what prompted the question and determine the motivation of the asker. Once the scope is appropriately refined and the intent is obvious, a satisfying answer will be much easier to provide.
I am hoping that someone else will post an answer better written than this one.
One application of double-ended queues to real-life musical applications is to make sure that an internet-based music playlist or internet based radio station does not play a song that was one of the most recent 10, 20, or 30 songs you heard.
from collections import deque
import random
class SongGetter:
# create a double-ended queue
forbidden_songs = deque()
@classmethod
def get_song_old_imp(cls):
"""
Faux implementation of how some internet radio service
or playlist shuffler currently gets music
This is a temporary place-holder of the code to be wrapped
"""
songs = [
"THE OFT REPEATED SONG",
"song1",
"song2",
"THE OFT REPEATED SONG",
"THE OFT REPEATED SONG",
"THE OFT REPEATED SONG",
"song3",
"song4",
"song5",
"THE OFT REPEATED SONG",
"THE OFT REPEATED SONG",
"THE OFT REPEATED SONG",
"song9",
"song10",
"THE OFT REPEATED SONG",
"THE OFT REPEATED SONG",
"song11",
"THE OFT REPEATED SONG",
"THE OFT REPEATED SONG",
"song12",
"THE OFT REPEATED SONG",
"THE OFT REPEATED SONG",
"song13",
"THE OFT REPEATED SONG",
"THE OFT REPEATED SONG",
"THE OFT REPEATED SONG",
"THE OFT REPEATED SONG",
"song14"
]
try:
song = songs[cls.old_song_idx]
except IndexError:
cls.old_song_idx = 0
song = songs[cls.old_song_idx]
cls.old_song_idx += 1
return song
old_song_idx = 0
@classmethod
def get_song_new_imp(cls):
"""
New Implementation of `Get a Song`
------------------------------------------
If
the new song is something we've listened to recently,
then
get a different song
"""
#
return cls.impimp()
@classmethod
def second_impimp(cls):
"""
"""
next_song = cls.get_song_old_imp()
while next_song in cls.forbidden_songs:
next_song = cls.get_song_old_imp()
cls.forbidden_songs.append(next_song)
# unban the oldest song in the set of all banned songs
cls.forbidden_songs.popleft()
return next_song
@classmethod
def first_impimp(cls):
"""
What to do the first time Starbucks Coffee opens in the morning
or the "radio"/internet playlist begins
"""
# get a song the old way you did last month
next_song = cls.get_song_old_imp()
while next_song in cls.forbidden_songs:
next_song = cls.get_song_old_imp()
cls.forbidden_songs.append(next_song)
if len(cls.forbidden_songs) >= 10:
# if we have banned (forbidden) 10 or more songs today
# we need to start un-banning the oldest banned song
cls.impimp = cls.second_impimp
return next_song
# `imp imp` is the `implementation of the implementation`
impimp = first_impimp
#####################################################333
for _ in range(50):
song = SongGetter.get_song_new_imp()
play(song)
Music is not my field, and I may be the least musical person you'd ever come across, but I remember that it was once a "thing" to play records backwards and look for satanic messages. Since you can iterate a doubly linked list from either end, such a list containing sufficiently short passages might serve for this.
Oddly enough, I am today building a circular linked list in Python out of double linked nodes to serve as either a stack or queue.
A DJ might find such a thing useful if the direction of iteration could be reversed at any moment.
Welcome to Heaven. Here is your harp. Welcome to Hell. Here is your accordion.
(source: Far Side comics)
As a kid, my instrument was accordion (badly played).
Repeat signs, Segno, Coda, are all examples of linking of sections. The "London Manuscript" (https://imslp.org/wiki/Manuscript,_GB-Lbl_Add._MS_29987_(Various)) even contains many directions "when you get here jump to there", giving in fact a DAG rather than a list.
