Stacks and queues are data structures that we can insert elements into and retrieve elements from. There are many forms of queues and stacks. The most common are the FIFO (First In First Out Queue and the LIFO Stack (Last In First Out). There are a few different ways to implement stacks and queues in SAS. We can use arrays or the fact that the Lag Function creates a static queue behind the scenes. However, no tool is better suited for a dynamic job like this than the hash object. In this post, I will create a simple FIFO Queue in SAS and explain the logic. Then, I will demonstrate a real-life example. Finally, I will guide you towards further reading material on other types of stacks and queues in SAS.
A FIFO Queue with the SAS Hash Object
Let us see how to implement a simple FIFO Queue in the SAS Data Step using the hash object. Without too much detail, the logic of inserting/withdrawing elements from a FIFO Queue is this. The element that is first added to the queue is the last one to leave it. The element that has been in the queue for longest is next in line to leave the queue. The correct terminology for adding/withdrawing elements from a queue is to queue and dequeue respectively.
In this example, I will keep things as simple as possible. In the code below, I use the putHash Macro to print the current content in the hash object. Compile the macro in the post if you want to. Otherwise, simply leave out that part. There are three main things to understand to create simple FIFO logic: The setup of an ordered hash object, how to queue and how to dequeue. Let us consider each point separately.
- In the code below, we create an ordered SAS hash object with the Ordered : ‘Y’ tag. This ensures that the hash object retrieves values in the ascending order of the key variable. In this case k. This is important because we can keep track of the order in which values enter the queue. And what value should be dequeued next. I must include the key variable in the data variables as well. Finally, I create a hash iterator object. With the iterator, I can easily find the ‘oldest’ element and dequeue it. See point three.
- Next, I queue the first item. I add 1 to the current value of k to ensure uniqueness. Next, I create the data value to be queued (d=100). Finally, I use the Add() Method to queue the item.
- The dequeuing part is a bit more tricky than the queuing part. I know that the oldest item in the queue has the lowest value of k. Ie it resides at the ‘top’ of the queue. Therefore, I can use the hash iterator to retrieve the corresponding value by calling the Next() and Prev() Methods in conjunction. I must call the Prev() Method because the iterator locks the hash object and prevents me from removing items from it as long as it resides inside the object. Finally, I call the Remove() Method to dequeue the item.
data _null_; declare hash h (ordered : "A"); /* Ordered hash to control FIFO Queue */ h.definekey ('k'); h.definedata ('k', 'd'); h.definedone (); declare hiter hi ('h'); k = sum(k, 1); /* Queue */ d = 100; h.add (); %putHash (h, k d); /* Display content of queue in the log */ k = sum(k, 1); /* Queue */ d = 200; h.add (); %putHash (h, k d); k = sum(k, 1); /* Queue */ d = 300; h.add (); %putHash (h, k d); rc = hi.next(); /* Dequeue */ rc = hi.prev(); h.remove(); %putHash (h, k d); k = sum(k, 1); /* Queue */ d = 400; h.add (); %putHash (h, k d); rc = hi.next(); /* Dequeue */ rc = hi.prev(); h.remove(); %putHash (h, k d); run; |
A Real Life Example
In the example above, I introduce the FIFO logick with a simple SAS code example. Recently, I replied to a thread at the SAS Community about a queuing model. Turn out the hash object was the perfect tool. Read the thread here.
Shortly put, the user has a list of upper/lower bounds in the data set market and a list of amounts that customers are willing to pay in the data set customers. The poster wants to go through each observation in the market data set and find the first customer that fits the interval. And then drop him from the queue. You can see the solution below. For a more detailed explanation of the code, read the thread at the SAS Communities. The logic is the same as the example above. However, I fill the queue using a DoW Loop. Also, I do not necessarily dequeue from the top of the queue. Rather, I dequeue the first customer that fits the condition ie. is inside the LB-UB interval.
data market; input UB LB; datalines; 137454.23 99272.50 127407.23 92016.34 134738.07 97310.83 118503.53 85585.88 117691.52 84999.43 126468.91 91338.66 138833.30 100268.50 ;;;; run; data customers; input pay; datalines; 117605 120194 114285 92316 125917 106480 94244 127482 94744 106371 122085 100327 107315 115530 116100 100279 94117 111069 98615 115879 124773 118694 111970 118629 129623 121400 100992 129743 93083 90643 ;;;; run; data want; format UB LB pay; keep UB LB pay; if _N_=1 then do; declare hash h(ordered:'Y'); h.definekey('k'); h.definedata('k', 'pay'); h.definedone(); declare hiter hi('h'); end; do k=1 by 1 until (lr1); set customers end=lr1; h.add(); end; do until (lr2); set market end=lr2; do until (LB <= pay <= UB | rc ne 0); rc=hi.next(); end; if rc=0 then do; output; _k=k; rc=hi.last(); rc=hi.next(); rc=h.remove(key: _k); end; else do; pay=.; output; rc=hi.last(); rc=hi.next(); end; end; run; |
Summary
In this post, I introduce the concept of Stacks and Queues in SAS. I demonstrate how the Hash Object is an ideal tool to implement such structures in SAS. We see a very simple example of FIFO logic and a real-life example of a queueing model from the SAS Community.
For futher reading on stacks and queues with the hash object, read chapter 10 of the great Data Management Solutions Using SAS Hash Table Operations. For more detail, read the article From Stocks to Flows: Using SAS® Hash Objects for FIFO, LIFO, and other FO’s by Mark Keintz.
Next week, you can read about how to Read Many Variables Into the SAS Hash Object.
You can download the entire code from this post here.