First Things First
In my last article I wrote about stacks, a “LIFO” or “last-in, first-out” data structure, and I gave you my implementation of a stack that could be used as a library script. This time we’ll be looking at queues and their big brother, the priority queue.
As you may remember, the stack functions like a stack of blocks or plates. The item on the top of the stack is the only item available to be removed, and it is the last item that was put there. Processors make use of stacks and so do some programs, like the Tower of Hanoi puzzle.
But there are times when we don’t want the last item we had, we want the first item that came to us. This sort of logic, not surprisingly, is called “FIFO” or “first-in, first-out.” This is the idea behind a queue, much like a line of people waiting to buy movie tickets. If you were standing somewhere in the middle of the line, you’d think it terribly rude if the folks who were last in line got served before you did! Our life experience tells us that the person who waited longest, at the front of the line, should be helped first.
The most common implementation of a queue in almost any computer with a graphic interface is the event queue. The Mac OS (both 9 and X) monitor the keyboard and mouse for events along with the I/O ports and even applications. As these events happen, they are logged in the OS’s event queue. Then, the OS uses idle times to “parcel out” these events to the correct receiver (an OS function or your program). In fact, the very thing that makes Applescript so powerful is it’s use of “Apple events” that are placed in the event queue along with all the keypresses and mouse clicks. These Apple events are generated when you write things like this:
tell application "iTunes"
activate
end tell
In your own programs, whether they are simple scripts or full-fledged Applescript Studio applications, you can use queues to help make your programming more intelligent. For example, you could write a program that lets the user select tracks to play in iTunes and store them in a queue to be run later, say in an alarm or sleep to music script.
The queue implementation is almost the same as our stack implementation, with one thing changed. In the stack, we placed new items at the front of the stack and pulled items from the front also. In our queue implementation, we’ll place new items at the END, but still pull items from the front. That’s the only real difference. I’ve changed the handler names to reflect that we’re using queues in case you need to use both stacks AND queues in the same program. Like stacks, we need handlers for emptiness, adding and removing items, and “peek”-ing at the first item without removing it. Our queue implementation (taken from my Nite Flite Library of scripts) looks like this:
property newqueue : {}
property queueResult : {}
on queueIsEmpty(theQueue)
--returns true if queue is empty, else false
if length of theQueue is 0 then return true
return false
end queueIsEmpty
on enqueue(theQueue, theData)
--returns the new queue (old queue+item)
set end of theQueue to theData
return theQueue
end enqueue
on dequeue(theQueue)
if queueIsEmpty(theQueue) then
return {}
else
set queueResult to item 1 of theQueue
return (rest of theQueue)
end if
end dequeue
on qPeek(theQueue)
if queueIsEmpty(theQueue) then
set queueResult to {}
return false
else
set queueResult to contents of first item of theQueue
return true
end if
end qPeek
And here’s our script to test the new handlers:
--load the library
set scriptPath to (path to scripts folder from user domain) & "Script Library:"
set queueLib to load script ((scriptPath as text) & "queueLib.scpt") as alias
--create a new queue
copy queueLib's newqueue to myqueue
--load the queue
repeat with myValue from 1 to 5
display dialog "Enqueue " & myValue
set myqueue to queueLib's enqueue(myqueue, myValue)
end repeat
--unload: notice the values are in the same order they
--went into the queue (fifo)
repeat while not (queueLib's queueIsEmpty(myqueue))
set myqueue to queueLib's dequeue(myqueue)
set myResult to queueLib's queueResult
display dialog "Dequeue " & myResult
end repeat
Getting Your Priorities in Order
The priority queue is a special adaptation of the queue idea. Going back to our example of people standing in line, let’s pretend we’re not waiting for movie tickets, but to be seated at a popular restaurant. Some restaurants take reservations and those who are smart enough to make a reservation get seated before those who decided to eat there at the last minute.
The people who thought to reserve a table have a higher priority in the eyes of the restaurant ma’tre d’ than those who didn’t. By the same token, there are times when you want higher priority tasks to “bubble up” to the top of the queue while still keeping items with the same priority in order.
Mac OS X, being a unix variant, uses priorities to decide what programs get the most processor time. Another use would be any program that runs tasks on a schedule. Using priority queues, the time that the task is to run is the priority and the task itself is the data.
We have a little bit more work to do in a priority queue than a regular queue, since we now have to deal with priorities as well as the actual data. In our implementation, also taken from the Nite Flite Library, we use a record declaration that will be used for every item in the priority queue:
property newPQItem : {priority:0, cargo:""}
And we need to revise our enqueue handler so that it places new items in the priority queue at their proper spot:
on priEnqueue(thePriQueue, theData, thePriority)
--returns thePriQueue after adding theData using thePriority to
--decide where to insert theData
set newPQItem to {priority:thePriority, cargo:theData}
if priQueueIsEmpty(thePriQueue) then
set end of thePriQueue to contents of newPQItem
else
set lastItem to length of thePriQueue
if lastItem = 0 then
set beginning of thePriQueue to contents of newPQItem
else if priority of newPQItem < priority of first item of thePriQueue then
set beginning of thePriQueue to contents of newPQItem
else if priority of newPQItem > priority of last item of thePriQueue then
set end of thePriQueue to contents of newPQItem
else
set insertHere to 1
repeat while ((priority of item insertHere of thePriQueue) is not greater than priority of newPQItem) and insertHere is not greater than lastItem
set insertHere to insertHere + 1
end repeat
set thePriQueue to ((items 1 thru (insertHere - 1)) of thePriQueue) & contents of newPQItem & (items insertHere thru lastItem of thePriQueue)
end if
end if
return thePriQueue
end priEnqueue
Other than changing the names of the other handlers to reflect the fact that we’re dealing with priority queues instead of queues, the rest of the queue implementation remains basically the same. For that reason, I’ll leave it as an exercise for you to write the rest of the handlers for priority queues and come up with a script that uses the new library. (Or you can download Nite Flite and use mine.)
More Information
For more information about data structures, check out these articles:
Wikipedia - Stacks
Wikipedia - Queues
Wikipedia - Queueing Theory
Wikipedia - Priority Queues
Wikipedia - Data Structures