A Queue in C#

A queue (pronounced as one would the letter ‘Q,’ although the grad student who taught my Data Structures course was fond of saying ‘kway-way’ to remind us of the spelling) is analogous to a stack, but our access to the data is at the element first added, not the element most recently added. It’s just like the line at McDonald’s or at the bank or a queue in Britain, where imitating data structures is a national pastime. Instead of being named ‘push’ and ‘pop,’ the operations are called ‘enqueue’ and ‘dequeue.’

queue

 

Queues are a very ‘fair’ means of determining priorities. As already mentioned, we use them to determine who is served next at a restaurant. A printer uses a queue to determine which job to handle next, in case multiple jobs are submitted while another is being handled.

Like a stack, a queue is implemented atop the scaffold of another data structure, like a list or an array. Since I did the linked list in C#, and we’re back around to C# in this example, I’ve built my toy queue on my own toy linked list, rather than using .Net’s built-in linked list:

As you can see, my earlier laziness in not fleshing out the linked list’s optional functionality made matters a bit more complicated. If the linked list tracked its last element and offered the ability to delete from either end, the dequeue method could be a bit simpler. As it stands, we have to walk through the entire queue every time we want to dequeue anything. It’s as if our maître d’ or bank teller starts at the end of the line, asking each customer “Was anyone here before you?” and determining whom to serve that way.

We also add another little test to our DataStructureTesters project:

Which gives the expected output: