Data-Structures-And-Algorithms-Alfred-V-Aho

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

shall use the following operations on queues.

1.MAKENULL(Q) makes queue Q an empty list.

2.FRONT(Q) is a function that returns the first element on queue Q. FRONT(Q) can be written in terms of list operations as RETRIEVE(FIRST(Q), Q).

3.ENQUEUE(x, Q) inserts element x at the end of queue Q. In terms of list operations, ENQUEUE(x, Q) is INSERT(x, END(Q), Q).

4.DEQUEUE(Q) deletes the first element of Q; that is, DEQUEUE(Q) is DELETE(FIRST(Q), Q).

5.EMPTY(Q) returns true if and only if Q is an empty queue.

A Pointer Implementation of Queues

As for stacks, any list implementation is legal for queues. However, we can take advantage of the fact that insertions are only done at the rear to make ENQUEUE efficient. Instead of running down the list from beginning to end each time we wish to enqueue something, we can keep a pointer (or cursor) to the last element. As for all kinds of lists, we also keep a pointer to the front of the list; for queues that pointer is useful for executing FRONT and DEQUEUE commands. In Pascal, we shall use a dummy cell as a header and have the front pointer point to it. This convention allows us to handle an empty queue conveniently.

Here we shall develop an implementation for queues that is based on Pascal pointers. The reader may develop a cursor-based implementation that is analogous, but we have available, in the case of queues, a better array-oriented representation than would be achieved by mimicking pointers with cursors directly. We shall discuss this so-called "circular array" implementation at the end of this section. To proceed with the pointer-based implementation, let us define cells as before:

type

celltype = record element: elementtype; next: − celltype

end;

Then we can define a list to consist of pointers to the front and rear of the queue. The first cell on a queue is a header cell in which the element field is ignored. This convention, as mentioned above, allows a simple representation for an empty queue. We define:

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (20 of 40) [1.7.2001 18:58:59]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

type

QUEUE = record front, rear: − celltype

end;

Figure 2.19 shows programs for the five queue operations. In MAKENULL the first statement new(Q.front) allocates a variable of type celltype and assigns its address to Q.front. The second statement puts nil into the next field of that cell. The third statement makes the header both the first and last cell of the queue.

The procedure DEQUEUE(Q) deletes the first element of Q by disconnecting the old header from the queue. The first element on the list becomes the new dummy header cell.

Figure 2.20 shows the results created by the sequence of commands MAKENULL(Q), ENQUEUE(x, Q), ENQUEUE(y, Q), DEQUEUE(Q). Note that after dequeueing, the element x being in the element field of the header cell, is no longer considered part of the queue.

A Circular Array Implementation of

Queues

The array representation of lists discussed in Section 2.2 can be used for queues, but it is not very efficient. True, with a pointer to the last element, we can execute ENQUEUE in a fixed number of steps, but DEQUEUE, which removes the first element, requires that the entire queue be moved up one position in the array. Thus DEQUEUE takes Ω(n) time if the queue has length n.

To avoid this expense, we must take a different viewpoint. Think of an array as a circle, where the first position follows the last, as suggested in Fig. 2.21. The queue is found somewhere around the circle in consecutive positions,† with the rear of the queue somewhere clockwise from the front. To enqueue an element, we move the Q.rear pointer one position clockwise and write the element in that position. To dequeue, we simply move Q.front one position clockwise. Thus, the queue migrates in a clockwise direction as we enqueue and dequeue elements. Observe that the procedures ENQUEUE and DEQUEUE can be written to take some constant number of steps if the circular array model is used.

There is one subtlety that comes up in the representation of Fig 2.21 and in any minor variation of that strategy (e.g., if Q.rear points one position clockwise of the

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (21 of 40) [1.7.2001 18:58:59]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

last element, rather than to that element itself). The problem is that there is no way to tell an empty queue from one that occupies the entire circle, short of maintaining a bit that is true if and only if the queue is empty. If we are not willing to maintain this bit, we must prevent the queue from ever filling the entire array.

To see why, suppose the queue of Fig. 2.21 had maxlength elements. Then Q.rear would point one position counterclockwise of Q.front. What if the queue were empty? To see how an empty queue is represented, let us first consider a queue of one element. Then Q.front and Q.rear point to the same position. If we dequeue the one element, Q.front moves one position

procedure MAKENULL ( var Q: QUEUE ); begin

new(Q.front); { create header cell }

Q.front−.next := nil;

Q.rear := Q.front { header is both first and last cell } end; { MAKENULL }

function EMPTY ( Q: QUEUE): boolean; begin

if Q.front = Q.rear then return (true)

else

return (false) end; { EMPTY }

function FRONT ( Q: QUEUE ): elementtype; begin

if EMPTY(Q) then error('queue is empty')

else

return (Q.front−.next−.element) end; { FRONT }

procedure ENQUEUE ( x: elementtype; var Q: QUEUE ); begin

