Snake_Byte #27: The Double Deque-r: A Double-Stacked Sandwich Queue

Something I really enjoy about the PokitDok crew is that it's not difficult to find others willing to explore downtown and find a good deal for lunch. One of the places we frequent is Our Friendly Neighborhood Grocer, which has daily sandwich deals. We've already had some interesting programming adventures with Our Friendly Neighborhood Grocer (because when coders aren't coding, they're coding), so when they changed the way they organized the sandwich counter, it seemed like a natural fit to use it as an example for more educational Python goodness.

Lovely people in an orderly queue to get sandwiches.

Previously, Our Friendly Neighborhood Grocer had two sandwich queues: a queue at the counter for in-store sandwich orders, and a separate queue nearby for retrieving pre-ordered sandwiches from a basket. Recently, however, they made a significant change: they moved the pickup basket behind the counter. This effectively merged the two queues. Those who wish to order sandwiches at the counter still stand in line, but now those who have ordered ahead have to request their pre-ordered sandwich and enter at the front of the line.

It's sort of a queue, but it has additional rules now. What is it?

A close fit happens to be a data structure called a deque -- pronounced "deck", as the title implies. This is short for a Double-Ended Queue. A deque is basically a queue that allows items to be added to or removed from the front or the back of the queue. As such, it has the standard operations a queue has for enqueuing and dequeuing items, but it has the added concept of what "side" an operation is performed on. append() and pop() are operations that enqueue and dequeue items on the right side of the deque, and appendleft() and popleft() are operations that enqueue and dequeue items on the left side of the deque. This makes it a kind of hybrid between a queue and a stack, as it can either act as FIFO (first-in, first-out) or LIFO (last-in, first-out).

To demonstrate, let's start our sandwich line with three people in it. Imagine the front of our line starts on the right, so as the line grows, customers will be added on the left.

A new customer joins the line. As established, we enqueue them on the left.

The sandwich artist is ready for the first customer, so we dequeue the person at the front of the line, on the right.

A customer ordered online and arrives for pickup. They enter at the front of the line to request their prepared sandwich.

The sandwich artist, ready for another customer, serves the online order next.

A customer at the back, seeing the length of the line, decides they'd prefer sushi and leaves the line.

There are other convenient operations you can perform with deques. Venturing beyond what one would expect from a queue, deques also have an operation called a rotation. This allows one to rotate all the items in a deque a number of steps to the left or right. A positive number rotates the deque to the right, and a negative number rotates the deque to the left.

You can also check whether an element is in the deque like one would for a list.

Additionally, like lists, they're indexed starting at 0 from left to right. So, you can check which item is next on the left (or, for our example, who's the last in line)...

...or, you can start from the right with negatives and see which item is next on the right (who's first in line).

Those are the basics of deques. By combining rotations and the appropriate append()s and pop()s, and in some cases, by limiting the maximum number of items stored, you can perform a number of quick and thread-safe operations on the data you store in them.

As with all data structures, design plays a key part in whether it's the correct data structure to use. Unfortunately, for my example, the real sandwich line is true chaos, and people tend to leave, cut, and rearrange themselves randomly -- operations that would be O(n) complexity for the deque (unlike the standard operations, which are a lovely O(1)). However, in specific cases, like some job scheduling needs where tasks are both taken from the front of the line, "stolen" from the end, and no access to the middle is necessary, the deque is the way to go. For more information, check out the docs.

About Gini Harrison

Gini Harrison does her own stunts (for code and art, anyway) in Charleston, SC.

View All Posts

1 comment

    • Holly on April 8, 2017 at 8:03 pm

    Reply

    Brilliant, Ginikins!

Leave a Reply

Your email address will not be published.