Data Structures Demystified (Demystified)

You probably never thought that waiting in line in the supermarket would help you become a whiz at data structures, but it s a big help: the checkout line at a supermarket is similar to the way data structures are organized. We re the things organized by the supermarket line, and the same kind of organization is used for data within your program. The checkout line in your program is called a queue. In this chapter, you ll learn the ins and outs of implementing a queue within your program.

A Queue

A queue is like the checkout line at the supermarket where the first customer is at the front of the line, the second customer is next in line, and so on until you reach the last customer who is at the back of the line. Customers check out of the supermarket in the order they arrive in the line. That is, the first customer is the first one to check out. This is referred to as first in, first out (fifo).

The same concept applies to a queue in your program. A queue is a sequential organization of data. Data is accessible using fifo. That is, the first data in the queue is the first data that is accessible by your program. In this chapter, you will explore the simplest type of queue, a fixed size , first in, first out queue using an array. In Chapter 8, you will learn how to build a priority queue using a linked list. With a priority queue, the elements are removed based on two factors, the order they were placed in the queue and the priority of the element.

A Simple Queue vs. Priority Queue

Programmers use one of two kinds of queues depending in the objective of the program, a simple queue or a priority queue. A simple queue organizes items in a line where the first item is at the beginning of the line and the last item is at the back of the line. Each item is processed in the order in which it appears in the queue. The first item in line is processed first, followed by the second item and then the third until the last item on the line is processed. There isn t any way for an item to cut the line and be processed out of order.

A priority queue is similar to a simple queue in that items are organized in a line and processed sequentially. However, items on a priority queue can jump to the front of the line if they have priority. Priority is a value that is associated with each item placed in the queue. The program processes the queue by scanning the queue for items with high priority. These are processed first regardless of their position in the line. All the other items are then processed sequentially after high priority items are processed.

You ll learn how to create and use a priority queue in Chapter 8. For now, we ll keep things simple by creating and using a simple queue.

The Business of Queues

Queues are very important in business applications that require items to be processed in the order they are received. The supermarket checkout line is a queue that most of us have experienced , but you won t be creating a supermarket checkout line in a program unless the program is designed to simulate a checkout line.

In the real world, queues are used in programs that process transactions. A transaction is a set of information such as an order form. Transaction information is received by a program and then placed in a simple queue waiting to be processed by another part of the program.

Let s return to a supermarket to see how this works. The cash register is a computer that runs a transaction program that, among other things, processes the bar code on each product scanned at the checkout counter.

One of the first steps to processing the bar code is to look up the price. There could be 20 or more cash registers in a busy supermarket all trying to look up prices at the same time. However, the computer can process only one bar code at a time. The program that look ups prices manages the demand by using a simple queue in which each new request is placed at the back of the queue, and the program looks up the bar code that is at the front of the queue.

Many other applications use a simple queue to maintain the order in which to process items. These include programs that process stock and bond trades and those that process students registering for a course. Queues are also used within a computer to manage printing.

The Array and the Queue

Data organized by a queue may be stored in an array. The queue determines the array element that is at the front and back of the queue. The array is not the queue. Likewise, the queue is not the array. Both are two separate things. This is an important concept to grasp and one that may be difficult to understand at first.

Take a look at Figure 5-1 and you ll see how an array and a queue are different and yet are linked together to organize data. The array is pictured as a block of elements. The queue is pictured as a circle. The empty boxes are where values are stored in the queue, and the numbers correspond to the index of the array that is associated with the queue. To the right of the circle are three values. The front and back values store the index of the front and back of the queue. The size value is the number of elements in the queue, which is 8 in this example.

Figure 5-1: The queue is different from the array used to store data that appears in the queue.

Enqueue

A value is placed in the queue by performing the enqueue process, which consists of two steps. The first step is to identify the array element that is at the back of the queue. However, this is not necessarily the last element of the array. Remember that the queue is not the array. The back of the queue is calculated by using the following formula:

back = (back+1) % size

Figure 5-2 shows how to use the formula and gives the values for the front, back, and size of the queue. The front and back variables are set to zero because the queue is empty, and size is set to 8 because the array has 8 elements.

Figure 5-2: The enqueue process places a new value at the back of the queue.

The next box shows the formula that identifies the back of the queue and assigns it the value 90. To the right of this box is the same formula with variable names replaced by actual values. Let s take a closer look at this and see how the back of the queue is calculated.

The first operation occurs within the parentheses, where 1 is added to the value of the back variable. The modulus operator determines where the next element should be placed in the queue by performing an integer division and returning the remainder of the division.

Although we ve described a queue as a checkout line in the supermarket, a queue is actually circular. This is illustrated in the calculation used to determine the back of the queue, as shown here:

(7 + 1) % 8

When you get to the last element in the array at index 7, the calculation returns 0 (8 divided by 8 is 1 and the remainder is 0). So after the last element in the array, you come around to the beginning of the array as the back of the queue. As you ll see in the Queues Using an Array in C++ section of this chapter, you check to see if you re at the front of the queue before placing an item at the back of the queue so you don t overwrite the item at the front and corrupt the queue.

The second step is to assign the value 90 to array element 1. That is, place the value 90 at the back of the queue. Remember that values are added to the queue from the back just as you go to the back of the checkout line to wait your turn at the supermarket. Notice that the value 90 is assigned to the array in Figure 5-2.

Dequeue

Dequeue is the process that removes a value from the front of the queue. It is important to understand that the value is removed from the queue, not the array. The value always remains assigned to the array until the value is either overwritten or the queue is abandoned . You ll see how to do overwrite later in this chapter.

There are two steps in the dequeue process, as illustrated in Figure 5-3. The initial step is to calculate the index of the array element at the front of the queue using the following expression:

Figure 5-3: The dequeue process removes an item from the front of a queue.

front = (front+1) % 8

Notice that this expression is very similar to the expression used in the enqueue process to calculate the index of the array element at the back of the queue. The first operation in this expression increments the value of the front variable. As you can see in Figure 5-3, the front variable is assigned the initial value zero. Therefore, the result of the first operation is 1. The next operation is to apply the modulus operator, which is identical to the modulus operation performed in the enqueue process. The result of this operation is 1, meaning that the front of the queue is the array element whose index is 1. This value is then assigned to the front variable. Previously in this chapter, you learned that if you were at index 7 in the array, the result of this calculation would be 0 ((7+1)%8 = 0), so you would chase the queue around in a circle.

The final step in the dequeue process is to use the value located at the front of the queue. Typically, the dequeue process is a method, and the front of the queue is returned to the statement that called the method.

In Figure 5-3, the array element values[1] is at the front of the queue. The value assigned to this element is 90, which was placed at the back of the queue by the previous enqueue process.

Notice that the value 90 remains assigned to the values[1] array element in Figure 5-3 because values assigned to the array associated with a queue are not affected when a value is removed from the front of the queue. The queue keeps track of array elements that are at the front and back of the queue, not the front or back of the array. In this case, we re using a simple integer array to illustrate the principles behind implementing the queue data structure. You may come across more complex implementations , where each element in the array is a pointer to a class object or structure. In these cases, you should be concerned about memory management when you perform enqueue and dequeue operations.