|
Before the advent of standardized nuts and bolts, each nut would only fit the bolt for which it was made. As you can imagine, that made working on machinery very awkward. Ideally, machinery should be made using replaceable parts. The same principle applies to computer programs.
An abstract data type can be implemented in various ways. It should be possible to remove one implementation and replace it by another without changing any other modules, by ensuring that the new implementation shares the same interface as the old implementation.
To illustrate, we write an alternative implementation of queues. This implementation uses a different representation of the information, but it still offers type Queue, and all of the operations have the same visible effect as the previous implementation.
An alternative representation of a queue uses an array to hold the values in the queue. Imagine inserting 1, 2 and 3, in that order. The array would look like this, with extra empty space at the end to allow for more insertions.
-------
0 | 1 |
|-------|
1 | 2 |
|-------|
2 | 3 |
|-------|
| |
| ... |
| |
-------
If the program now removes 1 from the front of the queue, the array
looks as follows.
-------
0 | |
|-------|
1 | 2 |
|-------|
2 | 3 |
|-------|
| |
| ... |
| |
-------
It is important that we do not
move things around in the array when there is an insertion or
deletion, since that would take too much time. But then the front
of the queue is not necessarily at index 0. We need to keep
both the index of the front and the logical size the queue.
When the values in the queue reach the end of the array, they can wrap around to the beginning. After doing several insertions and deletions, the array might look as follows, with the front at index 99 and the logical size being 4. The queue holds [30, 40, 50, 60], from front to back.
-------
0 | 50 |
|-------|
1 | 60 |
|-------|
2 | |
|-------|
| |
| ... |
| |
|-------|
99 | 30 |
|-------|
100 | 40 |
-------
File queue.h describes the representation and operations.
(Not everything written in the header file is part of the interface. Type Queue is available to other modules but the fact that type Queue is a structure with a field called load is not part of the interface. The fact that we need to put that information in the header file is a defect of this way of doing things, and correcting that defect is one motivation for object-oriented programming. This course is not about object-oriented programming, however, so we accept the defect, but still insist that other modules should not make use of the details of the representation of type Queue.)
const int initQueueSize = 10;
struct Queue
{
int* contents;
int physicalSize; // Physical size of array contents
int load; // Logical size
int front; // Where the queue's contents start
Queue()
{
contents = new int[initQueueSize];
physicalSize = initQueueSize;
front = 0;
load = 0;
}
};
bool isEmpty (const Queue& q);
void insertAtEnd (int x, Queue& q);
int removeFirst (Queue& q);
int peek (const Queue& q);
#include "queue.h"
//=====================================
// isEmpty
//=====================================
// Return true if q is an empty queue.
//=====================================
bool isEmpty(const Queue& q)
{
return q.load == 0;
}
//=====================================
// enlarge
//=====================================
// Double the physical size of the
// array for queue q to make more room
// for insertions.
//=====================================
void enlarge(Queue& q)
{
int n = q.physicalSize;
//--------------------------------------------
// Copy the old array into a new array. Move
// the front to index 0 in the new array.
//--------------------------------------------
int* newA = new int[2*n];
for(int i = 0; i < n; i++)
{
newA[i] = q.contents[(q.front + i) % n];
}
//--------------------------------------------
// Install the new array.
//--------------------------------------------
delete [] q.contents;
q.contents = newA;
q.front = 0;
q.physicalSize = 2*n;
}
//=====================================
// insertAtEnd
//=====================================
// Insert x at the back of queue q.
//=====================================
void insertAtEnd(int x, Queue& q)
{
if(q.load == q.physicalSize)
{
enlarge(q);
}
int back = (q.front + q.load) % q.physicalSize;
q.contents[back] = x;
q.load++;
}
//=====================================
// peek
//=====================================
// Return the first item in queue q.
// If q is empty, return -1.
//=====================================
void peek(const Queue& q)
{
if(isEmpty(q))
{
return -1;
}
else
{
return q.contents[q.front];
}
}
//=====================================
// removeFirst
//=====================================
// Remove and return the first item in
// queue q. If q is empty, return -1
// and do not modify q.
//=====================================
void removeFirst(Queue& q)
{
if(isEmpty(q))
{
return -1;
}
else
{
int result = q.contents[q.front];
q.front = (q.front + 1) % q.physicalSize;
q.load--;
return result;
}
}
Explain why replacing the linked queue module with the array queue module will not require modifying any other module in your program. Answer
Is the array suitable for implementing a deque? See question queue1-4. Answer
When the array becomes full, our implementation of queues doubles the size of the array. Would it be more sensible to add just one more slot to the array, to conserve memory? Answer
(difficult) Function enlarge takes time. Does the need to call enlarge mean that operations no longer take constant time each?
Can you argue that n operations on a queue still take O(n) time, even taking the cost of enlarging the queue into account?
AnswerModify the Queue implementation so that, if the load becomes less than 1/4 of the physical size, it shrinks the array to have half the former size. Answer
|