Chapter 8: Queues Using Linked Lists


Did you ever get ready to queue up to buy tickets for a hot concert, only to stand in the parking lot because there wasn t room at the ticket counter to accommodate all the fans? This is a common scenario, but you may not realize that programmers experience a similar problem storing data using queues: there is not enough room on the queue for all the data (just like the problem with all the fans) that must be processed . Box office staff still wrestle with this problem, but programmers have arrived with a solution: they use a linked list to create a queue. In this chapter, you ll learn how and when to use a linked list to queue data.

A Queue

In Chapter 5, you learned that a queue is a sequential organization of data where data is accessible on a first in, first out (fifo) basis, which is similar to the line that you stand in to buy concert tickets.

The queue in Chapter 5 was created using an array to store data. As you ll recall, the array is separate from the queue. Data is assigned to elements of the array. The queue itself consists of two variables called front and back . Each points to the array element that is at the front of the queue or at the back of the queue. When data is removed from the front of the queue, the program changes the value of the front variable to point to the next array element. However, the data removed from the queue remains assigned to the array. That is, data isn t removed from memory.

There is a serious problem with using arrays to store data for queues: you must know the size of the array when you write the program. An array can store only a specific maximum number of elements at any point in time, similar to an architect designing a specific space for a box office that can accommodate a maximum number of fans at any point in time.

However, there is a difference between exceeding the number of array elements and overflowing the space around the box office: unlike the stadium, there is no parking lot for fans to gather in while waiting to get in the queue to purchase tickets inside a computer.

Programmers work around the size issue by using a linked list instead of an array when creating a queue. As you learned in previous chapters, a linked list can grow and shrink at runtime based on the needs of the application.




Data Structures Demystified
Data Structures Demystified (Demystified)
ISBN: 0072253592
EAN: 2147483647
Year: 2006
Pages: 90

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net