Close
Register
Close Window

BM40A1500 Data Structures and Algorithms

Chapter 2 Linear Data Structures

Show Source |    | About   «  2.6. Linked Stacks   ::   Contents   ::   2.8. Linked Queues  »

2.7. Queues

2.7.1. Queue Terminology and Implementation

Like the stack, the queue is a list-like structure that provides restricted access to its elements. Queue elements may only be inserted at the back (called an enqueue operation) and removed from the front (called a dequeue operation). Queues operate like standing in line at a movie theater ticket counter. If nobody cheats, then newcomers go to the back of the line. The person at the front of the line is the next to be served. Thus, queues release their elements in order of arrival. In Britain, a line of people is called a “queue”, and getting into line to wait for service is called “queuing up”. Accountants have used queues since long before the existence of computers. They call a queue a “FIFO” list, which stands for “First-In, First-Out”. Here is a sample queue ADT. This section presents two implementations for queues: the array-based queue and the linked queue.

2.7.2. Array-Based Queues

The array-based queue is somewhat tricky to implement effectively. A simple conversion of the array-based list implementation is not efficient.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit


Settings

Proficient Saving... Error Saving
Server Error
Resubmit


Settings

Proficient Saving... Error Saving
Server Error
Resubmit

2.7.3. The Circular Queue

Settings

Proficient Saving... Error Saving
Server Error
Resubmit


Settings

Proficient Saving... Error Saving
Server Error
Resubmit

If the value of front is fixed, then \(n+1\) different values for rear are needed to distinguish among the \(n+1\) states. However, there are only \(n\) possible values for rear unless we invent a special case for, say, empty queues. This is an example of the Pigeonhole Principle. The Pigeonhole Principle states that, given \(n\) pigeonholes and \(n+1\) pigeons, when all of the pigeons go into the holes we can be sure that at least one hole contains more than one pigeon. In similar manner, we can be sure that two of the \(n+1\) states are indistinguishable by the \(n\) relative values of front and rear. We must seek some other way to distinguish full from empty queues.

One obvious solution is to keep an explicit count of the number of elements in the queue, or at least a Boolean variable that indicates whether the queue is empty or not. Another solution is to make the array be of size \(n+1\), and only allow \(n\) elements to be stored. Which of these solutions to adopt is purely a matter of the implementor’s taste in such affairs. Our choice here is to use an array of size \(n+1\).

   «  2.6. Linked Stacks   ::   Contents   ::   2.8. Linked Queues  »

nsf
Close Window