new(Q.rear−.next); { add new cell to rear of queue }

Q.rear: = Q.rear−.next; Q.rear−.element := x; Q.rear−.next := nil

end; { ENQUEUE }

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (22 of 40) [1.7.2001 18:58:59]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

procedure DEQUEUE ( var Q: QUEUE ); begin

if EMPTY(Q) then error('queue is empty')

else

Q.front := Q.front−.next end; { DEQUEUE }

Fig. 2.19. Implementation of queue commands.

clockwise; forming an empty queue. Thus an empty queue has Q.rear one position counterclockwise of Q.front, which is exactly the same relative position as when the queue had maxlength elements. We thus see that even though the array has maxlength places, we cannot let the queue grow longer than maxlength-1, unless we introduce another mechanism to distinguish empty queues.

Fig. 2.20. A sequence of queue operations.

Let us now write the five queue commands using this representation for a queue. Formally, queues are defined by:

type

QUEUE = record

element: array[1..maxlength] of elementtype; front, rear: integer

end;

The commands appear in Fig. 2.22. The function addone(i) adds one to position i in the circular sense.

Fig. 2.21. A circular implementation of queues.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (23 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

2.5 Mappings

A mapping or associative store is a function from elements of one type, called the domain type to elements of another (possibly the same) type, called the range type. We express the fact that the mapping M associates element r of range type rangetype with element d of domain type domaintype by M(d) = r.

Certain mappings such as square(i) = i2 can be implemented easily as a Pascal function by giving an arithmetic expression or other simple means for calculating M(d) from d. However, for many mappings there is no apparent way to describe M(d) other than to store for each d the value of M(d). For example, to implement a payroll function that associates with each employee a weekly salary seems to require that we store the current salary for each employee. In the remainder of this section we describe a method of implementing functions such as the "payroll" function.

Let us consider what operations we might wish to perform on a mapping M. Given an element d of some domain type, we may wish to obtain M(d) or know whether M(d) is defined (i.e., whether d is currently in the domain of M). Or we may wish to enter new elements into the current domain of M and state their associated range values. Alternatively, we might wish to change the value of M(d). We also need a way to initialize a mapping to the null mapping, the mapping whose domain is empty. These operations are summarized by the following three commands.

1.MAKENULL(M). Make M be the null mapping.

2.ASSIGN(M, d, r). Define M(d) to be r, whether or not M(d) was defined previously.

function addone ( i: integer ): integer; begin

return (( i mod maxlength ) + 1) end; { addone }

procedure MAKENULL ( var Q: QUEUE ); begin

Q.front := 1;

Q.rear := maxlength end; { MAKENULL }

function EMPTY ( var Q: QUEUE ): boolean; begin

if addone(Q.rear) = Q.front then

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (24 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

return (true) else

return (false) end; { EMPTY }

function FRONT ( var Q: QUEUE ): elementtype; begin

if EMPTY(Q) then error('queue is empty')

else

return (Q.elements[Q.front]) end; { FRONT }

procedure ENQUEUE ( x: elementtype; var Q: QUEUE ); begin

if addone (addone(Q.rear)) = Q.front then error('queue is full')

else begin

Q.rear := addone(Q.rear);

Q.elements[Q.rear] := x end

end; { ENQUEUE )

procedure DEQUEUE ( var Q: QUEUE ); begin

if EMPTY(Q) then error('queue is empty')

else

Q.front := addone(Q.front) end; { DEQUEUE }

Fig. 2.22. Circular queque implementation.

3.COMPUTE(M, d, r). Return true and set variable r to M(d) if the latter is defined; return false otherwise.

Array Implementation of Mappings

Many times, the domain type of a mapping will be an elementary type that can be used as an index type of an array. In Pascal, the index types include all the finite subranges of integers, like 1..100 or 17..23, the type char and subranges of char like 'A'..'Z', and enumerated types like (north, east, south, west). For example, a cipher-

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (25 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

breaking program might keep a mapping crypt, with 'A'..'Z' as both its domain type and its range type, such that crypt (plaintext) is the letter currently guessed to stand for the letter plaintext.

Such mappings can be implemented simply by arrays, provided there is some range type value that can stand for "undefined." For example, the above mapping crypt might be defined to have range type char, rather than 'A'..'Z', and '?' could be used to denote "undefined."

Suppose the domain and range types are domaintype and rangetype, and domaintype is a basic Pascal type. Then we can define the type MAPPING (strictly speaking, mapping from domaintype to rangetype) by the declaration

type

MAPPING = array[domaintype] of rangetype;

On the assumption that "undefined" is a constant of rangetype, and that firstvalue and lastvalue are the first and last values in domaintype,† we can implement the three commands on mappings as in Fig. 2.23.

List Implementations of Mappings

There are many possible implementations of mappings with finite domains. For example, hash tables are an excellent choice in many situations, but one whose discussion we shall defer to Chapter 4. Any mapping with a finite domain can be represented by the list of pairs (d1, r1), (d2, r2), . . . , (dk, rk), where d1, d2, . . . , dk are all the current members of the domain, and ri is the value that the mapping associates with di, for i = 1, 2 , . . . ,k. We can then use any implementation of lists we choose for this list of pairs.

To be precise, the abstract data type MAPPING can be implemented by lists of elementtype, if we define

type

elementtype = record domain: domaintype; range: rangetype

end;

and then define MAPPING as we would define type LIST (of elementtype) in

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (26 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

procedure MAKENULL ( var M: MAPPING ); var

i: domaintype; begin

for i := firstvalue to lastvalue do M[i] := undefined

end; { MAKENULL }

procedure ASSIGN ( var M: MAPPING; d: domaintype; r: rangetype );

begin

M[d] := r end; { ASSIGN }

function COMPUTE ( var M: MAPPING;

d: domaintype; var r: rangetype ): boolean; begin

if M[d] = undefined then return (false)

else begin

r := M[d]; return (true)

end

end; { COMPUTE }

Fig. 2.23. Array implementation of mappings.

whatever implementation of lists we choose. The three mapping commands are defined in terms of commands on type LIST in Fig. 2.24.

2.6 Stacks and Recursive Procedures

One important application of stacks is in the implementation of recursive procedures in programming languages. The run-time organization for a programming language is the set of data structures used to represent the values of the program variables during program execution. Every language that, like Pascal, allows recursive procedures, uses a stack of activation records to record the values for all the variables belonging to each active procedure of a program. When a procedure P is called, a new activation record for P is placed on the stack, regardless of whether there is already another activation record for P on the stack. When P returns, its activation record must be on top of the stack, since P cannot return until all procedures it has called have returned to P. Thus, we may pop the activation record

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (27 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

for this call of P to cause control to return to the point at which P was called (that point, known as the return address, was placed in P's activation record when the call to P

procedure MAKENULL ( var M: MAPPING ); { same as for list }

procedure ASSIGN ( var M: MAPPING; d: domaintype; r: rangetype );

var

x: elementtype; { the pair (d, r) }

p: position; { used to go from first to last position on list M } begin

x.domain := d; x.range := r;

p := FIRST(M);

while p <> END(M) do

if RETRIEVE(p, M).domain = d then

DELETE(p, M) { remove element with domain d } else

p := NEXT(p, M);

INSERT(x, FIRST(M), M) { put (d, r) at front of list } end; { ASSIGN }

function COMPUTE ( var M: MAPPING;

d: domaintype; var r: rangetype ): boolean; var

p: position; begin

p := FIRST(M);

while p <> END(M) do begin

if RETRIEVE(p, M).domain = d then begin r := RETRIEVE(p, M).range;

return (true) end;

p := NEXT(p, M) end;

return (false) { if d is not in domain } end; { COMPUTE }

Fig. 2.24. Mapping implementation in terms of lists.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (28 of 40) [1.7.2001 18:59:00]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

was made).

Recursion simplifies the structure of many programs. In some languages, however, procedure calls are much more costly than assignment statements, so a program may run faster by a large constant factor if we eliminate recursive procedure calls from it. We do not advocate that recursion or other procedure calls be eliminated habitually; most often the structural simplicity is well worth the running time. However, in the most frequently executed portions of programs, we may wish to eliminate recursion, and it is the purpose of this discussion to illustrate how recursive procedures can be converted to nonrecursive ones by the introduction of a user-defined stack.

Example 2.3. Let us consider recursive and nonrecursive solutions to a simplified version of the classic knapsack problem in which we are given target t and a collection of positive integer weights w1, w2 , . . . , wn. We are asked to determine whether there is some selection from among the weights that totals exactly t. For example, if t = 10, and the weights are 7, 5, 4, 4, and 1, we could select the second, third, and fifth weights, since 5+4+ 1 = 10.

The image that justifies the name "knapsack problem" is that we wish to carry on our back no more than t pounds, and we have a choice of items with given weights to carry. We presumably find the items' utility to be proportional to their weight,† so we wish to pack our knapsack as closely to the target weight as we can.

In Fig. 2.25 we see a function knapsack that operates on an array

weights : array [l..n] of integer.

A call to knapsack(s, i) determines whether there is a collection of the elements in weight[i] through weight[n] that sums to exactly s, and prints these weights if so. The first thing knapsack does is determine if it can respond immediately. Specifically, if s = 0, then the empty set of weights is a solution. If s < 0, there can be no solution, and if s > 0 and i > n, then we are out of weights to consider and therefore cannot find a sum equal to s.

If none of these cases applies, then we simply call knapsack(s-wi, i + 1) to see if there is a solution that includes wi. If there is such a solution, then the total problem is solved, and the solution includes wi, so we print it. If there is no solution, then we call knapsack(s, i + 1) to see if there is a solution that does not use wi.

Elimination of Tail Recursion

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (29 of 40) [1.7.2001 18:59:00]