Next in Line, Please

The Concept of Queues

Since the first day you went to the movies, you have been using queues. Here in the US we call what we do "standing in line"; however, in England and some other countries, it is called "standing in a queue" or just "queuing". The queue if is a First In First Out or FIFO operation where if you are first in line, you get the first ticket, second in line gets the next ticket, and so on. While you are at the front of the line getting your ticket, other folks are still arriving and they are getting in line at the end of the queue.

Going back to the blocks, consider a queue that has already started, shown here

When an item is removed from the "front" of the queue, this is called a dequeue process. In the case of this queue, the assumption is that the front is on the right. Take a look.

Next, consider adding an element to the end or back of the queue, which in this presentation is the left side of the image.

Do it again. Enqueue another value, which again will be appended to the back of the queue, or in this case, the left side of the queue

And for practice, dequeue one more value, which will be removed from the front of the queue, depicted by the right side of this image.

Like the stack, this is about it, and there isn"t anything terribly complicated about it. That said, the code can be a little more interesting for a queue when an array is used. That's up next.

Queues, with Arrays

Using an array with a queue is interesting because unlike the stack, the action doesn't always happen at the size position of the array. In fact, that doesn't happen often at all. To manage this with an array, the programmer has to be able to loop back to the beginning of the array, maintaining and updating a front index and back index with the operations. Consider the pseudo code for enqueuing here.

   // initially set the back index to -1
   // and the front index to 0
   // and initialize the size to zero

   // increment the front index, 
   // rolling it over to the beginning of the array
   // if it goes past the end

   // add the new value to the array at the back index
   // update the size

The back index must be incremented first, then the value can be added. Once the value is added the front and back indicies will both be zero, and correct for a queue of one item. Thereafter, each time another value is to be added, the back index must be advanced to a new back position where a new value can be placed. Note also that because this new back index might go off the end of the array, it must be rolled back around to the beginning of the array to continue. This is easily accomplished with modulo math. Now take a look at how an item is dequeued from the front of the queue.

   // Repeated here: initially set the back index to -1
   // and the front index to zero
   // and set the size to zero

   // first, check to make sure the size is greater than zero

   // get the value at the current front index

   // then increment the front index to go to the next available value
   // making sure to roll the index back to the beginning of the array as needed

   // then decrement the size

Queues, with Linked Lists

Much like stacks are very amenable to arrays, queues are quite easy to implement with linked lists. In a nutshell, you can insert new values at the head of a linked list and remove them from the end of the linked list, or you can do it the other way around. It doesn't matter. Inserting or removing from the head is quite easy to do, and inserting or removing from the tail just requires iterating (with or without recursion) to the end. You have already read about these operations in the Linked List chapter so there isn"t much more to discuss on that. Implementing a queue with a linked list is just plain (Geek) fun. Enjoy!

Wrapping Up Queues and Stacks

This is not a long chapter or pair of topics but the important thing about studying these is that you are responsible to know them in any Data Structures course, and you will very likely be challenged with questions on one or both of them in your interview(s). The good news is that they really are not difficult as long as you understand how they work, and you can think through how the data must be managed to accomplish pushing, popping, queueing, and dequeing. And you should be able to do that on the fly. It is very worth your while to work the stack and queue out with both arrays and linked lists both to help cement your knowledge, and to continue honing your programming chops. The fairly short time investment will pay you back. Next up is Binary Search Trees (BST). These are really interesting and will continue to make you a better programmer. Onward.