Chapter 16: The SureStop Utility
| ||||
| Copyright 1999 Sams Publishing |
| | ||
| | |
| Implementing a FIFO with an Array |
| | |
| You can implement a FIFO queue in many ways, including using a Vector , a linked list, an array, or any number of other options. In this chapter, I use an array of a fixed size to hold the elements. Because the array is fixed in size , the capacity of the FIFO is the length of the array. The capacity is the maximum number of elements that can be inside the queue at any one time. When all the array positions are filled, the FIFO is considered to be full . In addition, when the FIFO is full, calls to the add() method should block until space is available. |
| | |
| Space becomes available when another thread invokes the remove() method. The slots are reused when items have been removed so that the array can be thought of as circular after getting to the end, it wraps around to the beginning. |
| | |
| Figure 18.3 shows a FIFO implemented with an array that has a length of 5 . The cells are numbered from to 4 . The capacity is the maximum number of elements the FIFO can hold. In this case, capacity is 5 . The size is the number of elements currently being held inside the FIFO queue. In all FIFO queues, size is initially and can grow to a maximum value that equals capacity . |
| | |
 |
| | |
| Figure 18.3: A FIFO implementation that uses an array to hold the items. | |
| |
| | |
| Two indexes into the array are held: the head and the tail . The head points to the cell where the next element added will be put. An element may be added to the cell pointed to by head only when the FIFO queue is not full. The tail points to the cell that holds the next element to be removed. An element may be removed from the cell pointed to by tail only when the FIFO is not empty. Initially, both head and tail point to cell . |
| | |
| The first snapshot of the FIFO in Figure 18.3 shows an empty queue. The next snapshot shows how it looks after item S01 is added. You can see that size has increased to 1 , and that head now points to cell 1 ( capacity and tail remain unchanged). The third snapshot shows how the FIFO looks after item S02 is added. Notice that size has increased to 2 , and that head now points to cell 2 . The last snapshot of this figure shows how the FIFO looks after item S03 has been added. |
| | |
| Figure 18.4 continues this example. The first snapshot shows how the FIFO queue looks after one item has been removed. The item removed used to be in cell and was S01. As a result of this removal, size decreased to 2 , and tail now points to cell 1 . The second snapshot shows how the FIFO looks after item S04 has been added. The third snapshot shows the result of adding S05. The size has increased to 4 , and the head pointer wrapped around and now points to cell . When S06 is added, it goes into cell , and head moves over to point to cell 1 . At this time, both head and tail are pointing to the same cell. When the FIFO queue is empty or full, head and tail will point to the same cell. |
| | |
 |
| | |
| Figure 18.4: Adding and removing items with an array-based FIFO Queue. | |
| |
| | |
| Table 18.1 summarizes how a FIFO queue is implemented with a fixed-size array. |
| | |
| Table 18.1 An Array Implementation of a FIFO Queue: A Summary of Terms |
| | ||
|
| | |
| Term |
| | |
| Explanation |
| | ||
|
| | |
| capacity |
| | |
| The maximum number of items that can be held (the length of the array) |
| | |
| size |
| | |
| The current number of items in the queue |
| | |
| head |
| | |
| The index into the array where the next item will be added |
| | |
| tail |
| | |
| The index into the array where the next item will be removed |
| | |
| empty |
| | |
| When size is equal to |
| | |
| full |
| | |
| When size is equal to capacity |
| | ||
|
| |  | ||
| Toc | |||
