Data Structures and Algorithms |
6 Queues |
Queues are dynamic collections which have some concept of order. This can be either based on order of entry into the queue - giving us First-In-First-Out (FIFO) or Last-In-First-Out (LIFO) queues. Both of these can be built with linked lists: the simplest "add-to-head" implementation of a linked list gives LIFO behaviour. A minor modification - adding a tail pointer and adjusting the addition method implementation - will produce a FIFO queue.
Once we have written an O(1) method, there is generally little more that we can do from an algorithmic point of view. Occasionally, a better approach may produce a lower constant time. Often, enhancing our compiler, run-time system, machine, etc will produce some significant improvement. However O(1) methods are already very fast, and it's unlikely that effort expended in improving such a method will produce much real gain!
AsideThe great majority of computer systems would fall into the broad class of information systems - which simply store and process information for the benefit of people who make decisions based on that information. Obviously, in such systems, it usually doesn't matter whether it takes 1 or 100 seconds to retrieve a piece of data - this simply determines whether you take your coffee break now or later. However, as we'll see, using the best known algorithms is usually easy and straight-forward: if they're not already coded in libaries, they're in text-books. You don't even have to work out how to code them! In such cases, it's just your reputation that's going to suffer if someone (who has studied his or her algorithms text!) comes along later and says"Why on earth did X (you!) use this O(n2) method -Of course, hardware manufacturers are very happy if you use inefficient algorithms - it drives the demand for new, faster hardware - and keeps their profits high! |
There is a structure which will provide guaranteed O(logn) performance for both insertion and deletion: it's called a heap.
Key terms |
|
Continue on to Heaps | Back to the Table of Contents |