Queues, Priority Queues, and Bags

Queues

In the U.S., people stand "in line" to check out at the grocery store, board a plane, or to watch a movie. The British stand in "queues" to do the same thing. What characterizes a queue is that arriving customers always go to the "end of the line", while the next customer to be served is always taken from the "front of the line". More generally, customers are always served in the order in which they arrived.

There are times when data or objects must be similarly stored in a "queue", until they can be processed later. This often happens when one process generates data for another process, but the two processes run independently -- and at possibly different rates of speed. Examples include: print jobs being sent to a printer, or a web server trying to fulfill incoming requests for documents, or even the processing of characters typed from a keyboard.

In computer science, a queue is an abstract data type that can help in these (and other) circumstances. Queues are collections where the data they store are stored sequentially, and additions and removals are done in a First-In-First-Out (FIFO) manner.

In a queue, we call the method that adds something to the queue enqueue() and the method that removes something from the queue dequeue(). Having a method that can check if the queue is empty is also necessary so that one doesn't try to dequeue and element that is not present (an underflow error).

Similar to stacks, a queue should generally not have a fixed capacity. That is to say, regardless of how many elements are in the queue, one should always be able to enqueue another.

When using an array to store the contents of a queue, one should be aware that it is not necessary to copy items towards the head of the queue to accomplish a dequeue. Instead, the simple trick of turning the array into a closed circle by computing indices modulo the size of the array, and letting the head and tail drift around endlessly in that circle makes it unnecessary to ever move items stored in the array. Of course, when the array ultimately fills, it can be resized in much the same way as resizing arrays can be used to implement stacks.

Linked lists provide a very efficient alternative to arrays when implementing a queue.

Priority Queues

A priority queue is an abstract data type similar to a queue in that it can serve as a "holding area" for data or objects before they are processed in some way. However, unlike a queue where items are processed in the same order in which they were enqueued, in a priority queue each item has some associated priority level, and items are processed in order of priority. As a (somewhat somber) real world example, one sees this type of organization in the process of medical triage following some natural disaster or other mass casualty/fatality event. In these situations, patients are not treated in the order they arrive at the hospital, but rather in an order based on the severity of their condition. Each patient is given some tag or wristband like those shown at right to indicate their priority level, so that medical practitioners know who to treat next.

One place where a priority queue is often needed is in the process manager of an operating system. Lots of tasks/users are vying for limited resources. How should the operating system choose which task should be executed next? FIFO is a possibility - but not the most practical. One long task could prevent many short (but potentially important) ones from being accomplished. By assigning priorities to the tasks and using a priority queue, time can be used more wisely and disgruntled users can be kept at a minimum.

Priority queues can also be used to sort data.

The implementation of a priority queue can be accomplished in a variety of ways, including the use of heaps or arrays of queues (one for each priority level).

Bags

In stacks and queues, the order elements are added to the collection is important, as the order in which elements are removed is related to the order in which they are inserted. A bag is a type of collection for which the order of insertion is completely irrelevant. This might be due to a requirement that once items are added to a bag, they are not allowed to be removed. Alternatively, one might allow the removal of an occurrence of some particular item, but have no mechanism for removing the $k^{th}$ item added, regardless of $k$.

Bags generally allow for the collection of duplicate objects as well. When duplicates are disallowed, the collection might be better described as a set instead of a bag.

Using the name "bag" to describe this abstract data type, we again suggest a collection familiar to everyday experience. A bag of marbles provides a good mental image.

Bags turn out to be particularly useful to store incidence information in networks (i.e., information on whose connected to whom). For example, in a social network application like Facebook, one might keep for each account a "bag-of-friends".

The ways to implement a bag are extremely varied. Simple implementations can be accomplished with arrays or linked lists, while more sophisticated implementations might include binary search trees, hash tables, and other more complex data structures. As mentioned above, sometimes bags are restricted to simply accumulating objects (along with the means to iterate through those items collected), while other implementations allow for removal of specified items, or checking to see if a particular item is contained in the bag.