*Presents recursion as a special case of the top-down approach to problem solving**Explains recursive programs**how to understand them**how to simulate them**how to write them**Shows how recursive programs may be translated by a compiler or written in a non-recursive language**Introduces two more data structures**the stack**the queue**Illustrates the use of a stack with operations**setstack**empty**push**pop**Case study--checking sequences for proper nesting**uses the stack and treats it as a data abstraction*

People can't help but use themselves--their own life experiences--as a point of reference for understanding the world and the experiences of others. Definitions, algorithms, and programs may also refer to themselves, but for a different purpose: to express their meaning or intention more clearly and concisely. They are then said to be * recursive*. Languages such as C that allow functions to call themselves are called

A game called the Towers of Hanoi was purportedly played by priests in the Temple of Brahma, who believed that completion of the game's central task would coincide with the end of the world. The task involves three pegs. The version considered here has *n* disks initially mounted on peg 1 (the priests dealt with 64 disks). The *n* disks increase in size from top to bottom, the top disk being the smallest. The problem is to relocate the *n* disks to peg 3 by moving one at a time. Only the top disk on a peg can be moved. Each time a disk is moved it may be placed only on an empty peg or on top of a pile of disks of larger size. The task is to develop an algorithm specifying a solution to this problem, *no matter what the value of *n*.*

1. Move the top disk from peg l to peg 2.

2. Move the top disk from peg 1 to peg 3.

3. Move the top disk from peg 2 to peg 3.

4. Move the top disk from peg 1 to peg 2.

5. Move the top disk from peg 3 to peg 1.

6. Move the top disk from peg 3 to peg 2.

7. Move the top disk from peg 1 to peg 2.

8. Move the top disk from peg 1 to peg 3.

9. Move the top disk from peg 2 to peg 3.

10. Move the top disk from peg 2 to peg 1.

11. Move the top disk from peg 3 to peg 1.

12. Move the top disk from peg 2 to peg 3.

13. Move the top disk from peg 1 to peg 2.

14. Move the top disk from peg 1 to peg 3.

15. Move the top disk from peg 2 to peg 3.

1. Move the top *n* - 1 disks from peg 1 to peg 2.

2. Move the top disk from peg 1 to peg 3.

3. Move the top *n* - 1 disks from peg 2 to peg 3.

We now generalize the original problem:

Move the top *n* disks from peg *i* to peg *f*.

To obtain towers(n,i,a,f):

If n = 1, then

move the top disk from peg i to peg f

else

apply towers(n - 1,i,f,a)

moves the top disks from peg i to peg f

apply towers(n - 1,a,i,f).

This is the recursive algorithm for the Towers of Hanoi problem. Notice that the definition gives an explicit solution for the special case when n = l and an implicit solution for the case of n > 1.

To use the method of recursion we must recognize when it is applicable and find a correct way to generalize the original problem and then to break down the generalization. We have been successful and have found a recursive algorithm. Because no further refinement is needed, the corresponding recursive program can be written directly using functional modularization:

towers(n,i,a,f)

/* Moves the top n disks from peg i to peg f

*/

int n,i,a,f;

{

if(n == 1)

printf("\n %d -> %d\n",i,f);

else

{

towers(n-1,i,f,a);

printf("\n %d -> %d\n",i,f);

towers(n-1,a,i,f);

}

}

Anytime a function calls itself during its execution, a * recursive call* has been made. The two invocations of towers within towers represent such recursive calls. In general, when a recursive program executes on a computer, or when its execution is simulated, many recursive calls will be made. Simulation of a program or function call means carrying out its instructions by hand and keeping track of the values of all its variables. These are referred to as the first, second, etc., recursive calls. The initial call to the function precedes the first recursive call.

The verification of a recursive program can be done in two ways, as is true for a nonrecursive program. One is by formal proof, the other by checking all cases. With recursion, the cases given explicitly are checked first. A case is given explicitly when the action taken by the program in that case does not require a recursive call. Also, it is assumed that each function individually works correctly. For towers(n,i,a,f), the only explicit case is when n = 1 and the function clearly outputs the proper result and terminates.

Since n is greater than 1, the procedure requires the sequential execution of

towers(3,1,3,2)

printf("\n %d -> %d\n",1,3);

towers(3,2,1,3)

Dealing with towers(3,1,3,2), since n > 1, the commands

towers(2,1,2,3)

printf("\n %d -> %d\n",1,2);

towers(2,3,1,2)

Dealing with towers(2,1,2,3), since n > 1,

towers(1,1,3,2)

printf("\n %d -> %d\n",1,3);

towers(1,2,1,3)

The four parameter values of the call currently being carried out

Where to resume when the call currently being carried out is completed

It is not always possible to find a recursive solution to a problem, nor is it always desirable to use one when available. Sometimes a recursive solution is the only one we can find. For the Towers of Hanoi problem it is difficult to find a nonrecursive solution, but a number are known. Recursive solutions normally make it easier to see why they are correct, probably because to achieve them requires that you make the structure inherent in the problem more explicit.

To make this point clearly, the recursive algorithm and a nonrecursive algorithm are repeated here. Convince yourself that the nonrecursive algorithm solves the Towers of Hanoi problem correctly (see Exercise 8). The nonrecursive program is taken from Walsh [1982]; another nonrecursive program appears in Buneman and Levy [1980].

A Recursive Solution for the Towers of Hanoi

To obtain towers(n,i,a,f):

If n = 1, then

move the top disk from i to f

else

apply towers (n - 1,i,f,a)

move the top disk from i to f

apply towers(n - 1,a,i,f).

A Nonrecursive Algorithm for the Towers of Hanoi

l. Label the disks l, 2, . . . , n in increasing order of size.

2. Label the pegs i, a, and f, n + 1, n + 2, and n + 3, respectively.

4. While all disks are not on the same peg

a. move the second smallest top disk onto the peg not containing the smallest disk

We will now present a series of functions to further illustrate recursive programs. The functions

**1. **Determine the length of a list

**2. **Create a list that is a copy of another list

**3. **Count checkerboard placements

length(listname)

/* Returns the number of records

in the list pointed to by listname.

*/

listpointer listname;

{

listpointer setnull(),next();

if(listname == setnull())

return(0);

else

return(1 + length(next(listname)));

}

This function returns the length of the list**, **listname**. **To verify that this is correct we must check

**1. **The null list. It returns with length = 0.

**2. **A one-record list followed by another list. It returns length = 1 + the length of the list after the first record.

It is correct, since its value is correct for each case. Of course it is correct--after all, the length of a null list is zero, and the length of a list with at least one record is 1 for the record, plus the length of the rest of the list beyond the first record ! This was how length was written in the first place.

Consider the function copy,** **which creates a list second that is a copy of a list** **first:

copy(first,psecond)

/* Creates a new list which is a copy

of the list pointed to by first and

whose head is second

*/

listpointer first,*psecond;

{

listpointer null, rest,setnull(),avail(),next();

null = setnull();

if(first == null)

*psecond = null;

else

{

*psecond = avail();

setinfo(*psecond,first);

copy(next(first),&rest);

setlink(*psecond,rest);

}

}

When first is the null list, copy faithfully terminates with the copy also a null list. When first is a one-record list, copy sets second to point to storage allocated for a record and sets the information field value of this record to the value of the information field in first's first record. The recursive call to copy(next(first),&rest) is then an invocation of copy to copy the null list, since next(first) is null in this case. Assuming it performs its task correctly,** **rest will be null when it returns. The link field of the record pointed to by second is then set to the value of rest (the null pointer), and the initial call to** **copy terminates correctly.

Similarly, had there been more than one record in first's list, the recursive call to copy would have returned with rest pointing to a correct copy of the list pointed to by next(first). Setlink would correctly place a pointer to that correct copy into the link field of the record pointed to by second, and the initial call would terminate correctly. This verifies that copy is correct in all cases. Again, to copy the null list is easy. To copy a list with at least one record, simply copy that record, copy the rest of the list beyond the first record, and append that copy to the copy of the first record. This is how copy was written!

If you are confronted with a recursive program and want to understand it, approach it in the same way as you would a nonrecursive program. Assume that any functions that are called perform their functions correctly, and then attempt to see what the program itself does. Sometimes this will be apparent, as it was for** **towers and copy, and sometimes a simulation of the program helps to increase comprehension. Imagine, for example, that you were not told what copy did. It wouldn't have been so easy to find out without simulating some simple cases.

In order to understand what happens as a recursive program executes, it is necessary to review how local and global variables are treated, and also how parameters are treated. This must also be known to understand what happens when any program executes.

In nonrecursive programs, references to global and to static variables always refer to the current actual storage assigned to them. Hence any changes to their values during execution of the program will be reflected back in their values. Local automatic variables are treated differently. Local copies are made, and these are referred to during the execution of the function to which they are local. If the local variables are automatic, the storage for the local copies disappears when the function terminates or returns. If the local variables are static, the storage remains after the function is terminated, and the variable retains its value for the next time the function is called.

Parameters passed in the argument lists of functions are treated as variables local to the function. They are passed by value. New storage is established for each parameter. The storage is initially set to the value of the corresponding actual parameter when the function is invoked. In effect, this storage represents a *local copy* of the actual parameter. Any reference in the function is interpreted as a reference to the local copy only. This implies that any change to a parameter during the execution of the function will *not* be reflected back to the storage used for the actual parameter; it can not have its value changed by the function.

simple (x,py)

int x, *py;

{

x = 1;

*py = 2;

*py = x + *py;

}

In the recursive version of copy, note that

First is passed by value and second by pointer.

An alternative version of copy that returns a pointer to the copy of the list first would be as shown on page 160.

listpointer copy(first)

/* Returns a pointer to the first record of a new list which is a

copy of the list first.

*/

listpointer first;

{

listpointer null,second,setnull(),avail(),next();

null = setnull();

if (first == null)

second = null;

else

{

second = avail();

setinfo(second,first);

setlink(second,copy(next(first)));

}

return (second);

}

This version differs from the original version in two ways. One, it has only one parameter, the list to be copied, and two, it returns a pointer to the new copy rather than setting a second parameter to point to the new copy.

f(n) is

1 ifn= 4

f(n- 1) + (n- 3) + (n- 4) ifn5

It is easy to write a recursive function f, with parameter n, to return the correct result for any n 4.

f(n)

int n;

{

if (n == 4)

return (1);

else

return(f(n-1)+(n-3)+(n-4));

}

If n = 7, the program would execute as follows:

f(7) =f(6) + (7 - 3) + (7 - 4)

f(6) =f(5) + (6 - 3) + (6 - 4)

f(5) =f(4) + (5 - 3) + (5 - 4)

f(4) = 1

f(5) = 1 + 2 + 1 = 4

f(6) = 4 + 3 + 2 = 9

f(7) = 9 + 4 + 3 = 16

f(n)

int n;

{

return((n-3)*(n-3));

}

The final example returns to the stable marriage problem. Suppose you are asked to find a stable pairing for the *n* men and women of the stable marriage problem in Chapter 2, but you aren't aware of the algorithm discussed in Section 2.5. Probably the most straightforward approach is to search through all the possible pairings until a stable pairing is found. Each possible pairing may be thought of as a specific permutation of the *n* women. Thus the example pairing of Table 2.2 corresponds to the permutation (or listing) 4, 3, 1, 2, 5. In general there are *n* ! such permutations (where *n*! means *n* factorial).

permutations(n)

/* Generates and processes each

permutation of the integers

1 to n.

*/

int n;

{

int done;

done = FALSE;

initialize(n);

while (!done)

{

process(n);

next(n,&done);

}

}

where next (n,&done) must return, having updated the current permutation to the next permutation, unless the current permutation is the last one, when it simply sets done to *true*.

The problem is now to refine next. Suppose *n* = 4 and the first permutation is 3 2 1. Inserting 4 in all possible positions among 1, 2, and 3 gives the first four permutations of 1, 2, 3, and 4.

43 2 1

342 1

3 241

3 2 14

Removing 4 leaves 3 2 1. The next four permutations for n = 4 can be obtained by first obtaining the next permutation after 3 2 1 for *n* = 3. But this next permutation for *n* = 3 can similarly be obtained by shifting 3 to the right one place, yielding 2 3 1. Then the next four permutations for *n* = 4 are

42 3 1

243 1

2 341

2 3 14

Removing 4 leaves 2 3 1. Again, the next permutation after 2 3 1, 2 1 3, is obtained by shifting 3 right. The next four permutations for *n* = 4 are

42 1 3

241 3

2 143

2 1 34

Continuing this process will produce, in turn,

43 1 241 3 241 2 3

341 2 143 2 142 3

3 142 1 342 1 243

3 1 241 3 24and 1 2 34

next (n,pdone)

If n is not 1, then

If n is not at the right end of the current permutation of 1, . . , n then

shift it right one position

else

remove "n" from the current permutation of 1, . . , n

next(n - 1,pdone)

Insert "n" at the left end of the current permutation of 1, . . , n - 1

else

set done to true.

next(n,pdone)

/* Generates the next permutation unless

the current one is the last. In this case

done is set to true.

*/

int n,*pdone;

{

int i;

if (n > 1)

if (l[n] < n)

{

p[l[n]] = p[l[n]+1];

p[l[n]+1] = n;

l[n] = l[n]+1;

}

else

{

next(n-1,pdone);

for (i=n-1;i>=1;i--)

p[i+1] = p[i];

p[1] = n;

l[n] = 1;

}

else

*pdone = TRUE;

}

Figure 4.6(a) simulates the execution of next(4,pdone) when the current permutation is 2 1 3 4.

next(n,pdone)

/* Generates the next permutation unless

the current one is the last. In this case

done is set to true.

*/

int n,*pdone;

{

if (n > 1)

if (ptr[n]->link != NULL)

{

pred[n]->link = ptr[n]->link;

pred[n] = pred[n]->link;

ptr[n]->link = pred[n]->link;

pred[n]->link = ptr[n];

}

else

{

pred[n]->link = NULL;

next(n-l,pdone);

ptr[n]->link = p->link;

p->link = ptr[n];

pred[n] = p;

}

else

*pdone = TRUE;

}

Figure 4.6(b) simulates the execution of next(4,pdone) when the current permutation is 2 l 3 4.

In comparing the two implementations notice that the advantage of the list implementation is that the **for** loop required by the array implementation is no longer needed. Inserting n at the left end of the current permutation thus takes only two pointer changes rather than time proportional to *n*. Other permutation algorithms are explored in Sedgewick [1977].

To further illustrate the differences, two complete programs using function permutations, one for the array and one for the list implementation, are given below. The process function prints each permutation. To adapt these programs to obtain a solution for the stable marriage problem, the function process must test for stability. Another modification would be to abort the execution when a stable pairing is found. This requires that process be given access to done so that it can set done to true at that point.

#include <stdio.h>

#define TRUE 1

#define FALSE 0

typedef int arraytype[21];

arraytype p,l;

main()

/* Driver for permutations. */

{

int n;

printf("\n n = ?\n");

scanf("%d",&n);

permutations(n);

}

permutations(n)

/* Generates and processes each

permutation of the integers

1 to n.

*/

int n;

{

int done;

done = FALSE;

initialize(n);

while (!done)

{

process(n);

next(n,&done);

}

}

initialize(n)

/* Creates initial permutation */

int n;

{

int i;

for (i = 1;i<=n;i++)

{

p[i] = n - i + 1;

l[i] = 1;

}

}

process(n)

/* Prints the current permutation */

int n;

{

int i;

for (i=1;i<=n;i++)

printf("\n%d\n",p[i]);

printf("\n");

}

next(n,pdone)

/* Generates the next permutation unless

the current one is the last. In this case

done is set to true.

*/

int n,*pdone;

{

int i;

if (n > 1)

if (l[n] < n)

{

p[l[n]] = p[l[n]1];

p[l[n]+1] = n;

l[n] = l[n]+1;

}

else

{

next(n-1,pdone);

for (i=n-1;i>=1;i--)

p[i+1] = p[i];

p[1] = n;

l[n] = 1;

}

else

*pdone = TRUE;

}

#include <stdio.h>

#define TRUE l

#define FALSE 0

#define NULL 0

typedef struct record

{

int info;

struct record *link;

}listrecord,*listpointer;

typedef listpointer pointerarray[21];

pointerarray ptr,pred;

listpointer p;

main()

/* Driver for permutations. */

{

int n;

printf("\n n = ?\n");

scanf("%d",&n);

permutations(n);

}

permutations(n)

/* Generates and processes each

permutation of the integers 1 to n.

*/

int n;

{

int done;

done = FALSE;

initialize(n);

while (!done)

{

process(n);

next(n,&done);

}

}

initialize(n)

/* Creates initial permutation */

int n;

{

int i;

listpointer q;

p = malloc(sizeof(listrecord));

q = P;

for (i=1;i<=n;i++)

{

q->link = malloc(sizeof(listrecord));

q = q->link;

q->info = n - i + 1;

ptr[n-i+1] = q;

pred[i] = p;

}

q->link = NULL;

}

process(n)

/* Prints the current permutation */

int n;

{

listpointer q;

q = p->link;

while (q != NULL)

{

printf("\n%d\n",q->info);

q = q->link;

}

printf("\n");

}

next(n,pdone)

/* Generates the next permutation unless

the current one is the last. In this case

done is set to true.

*/

int n,*pdone;

{

if (n > 1)

if (ptr[n]->link != NULL)

{

pred[n]->link = ptr[n]->link;

pred[n] = pred[n]->link;

ptr[n]->link = pred[n]->link;

pred[n]->link = ptr[n];

}

else

{

pred[n]->link = NULL;

next(n-1,pdone);

ptr[n]->link = p->link;

p->link = ptr[n];

pred[n] = p;

}

else

*pdone = TRUE;

}

When any program invokes one of its functions, it is because the task performed by that component must now be carried out. Global variables and variables passed by address (pointers) specify storage that is not local to the component but that it may reference and change. It may also reference and change static variables. All such storage represents the *data* the component is to process. Any changes by the component to the data are reflected back in the data's storage.

In effect, these copies are treated as if they were additional local variables of the component. The actual local variables of the component represent temporary information that the component uses to do its job. Both the local copies and local variables disappear when the task is completed. This storage for local copies and local variables serves as a "scratchpad" for use by the component. The scratchpad contains information used temporarily by the component to perform its task on the data. This view of the data and scratchpad of a component is depicted in Figure 4.7.

Suppose that this number is *k*, that the return for the initial call is handled separately, and also that the scratchpad for the currently executing call is associated with the function. The number of sets of additional returns and scratchpads that must be retained is then *k*. The *depth* of a recursive program is given by the maximum value of *k*. It is the depth that determines the amount of storage required by the function. The following examples illustrate these ideas.

[2] and n = 4, i = l, a = 2, f = 3 for the initial call

[1] and n = 3,i = 2, a = 1, f = 3 for the eighth recursive call

[1] and n = 2, i = 2, a = 3, f = 1 for the ninth recursive call

first0, null0, rest0 for the initial call

first1, null1, rest1 for the first recursive call

first2, null2, rest2 for the second recursive call

n = 4 for the initial call

n = 3 for the second recursive call

n = 2 for the third recursive call

Recursion is a powerful tool for the development of algorithms and leads to concise, clear recursive programs that can be easier to check for correctness. Complex algorithms may be expressed using relatively few program statements, which at the same time emphasize the structure of the algorithm. This will become even more apparent later in the text, as more difficult problems are solved.

A function that invokes itself is * directly recursive*. A function is

1. Each time a recursive call is made to the function,

a. save the proper return place and the current scratchpad values,

b. set the scratchpad values to their new values.

2. Each time a recursive call is completed,

The stack is the most convenient data abstraction to use for the bookkeeping recursion entails. To illustrate the translation, and the possibility of enhancing efficiency, the recursive functions towers and next will now be translated into nonrecursive functions.

In towers** **there are two recursive calls. The idea in implementing it is to write a nonrecursive program that executes just as the recursive program would, while managing the additional records generated by the recursion. This amounts to implementing the procedure described for simulating towers. Each recursive call will be replaced by code to insert the proper return indicator onto a stack, as well as the current scratchpad values. Whenever the end of a recursive call is reached, the proper return indicator and the scratchpad values last put on the stack will be removed and restored to the program's local storage. The earlier recursive version and its implementation as a nonrecursive function are as follows .

towers(n,i,a,f)

/* Moves the top n disks

from peg i to peg f

*/

int n,i,a,f;

{

if(n == 1)

printf("\n %d -> %d\n",i,f);

else

{

towers(n-1,i,f,a);

printf("\n %d -> %d\n",i,f)

towers(n-1,a,i,f);

}

}

Nonrecursive Version

towers(n,i,a,f)

/* Moves the top n disks

from peg i to peg f

*/

int n,i,a,f;

{

int retrn;

stack s;

setstack(&s);

one: if(n == 1)

printf("\n %d -> %d\n",i,f);

else

{

s_tack(1,n,i,a,f &s);

setvar1(&n,&i,&a,&f);

goto one;

}

two: if(!empty(&s))

{

restore(&retrn,&n,&i,&a,&f,&s);

switch(retrn)

{

case 1:

printf("\n %d -> %d\n",

i,f)

s_tack(2,n,i,a,f,&s);

setvar2(&n,&i,&a,&f);

goto one;

case 2:

goto two;

}

}

}

S_tack is a routine that inserts its arguments, as fields of a record, onto the stack. The name s_tack is used to be sure the compiler can distinguish this routine from the type name stack that also appears in the function. Setstack ensures that the stack will initially contain zero entries; empty returns *true *if the stack contains no records and *false* otherwise. The setvar routines do the proper setting of the current scratchpad values for the ensuing recursive call. Restore(&retrn,&n,&i,&a,&f,&s) restores the proper scratchpad values when a return is to be made after completion of some recursive call.

Setvar1(&n,&i,&a,&f) sets n to n - 1 and interchanges the values of f and a.

Setvar2(&n,&i,&a,&f) sets n to n - 1 and interchanges the values of a and i.

Notice that the implementation requires a stack that can hold the stored information for up to *n *- 1 recursive calls. The stack must be initialized to empty. Its contents must be preserved between calls. We will not dwell on its implementation details here, but a complete program to test this version is given in Section 4.5.1.

How can we create a more efficient version of a translated program such as towers? The reason for the stack in the first place is to save return codes and to save scratchpad values that are needed when the suspended call is ready to resume (after the saved values have been unstacked and restored, and the proper program segment is to be executed). If the programmer can determine where the return should be, or what the scratchpad values that are to be restored should be, then this information does not have to be stacked. It may not be necessary to save the values of some other variables. It may also be possible to eliminate some return codes. If no variables need to be saved, and there is only one return code, then the stack itself is not needed. Let us attempt to reach this goal for the implementation of the recursive towers routine.

towers(n,i,a,f)

/* Moves the top n disks

from peg i to peg f

*/

int n,i,a,f;

{

stack s;

setstack(&s);

one: if(n == 1)

printf("\n %d -> %d\n",i,f);

else

{

s_tack(n,i,a,f,&s);

setvar1(&n,&i,&a,&f);

goto one;

}

if(!empty(&s))

{

restore(&n,&i,&a,&f,&s);

printf("\n %d -> %d\n",i,f);

setvar2(&n,&i,&a,&f);

goto one;

}

}

Another improvement can be made by changing the **if-else** structure to a **while** loop. Doing so improves the clarity and eliminates the **goto:**

one: if(n == 1) one: while(n > 1)

printf("\n %d -> %d\n",i,f); {

else s_tack(n,i,a,f,&s);

{ setvar1(&n,&i,&a,&f);

s_tack(n,i,a,f,&s); }

setvar1(&n,&i,&a,&f); printf("\n %d -> %d\n",i,f);

goto one;

}

This yields

Third Nonrecursive Version

towers(n,i,a,f)

/* Moves the top n disks

from peg i to peg f

*/

int n,i,a,f;

{

stack s;

one: while(n > 1)

**5 while*** loop replaces ***if-else*** construct*

{

s_tack(n,i,a,f,&s);

setvar1(&n,&i,&a,&f);

}

printf("\n %d -> %d\n",i,f);

if(!empty(&s))

{

restore(&n,&i,&a,&f,&s);

printf("\n %d -> %d\n",i,f);

setvar2(&n,&i,&a,&f);

goto one;

}

}

Finally, the function can be written in more structured form, as follows:

towers(n,i,a,f)

/* Moves the top n disks

from peg i to peg f

*/

int n,i,a,f;

{

stack s;

int done

done = FALSE;

while(!done)

{

while(n > 1)

{

s_tack(n,i,a,f,&s);

setvar1(&n,&i,&a,&f);

}

printf("\n %d -> %d\n",i,f);

if(!empty(&s))

{

restore(&n,&i,&a,&f,&s);

printf("\n %d -> %d\n",i,f);

setvar2(&n,&i,&a,&f);

}

else

done = TRUE;

}

The same approach can now be applied to develop a nonrecursive translation for next.

next(n,pdone)

/* Generates the next permutation unless

the current one is the last. In this case

done is set to true.

*/

int n,*pdone;

{

int i,retrn;

stack s;

one: if(n > 1)

if(l[n] < n)

{

p[l[n]] = p[l[n] + 1];

p[l[n] + 1] = n;

l[n] = l[n] + 1;

}

else

{

s_tack(1,n,i,&s);

setvar(&n,&i);

goto one;

}

else

*pdone = TRUE;

two: if(!empty(&s))

{

restore(&retrn,&n,&i,&s);

switch(retrn)

{

case 1:

"explicit" exit must be made

{

for(i=n-1;i>=1;i--)

p[i+1] = p[i];

p[1] = n;

l[n] = 1;

goto two;

{

{

{

{

where setvar(&n,&i) simply sets n to n-1.

The same program can be written in a more structured way. First notice that the statement labeled "two" and the **goto** "two" statement create a **while** loop. Introducing that **while** loop but retaining the structure of "one," the overall structure of the program becomes as follows

one: ifc1 then

ifc2 then

taskc1 andc2 both true

else

task forc1 true butc2 false

goto one

else

task forc1 false

while not empty(&s)

loop task

Next, the structure of "one" can also be improved, as follows.

while (c1 and notc2)

task forc1 true butc2 false

ifc1, then

task forc1 andc2 both true

else

task forc1 false

while not empty (&s)

loop task.

next(n,pdone)

/* Generates the next permutation unless

the current one is the last. In this case

done is set to true.

*/

int n,*pdone

{

int i,retrn;

stack s;

while((n > 1) && !(l[n] < n))

{

s_tack(1,n,i,&s);

setvar(&n,&i);

}

if(n > 1)

{

p[l[n]] = p[l[n] + 1];

p[l[n] + 1] = n;

l[n] = l[n] + 1;

}

else

*pdone = TRUE;

while(!empty(&s))

{

restore(&retrn,&n,&i,&s);

switch(retrn)

{

case 1:

{

for(i=n-1;i>=1;i--)

p[i+1] = p[i];

p[1] = n;

l[n] = 1;

}

}

}

}

In general, when the value of a scratchpad variable does not change or does not need to be maintained between recursive calls, it need not be stacked. This is the case with the variable i of next. Also, when there is only one return place from a recursive call, there is no need to stack a return indicator. This is the situation with next. Finally, the value of n varies in a predictable fashion. Its restored value will always be 1 greater than its current value. Thus there is no need to stack n. Each time a recursive call returns, n may be correctly restored by adding 1 to its current value.

Therefore, the stack is unnecessary, since no information must be retained on it. The s_tack function can be removed, setvar can be replaced by the statement n = n-1, and restore can be replaced by the statement n = n+1. Still, the stack controls the second **while** loop in our translated version. Even though no information needs to be stacked, it is still necessary to know when the stack would have been empty so that the loop may be properly exited.

Notice that the first **while** loop decreases n by l every time a stack entry would have been made, and the second **while** increases n by l every time an entry would have been deleted from the stack. Hence, if an integer variable s is set to n initially, prior to the first **while** loop, the test to see if the stack is empty in the second **while** loop becomes s = n. The final version of next is an iterative program that has no stack. It is an example of the translated version giving us a better solution. This four-step solution is efficient and is also clear.

1. Set s to n.

2. Set n to the rightmost entry in the permutation that can still be shifted right.

3. If that entry is not l, then

Shift it right

else

Set done to *true*

4. Place the s-n entries that could not be moved to the right in the proper order at the left end of the permutation.

The final program is as follows:

next(n,pdone)

/* Generates the next permutation unless

the current one is the last. In this case

done is set to true.

*/

int n,*pdone

{

int i,s;

1. s = n;

2. while((n > 1) && !(l[n] < n))

n--;

3. if(n > 1)

{

p[l[n]] = p[l[n] + 1];

p[l[n] + 1] = n;

l[n] = l[n] + 1;

}

else

*pdone = TRUE;

4. while(s > n)

{

n++

for(i=n-1;i>=1;i--)

p[i+1] = p[i];

p[1] = n;

l[n] = 1;

}

}

By translating the recursive solution and analyzing it, a highly efficient nonrecursive solution was built. A little insight can help a lot. For more on recursion, see Barron [1968] and Bird [1977a, 1977b]. It may now be time for you to make a recursive call on all preceding material!

Earlier in this chapter the notion of a stack was introduced and used in the nonrecursive implementations of towers and next. Stacks are useful in situations requiring the retention and recall of information in a specific order--namely, when information is removed in a last-in, first-out order (LIFO for short). Removing tennis balls from a can is LIFO. In programming, stacks are useful when a program must postpone obligations, which must later be fulfilled in *reverse order *from that in which they were incurred.

Information is kept in order in a * stack*. Additional information may be inserted on the stack, but only at the front or top end. Thus the information at the top of the stack always corresponds to the most recently incurred obligation. Information may be recalled from the stack, but only by removing the current top piece of information. The stack acts like a pile of playing cards to which we can only add a card at the top and from which we can only remove the top card. Of course, this is not what is meant by a "stacked deck."

A stack may be implemented using arrays with the following declarations:

typedef struct

{

whatever info;

}stackrecord;

typedef struct

{

stackrecord stackarray [LIMIT];

int top;

}stack;

stack s;

The definitions must be preceded by a typedef for "whatever." Let us assume LIMIT has been set in a define statement fixing the maximum number of items the stack can hold. Suppose 6, 45, 15, 32, and 18 were pushed onto the stack. Figure 4.8 illustrates the meaning attached to the declaration. Figure 4.8(a) is a conceptualization of the stack. Since 6 was the first entry on the stack, it is on the bottom. Likewise, 18 was the last entry, so it is on top. Figure 4.8(b) is the way the data is stored in the actual stack s. The stackarray holds the data and top contains an index to the current entry on the top of the stack. Although 6 is at the top of the array, it is the bottom stack entry; while 18 is at the bottom of the array, it is the top stack entry. Thus top has the value 4.

Addition or insertion of a new element to the stack will be accomplished by a function push. Removal or deletion of the current top stack element will be accomplished by a function pop. Executing push (&newrecord,&s) results in the contents of newrecord being placed on the stack as a new first element. A call to the function pop(&s,&value) causes the removal of the current top stack element, with value containing a copy of that value. A routine setstack sets the stack to empty so that it initially contains no entries.

pop(&s,&y);

pop(&s,&z);

push(&newrecord,&s);

If Figure 4.8 indicates the current stack, then Figure 4.9 shows the new situation after this execution.

* Stack underflow* occurs when a program attempts to remove an element from an empty stack. It normally indicates either an error or the termination of a task.

It is also necessary to test the stack to determine whether or not it is empty. This may be accomplished by invoking a function empty, which will return the value *true* when the stack is empty and *false* otherwise.

These routines may be implemented as follows:

setstack (ps)

/* Initializes the stack s to empty */

stack *ps;

{

(*ps).top = -1;

}

empty (ps)

/* Returns true only if the stack is empty */

stack *ps;

{

return ((*ps).top == -1);

}

push (pnewrecord,ps)

/* Inserts the record newrecord

at the top of the stack s

*/

stackrecord *pnewrecord,

stack *ps;

{

if ((*ps).top == (LIMIT - 1))

overflow(ps);

else

{

(*ps).top = (*ps).top + 1;

(*ps).stackarray[(*ps).top].info =

(*pnewrecord).info;

}

}

pop(ps,pvalue)

/* Copies the contents of the top record

of stack s into value and removes the

record from the stack

*/

stack *ps;

stackrecord *pvalue;

{

if(empty(ps))

underflow(ps);

else

{

(*pvalue).info = (*ps).stackarray

[(*ps).top].info;

(*ps).top = (*ps).top - 1;

}

}

The procedures overflow and underflow are assumed to take appropriate action when they are invoked. Notice that the elements of the stack will be of "whatever" type. We have taken the liberty here of assuming that the C compiler being used allows the contents of one structure to be assigned to another. Otherwise, for example, the assignment

(*ps).stackarray[(*ps).top].info =

(*pnewrecord).info;

that occurs in push could not be used. Instead, each field of info would have to be individually assigned.

The implementation discussed so far applies when *records* are to be stored on the stack. Instead, if only the contents of *simple variables* of type such as int, float, char, or listpointer are to be stored, then the declarations and definitions of push and pop may be simplified, as follows.

typedef struct

{

whatever stackarray [LIMIT];

int top;

}stack;

push(value,ps)

/* Inserts the new value

at the top of the stack s

*/

whatever value;

stack *ps;

{

if((*ps).top == (LIMIT-1))

overflow(ps);

else

{

(*ps).top = (*ps).top + 1;

(*ps).stackarray[(*ps).top] = value;

}

}

pop(ps,pvalue)

/* Copies the contents of the top entry

of stack s into value and removes it

from the stack

*/

stack *ps;

whatever *pvalue;

{

if(empty(ps))

underflow(ps);

else

{

*pvalue = (*ps).stackarray[(*ps).top];

(*ps).top = (*ps).top - 1;

}

}

"Whatever" will, of course, be declared of type int, or float, etc. The same simplification can be made, when appropriate, to the implementations of Sections 4.5.2, 4.5.3, 4.7.1, 4.7.2, and 4.7.3.

#include <stdio.h>

#define LIMIT 50

typedef struct

{

int n;

int i;

int a;

int f;

}whatever;

typedef struct

{

whatever info;

}stackrecord;

typedef struct

{

stackrecord stackarray [LIMIT];

int top;

}stack;

setstack(ps)

/* Initializes the stack s to empty */

stack *ps;

{

(*ps).top = -1;

}

empty(ps)

/* Returns true only if the stack s is empty */

stack *ps;

{

return((*ps).top == -1);

}

push(pnewrecord,ps)

/* Inserts the record newrecord

at the top of the stack s

*/

stackrecord *pnewrecord;

stack *ps;

{

if ((*ps).top == (LIMIT-1))

overflow(ps);

else

{

(*ps).top = (*ps).top + 1;

(*ps).stackarray[(*ps).top].info =

(*pnewrecord).info;

}

}

pop(ps,pvalue)

/* Copies the contents of the top record

of stack s into value and removes the

record from the stack

*/

stack *ps;

stackrecord *pvalue;

{

if (empty(ps))

underflow(ps);

else

{

(*pvalue).info =

(*ps).stackarray[(*ps).top].info;

(*ps).top = (*ps).top - 1;

}

}

overflow(ps);

/* Prints a message that the stack has overflowed */

stack *ps;

{

printf(" The stack has overflowed \n");

}

underflow(ps);

/* Prints a message that the stack has underflowed */

stack *ps;

{

printf(" The stack has underflowed \n");

}

main()

/* Driver for towers */

{

int n;

printf("\n enter a value for n\n");

scanf("%d",&n);

towers(n,1,2,3);

}

towers(n,i,a,f)

/*Moves the top n disks

from peg i to peg f

*/

int n,i,a,f;

{

stack s;

int done;

setstack(&s);

done = FALSE;

while(!done)

{

while (n > 1)

{

s_tack(n,i,a,f,&s);

setvar1(&n,&i,&a,&f);

}

printf("\n %d -> %d\n",i,f);

if(!empty(&s))

{

restore(&n,&i,&a,&f,&s);

printf("\n %d -> %d\n",i,f);

setvar2(&n,&i,&a,&f);

}

else

done = TRUE;

}

setvar1(pn,pi,pa,pf)

/* Sets n to n-1 and

interchanges f and a

*/

int *pn,*pi,*pa,*pf;

{

int t;

*pn = *pn-1;

t = *pf;

*pf = *pa;

*pa = t;

}

setvar2(pn,pi,pa,pf)

/* Sets n to n-1 and interchanges a and i

*/

int *pn,*pi,*pa,*pf;

{

int t;

*pn = *pn-1;

t = *pa;

*pa = *pi;

*pi = t;

}

s_tack(n,i,a,f,ps)

/* Creates a record containing

n,i,a, and f and inserts it

on stack s

*/

int n,i,a,f;

stack *ps;

{

stackrecord newrecord;

newrecord.info.n = n;

newrecord.info.i = i;

newrecord.info.a = a;

newrecord.info.f= f;

push(&newrecord,ps);

}

restore(pn,pi,pa,pf,ps)

/* Removes the top record from

stack s and copies its contents

into n,i,a,f

*/

int *pn,*pi,*pa,*pf;

stack *ps;

{

stackrecord value;

pop(ps,&value);

*pn = value.info.n;

*pi = value.info.i;

*pa = value.info.a;

*pf = value.info.f;

}

In addition to the array implementation, a stack can be implemented as a list. Since we have discussed two ways to implement lists, we know two ways to implement stacks as lists. One is to store the stack records in an array; the other is to store them in dynamic memory. We have already given an implementation of a stack using an array of records in Chapter 3--where availist (Section 3.7) actually acts as a stack. When avail is invoked, it removes the top record from the availist, in addition to returning a pointer to the record. Thus it has effectively popped the record. Likewise, reclaim may return a record to the front of the availist. Doing so, reclaim is essentially pushing a new record onto the availist. Availist serves as the head of a list, which itself serves as a list implementation of a stack. Of course, appropriate overflow and underflow checking must be built into avail and reclaim, respectively.

typedef struct record

{

struct whatever info;

struct record *link;

}stackrecord,*stack;

If we then define s as type stack**,** code can be written that is independent of its implementation. Setstack must initialize the stack to empty. This means setting s, the head of the list implementing the stack, to null. Push must now use malloc to allocate storage for the entry to be pushed onto the stack before setting its info field and inserting that record as the new first record on the stack. Pop must copy the info field value of the top record into value and then delete that record from the stack.

These stack operations are implemented as follows.

setstack(ps)

/* Initializes the stack s to empty */

stack *ps;

{

*ps = NULL;

}

empty(ps)

/* Returns true only if the stack s is empty */

stack *ps;

{

return(*ps == NULL);

}

push(pnewrecord,ps)

/* Inserts the record newrecord

at the top of the stack s

*/

stackrecord *pnewrecord;

stack *ps;

{

stackrecord *newentry;

newentry = malloc(sizeof(stackrecord));

newentry->info = pnewrecord->info;

newentry->link = *ps;

*ps = newentry;

}

pop(ps,pvalue)

/* Copies the contents of the top record

of stack s into value and removes the

record from the stack

*/

stack *ps;

stackrecord *pvalue;

{

if(!empty(ps))

{

pvalue->info = (*ps)->info;

*ps = (*ps)->link;

}

else

underflow(ps);

}

Notice that this implementation removes the artificial restriction imposed by LIMIT in the first implementation using an array. This is one of the advantages of using dynamic allocation by means of pointer variables.

It is very important to see that no matter what the implementation, as long as the stack is treated as a data abstraction when writing programs, the programs need not be changed, even if the programmer decides to change the implementation of the stack. Only the declarations and definitions related to the stack need be changed, as is evident in the following nonrecursive towers that uses the list implementation. It should be compared to the program of Section 4.5.1, in which the stack was implemented using an array.

#include <stdio.h>

#define NULL 0

typedef struct

{

int n;

int i;

int a;

int f;

}whatever;

typedef struct record

{

whatever info;

struct record *link;

}stackrecord, *stack;

setstack(ps)

/* Initializes the stack s to empty */

stack *ps;

{

*ps = NULL;

}

empty(ps)

stack *ps;

{

return(*ps == NULL);

}

push(pnewrecord,ps)

stackrecord *pnewrecord;

stack *ps;

{

stackrecord *newentry;

newentry = malloc(sizeof(stackrecord));

newentry->info = pnewrecord->info;

newentry->link = *ps;

*ps = newentry;

}

pop(ps,pvalue)

/* Copies the contents of the top record

of stack s into value and removes the

record from the stack

*/

stack *ps;

stackrecord *pvalue;

{

if(!empty(ps))

{

pvalue->info = (*ps)->info;

*ps = (*ps)->link;

}

else

underflow(ps);

}

overflow(ps);

/* Prints a message that the stack has overflowed */

stack *ps;

{

printf(" The stack has overflowed \n");

}

underflow(ps);

/* Prints a message that the stack has underflowed */

stack *ps;

{

printf(" The stack has underflowed \n");

}

main()

/* Driver for towers */

{

int n;

printf("\n enter a value for n \n");

scanf("%d",&n);

towers(n,1,2,3);

}

towers(n,i,a,f)

1 final nonrecursive version

/* Moves the top n disks

from peg i to peg f

*/

int n,i,a,f;

{

stack s;

1 allocates storage fors(an instance of typestack)

int done

setstack(&s);

done = FALSE;

while(!done)

{

while (n > 1)

{

s_tack(n,i,a,f,&s);

setvar 1(&n,&i,&a,&f);

}

printf("\n %d -> %d\n",i,f);

if(!empty(&s))

{

restore(&n,&i,&a,&f,&s);

printf("\n %d -> %d\n",i,f);

setvar2(&n,&i,&a,&f);

}

else

done = TRUE;

}

setvar1(pn,pi,pa,pf)

/* Sets n to n - 1 and

interchanges f and a

*/

int *pn,*pi,*pa,*pf;

{

int t;

*pn = *pn - 1;

t = *pf;

*pf = *pa;

*pa = t;

}

setvar2(pn,pi,pa,pf)

/* Sets n to n - 1 and

interchanges a and i

*/

int *pn,*pi,*pa,*pf;

{

int t;

*pn = *pn - 1;

t = *pa;

*pa = *pi;

*pi = t;

}

s_tack(n,i,a,f,ps)

/* Creates a record containing

n, i, a, and f and inserts it

on stack s

*/

int n,i,a,f;

stack *ps;

{

stackrecord newrecord;

newrecord.info.n = n;

newrecord.info.i = i;

newrecord.info.a = a;

newrecord.info.f = f;

push(&newrecord,ps);

}

restore(pn,pi,pa,pf,ps)

/* Removes the top record from

stack s and copies its contents

into n,i,a,f

*/

int *pn,*pi,*pa,*pf;

stack *ps;

{

stackrecord value;

pop(ps,&value);

*pn = value.info.n;

*pi = value.info.i;

*pa = value.info.a

*pf = value.info.f;

}

The problem of implementing many stacks simultaneously is introduced in the suggested assignment at the end of this chapter. More sophisticated algorithms for the management of the stacks are explored in Garwick [1964], Knuth [1973], and Korsh [1983].

To illustrate the use of stacks, let us consider the problem of evaluating arithmetic expressions. People are accustomed to writing arithmetic expressions in * infix notation*, where an operator appears between its operands. Consequently, programming languages generally use infix notation to be "user friendly." Thus the programmer can write

(((*a* + (*b*/*c* * *d*)) + (*a*/*w*)) * *b*)/(((*a* * *c*) + *d*) + *a*)

Arithmetic Expressions

a + (b * c) (a + b) * c

Prefix + a * bc * + abc

Infix a + b * c a + b * c

Postfix abc * + ab + c *

Consider the arithmetic expressions of Table 4.1. These arithmetic expressions are written in prefix, infix, and postfix notation. * Prefix *means that the operator appears to the left, before its operands, and

Note that the prefix and postfix expressions of the first column are equivalent ways to express the infix expression *a + *(*b * c*), while the prefix and postfix expressions of the second column are equivalent to (*a + b*)* ** *c*. Unfortunately, the *infix* expressions of both columns are identical. This means that, unless parentheses are used, there is no way to distinguish between *a + *(*b * c*) and (*a + b*)* * c* using infix notation. Yet we* can *choose the proper prefix or postfix notation to make clear which of the two is intended, even though no parentheses (or special conventions) are used. This holds true in general for arithmetic expressions. For this reason, prefix and postfix notations are called * parentheses-free* notations. Compilers can easily process prefix and postfix expressions. Since postfix expressions are generally used, they are the main focus of the discussion that follows.

Given an infix expression that is completely parenthesized, such as

((a+b) * (c/d))

a+b*c/d

((a+b) * (c/d))

(((a+b) *c)/d)

((a+ (b*c))/d)

(a+ ((b*c)/d))

(a+ (b* (c/d)))

ab+cd/*

1. Scan the postfix expression from left to right.

2. Whenever an operator is encountered,

3. Treat this replacement as an operand, and continue scanning from this point.

Thus the postfix expression is equivalent to the infix expression

((a+b) * (c/d))

((a+b) * (c/d)) ....ab+cd/*

(((a+b) *c)/d) ....ab+c*d/

((a+ (b*c))/d) ....abc* +d/

(a+ ((b*c)/d)) ....abc*d/+

(a+ (b* (c/d))) ....abcd/*+

These examples emphasize two points:

Input Operand Stack

a a

b b

a

c c

b

a

* (b*c)

a

d d

(b*c)

a

/ ((b*c)/d)

a

+ (a+ ((b*c)/d)

The rule to be used for a completely parenthesized infix expression is

1. Scan the infix expression from left to right.

2. When a "matched" pair of ''left" and "right" parentheses is encountered,

a+b*c/d

then when the * is encountered, the stacks appear as

Operand Stack Operator Stack

--------------------------------

b+

a

The operator * signals that, had the expressions been completely parenthesized, a *left* parenthesis would have occurred just *before* the *b*, or else a *right* parenthesis would have occurred just *after* the *b*. In other words, the appearance of the operator requires a decision as to whether *b* should be considered an operand of *or an operand of +. The standard rules resolve such ambiguities by assigning *priorities* or *precedence values* to operators, assuming a left-to-right scan of the expression. For the binary operators, +, -, *, /, and ** (for exponentiation), the priorities are as follows:

**1. **Exponentiation (**) has the highest priority.

**3. **Addition and subtraction (+, -) have the same priority.

A left parenthesis also needs a priority, the lowest.

(a+b) *c/d

*b* is to be associated with the + operator.

a+ (b*c/d**e) *f

To evaluate it, when the first * is encountered the situation will be

Operand Stack Operator Stack

--------------------------------

b (

a +

Operand Stack Operator Stack

---------------------------------

c*

b(

a+

In the example, after / and *d* are processed, the stacks are as follows:

Operand Stack Operator Stack

---------------------------------

d/

(b*c) (

a+

Operand Stack Operator Stack

---------------------------------

e**

d/

(b*c) (

a+

Operand Stack Operator Stack

----------------------------------

((b*c)/(d**e)) +

a

Operand Stack Operator Stack

-----------------------------------

f*

((b*c)/(d**e)) +

a

The algorithm for the evaluation of any infix expression can now be written. The algorithm, which follows, assumes that a character, when read, will be an entire operand or operator. This means, for example, that ** should be interpreted as a "character." The algorithm returns the value of the expression in evaluate.

1. Initialize the operand stack to empty.

2. Initialize the operator stack to empty.

3. While there is another input character,

if the current character is "(", then

push it on the operator stack;

else if the current character is an operand, then

else if the current character is an operator, then

if the operator stack is not empty, then

if the current character does not have greater priority than the top

operator stack character, then

pop the operator stack, remove the required number of operands

from the operand stack, apply the operator to them, and push the

push the current character onto the operator stack

else if the current character is ")", then

pop the operator stack and set topchar to the popped value

remove the number of operands required by topchar from the operand

stack, apply topchar to them, and

push the result onto the operand stack

pop the operator stack and set topchar to the popped value

4.While the operator stack is not empty,

pop the operator stack, remove the required number of operands from the

operand stack, apply the operator to them, and push the result on the operand

5.Pop the operand stack and set evaluate to the popped value

Notice that the evaluation of an infix expression requires two stacks rather than the one stack required for the evaluation of a postfix expression. Other operators may be introduced and given appropriate priorities. For example, the assignment operator, =, would be given a higher priority than **.

Suppose, rather than evaluating an infix expression, a programmer wished to translate it and produce the corresponding postfix expression as output. The reason is that postfix expressions can be executed directly, whereas infix expressions are tricky to evaluate. Moreover, if the translation can be done, then the postfix expression may easily be embellished to produce a machine language program for the evaluation of the original infix expression.

The following modification of the infix evaluation algorithm results in such a translation.

2. Instead of applying operators to operands, simply output the operators.

The queue, like the stack, is a useful data abstraction for retaining information in a specific order. A * queue* is a data structure with restricted insertion and deletion operations. Information may be inserted on the queue, but only at the

The queue acts like the pile of Community Chest cards in Monopoly. The top card is the only one that can be removed, and insertions to the pile can be made only at the bottom. If we think of the information stored as representing postponed obligations, then the queue gives access to the obligations in the order in which they were incurred. A popular mnemonic for helping to remember this characteristic is FIFO--first in, first out. Like LIFO, this is a common term in accounting and inventory control systems.

Queues can be implemented in the same basic ways as stacks--as an array of records, as a list with its records stored in an array, and as a list with its records stored in dynamic memory. As in the case of stacks, these implementations are discussed in that order.

A queue may be implemented using an array of records by first declaring

typedef struct

{

whatever info;

}queuerecord;

typedef struct

{

queuerecord queuearray [LIMIT];

int front, rear;

}queue;

queue q;

As with stacks, overflow and underflow should be checked in a general implementation. A typical queue situation is depicted in Figure 4.10(a) for the array implementation. Figure 4.10(b) shows the situation after 18, 32, and 15 have been removed and 17 and 20 have been inserted.

Storage for insertion of more records is available at the top of the queuearray, but not at the bottom. To ensure that all the relocated storage for queue is used before overflow occurs, programs "wrap around." That is, the queue is implemented so that the queuearray is viewed as a circle of records, with 0 following the LIMIT, 7. Front is used to point to the entry at the front of the queue, and rear is used to point to the array location in which the next

The insertion operation may then be implemented as follows:

insert(pnewrecord,pq)

/* Inserts newrecord at the rear of queue q */

queuerecord *pnewrecord;

queue *pq;

{

if ((*pq).front == -1)

{

(*pq).front = 0;

(*pq).queuearray[0].info = (*pnewrecord).info;

(*pq).rear = 1;

}

else

if((*pq).rear == (*pq).front)

printf("\n overflow \n");

else

{

if((*pq).rear <= (LIMIT - 1))

{

(*pq).queuearray[(*pq).rear].info =

(*pnewrecord).info;

(*pq).rear = (*pq).rear + 1;

}

else

{

if((*pq).front == 0)

printf("\n overflow \n");

else

{

4 there is room to wrap around, so the new entry is inserted at the start of the array andrearset to the next location

(*pq).queuearray[0].info =

(*pnewrecord).info;

(*pq).rear = 1;

}

}

}

}

Setqueue must set front and rear to minus one (-1). Empty will return the value *true* when front = -1, and *false* otherwise. The removal of a record can be implemented by a function remove, which returns in value the record that was deleted from the queue.

remove (pq, pvalue)

/* Deletes the front entry from

queue q and copies its contents

into value

*/

queue *pq;

queuerecord *pvalue;

{

if(empty(pq))

printf("\n underflow \n");

else

{

(*pvalue).info = (*pq).queuearray

[(*pq).front].info;

(*pq).front = (*pq).front + 1;

if((*pq).front == (*pq).rear)

2 if queue is empty, then reinitialize it

setqueue(pq);

if((*pq).front > (LIMIT - 1))

(*pq).front = 0;

}

}

Now we can turn to implementing a queue as a list with records stored in an array. The availist of Section 3.7 actually acts as a list implementation of a *queue* if reclaim returns a record to the *rear* of the availist. Thus queue can be implemented as a list of records stored in an array.

typedef struct record

{

whatever info;

struct record *link;

}queuerecord,*queue;

To bring together the major ideas of this chapter, a case study to check program structure for proper nesting is presented. Its main features are:

**2. **Demonstration of the use of the stack, treating it as a data abstraction

**4.** The different perspectives required to develop the two functions

* Nesting* means that one matching pair is wholly contained within another. When pairs are nested, they may not overlap, as do the two pairs in ( [ ) ]. The rules of nesting are the same for any sequence that is built by combining simpler sequences. They require that the start and end of each component be specified. Checking complex sequences to determine that these

Given a sequence of left and right parentheses, determine if they may be paired so that they satisfy two conditions:

**ii.** Each parenthesis occurs in exactly one pair.

If a sequence has a pairing satisfying both of these conditions, the sequence and pairing are * valid*. The problem is to determine whether a given sequence is valid or not. No sequence starting with a right parenthesis, ")", can be valid, since there is no preceding left parenthesis, "(", to pair with it. Any valid sequence must therefore begin with some series of

Consequently, the conclusion is that a solution to the problem is obtained as follows:

1. Pair the first adjacent left, "(", and right, ")", parentheses and remove the pair.

This solution may be implemented as in the function determine, which follows this paragraph. Note that the stack is treated as a data abstraction . Readchar is a function that reads into its parameter the next character of the input sequence and returns *true,* unless the character read was a specialchar used as a sentinel, and then it returns *false.* When determine returns, the entire input sequence has been read. Valid will return *true* if a pairing satisfying (i) and (ii) exists, and *false* otherwise.

determine(pvalid)

/* Returns true in valid only if the

input sequence is properly nested

*/

int *pvalid;

{

char currentchar;

struct

{

char topchar;

}topcharacter;

stack s;

*pvalid = TRUE;

setstack(&s);

while(readchar(¤tchar))

if(leftparen(currentchar))

push(¤tchar,&s);

else if(rightparen(currentchar))

if(!empty(&s))

{

pop(&s,&topcharacter);

if(!match(topcharacter.topchar,

currentchar))

*pvalid = FALSE;

}

else

*pvalid = FALSE;

else

process(currentchar,&s);

if(!empty(&s))

*pvalid = FALSE;

}

Leftparen returns the value *true* if its parameter is a left parenthesis, and false otherwise. Rightparen is defined similarly. Match returns the value *true* if topchar and currentchar are left and right parentheses, respectively.

1. Scan the infix expression from left to right.

2. When a "matched" pair of "left" and "right" parentheses is encountered,

Determine may be modified to obtain a function evaluate, by defining the process routine as follows:

1. When an operand is encountered, place the operand on top of an operand stack.

2. When an operator is encountered, place the operator on top of the operator stack.

The general function determine is actually more complex than need be for "paired parentheses." In fact, a stack is not even necessary. All that is really needed is to keep a tally of "(" parentheses, decreasing the tally by 1 every time a ")" parenthesis is read. If the tally ever becomes negative, then determine should, from that point, simply read in the rest of the input sequence and return *false*. Otherwise, if the tally is zero after the entire input sequence has been read, it should return true. Determine is implemented as shown in the nonrecursive function listed above because it will serve as the solution to the next problem, for which "paired parentheses" will be a special case.

Given a sequence of left and right characters, determine if they may be paired so that

**ii.** Each character occurs in exactly one pair.

If a sequence of left and right characters satisfies conditions (i), (ii), and (iii), the sequence and the pairing are *valid*. Condition (iii) then says that the sequence of characters between the left and right characters of each pair must be valid.

In conclusion, a solution may be obtained as follows:

1. Pair the first adjacent left and right parentheses that match, and remove the pair.

Function determine is also an implementation of this solution using a stack, assuming leftparen, rightparen, and match reflect the different left parentheses, right parentheses, and matched pairs, respectively. The stack is needed in order to implement this solution. It is no longer simply a question of increasing or decreasing a tally, depending on whether the program reads a "(" or a ")"parenthesis, and making sure it never goes below zero and ends at zero. It is not even enough to keep a distinct tally for each of the different kinds of "left" and "right" parentheses. This would not result in Figure 4.12(b), for example, being recognized as invalid, because each of the four numbers would satisfy the requirements just mentioned. It is condition (iii), and more than one kind of left and right parentheses, that makes the stack mandatory. Consider a pair satisfying conditions (i) and (ii). To satisfy condition (iii), the sequence of characters between the "left" and "right" parentheses of the pair must also be valid. In effect, a new set of tallies must be kept for that sequence, and they must satisfy the three conditions. The stack is actually holding *all* of these tallies. Each time a "left" parenthesis appears, it becomes a character in many sequences, in general, and the tally for it, associated with each of those sequences, must be increased by one. Pushing it onto the stack, in effect, increases all these tallies by one simultaneously. Similarly, popping the stack decreases them all simultaneously.

A left and right matching pair of parentheses with a valid sequence between them

A valid sequence followed by a valid sequence

In other words, a valid sequence is

*One* valid sequence surrounded by a pair of matching parentheses, or

A series of valid sequences, *each* surrounded by a pair of matching parentheses

(valid sequence)(valid sequence) . . . (valid sequence)

The following program is a recursive version of determine based on the recursive definition.

determine(pvalid,last)

/* Returns true in valid only if the input

sequence is properly nested; last must

initially contain a special character

used as the input terminator.

*/

int *pvalid;

char last;

{

char currentchar;

int done;

static int more;

done = FALSE;

more = TRUE;

while(!done && more)

17 loops through each input character

{

more = readchar(¤tchar);

if(leftparen(currentchar))

determine(pvalid,currentchar);

else if(rightparen(currentchar))

if(!match (last,currentchar))

*pvalid = FALSE;

else

{

done = TRUE;

last = SPECIALCHAR;

}

else

process(last,currentchar);

}

if(last != SPECIALCHAR)

*pvalid = FALSE;

}

[ ( [ ] ) ] ( ) { [ ] } #

[ ( [ 1 ] ) ] ( 4 ) { [ 5 ] } # (6 pairs of matching parentheses)

- 2 - - 6 -

- - 3 - -

and the recursive solution sees it as

[ ( [ ] ) ] ( 2 ) { [ ] } # (3 valid sequences each one surrounded by a pair of

- - 1 - - - 3 - matching parentheses)

where # denotes the specialchar.

**1. S**et* i* and *j* be two integers and define *q*(*i, j*) by *q*(*i, j*) = 0 if *i* < *j* and *q*(*i - j, j*) + 1 if *i* *j*

**a. **What is the value of *q*(7,2)?

**c. **Can we determine *q*(-3, -4)?

**2. **Let a be an array of type float and *i* and *n* be positive integers. The function

m(a,i,n) = a[i] if i = n and max(m(a,i + 1,n) ,a[i]) if i < n

**a. **Find m(a,i,n) if i = 1, n = 6, and a is

0. 6.8

1. 3.2

2. -5.0

3. 14.6

4. 7.8

5. 9.6

6. 3.2

7. 4.0

**3. **Let a be an array of type real, and *i* and *n* be positive integers. The function m(a,i,n) is defined by

(i + n)/2 means, "Do an integer divide of (i + n)/2."

**a. **Find m(a,i,n) for *i* = 1, *n* = 6, and a the array of Exercise 2.

**4. **Let *i* be a nonnegative integer. Find *b*(4) where

b(0) = 1

b(n) =b(0) Xb(n- 1) +b(1) Xb(n- 2)

+b(2) Xb(n- 3) + . . . +b(n- 1) Xb(0)n>0

**5. **Write a recursive function max corresponding to Exercise 2.

**6. **Write a recursive function max corresponding to Exercise 3.

**7. a. **Why does the recursive solution to the Towers of Hanoi problem use the minimum number of moves?

**b. **What is the number of moves it uses?

**8. **Consider the following nonrecursive algorithm for the Towers of Hanoi problem.

1. Label the disks 1, 2, . . ., *n* in increasing order of size.

2. Label the pegs *i, a,* and *,* respectively, *n *+ 1, *n *+ 2, and *n *+ 3.

**a.** Convince yourself that this correctly solves the Towers of Hanoi problem.

**b.** Is the recursive solution or this nonrecursive version easier to understand.

**9. **Suppose a fourth peg is added to the Towers of Hanoi problem.

**a.** Write a recursive solution for this problem.

**b.** Can you find a recursive solution that uses the minimum number of moves for this problem?

**10. **Mark any *n* distinct points on the circumference of a circle. How many triangles may be drawn whose vertexes lie on three of the *n* points?

**11. **How many ways may *k* distinct points be selected from the *n* points of Exercise 10?

**12. **Given a permutation of 1, 2, . . ., *n*, let *n _{i}* be the number of integers to the right of

**13. **Suppose 1 is implemented as a two-way list. Write a recursive function to reverse 1.

**14. **Implement the function of Exercise 5.

**15. **Implement the function of Exercise 6.

**16. **Compare the requirements for the stack storage required during execution for the implementations of Exercises 5 and 6.

**17. **Why are the more efficient versions of Section 4.4 more efficient?

**18. **The Fibonacci sequence is defined by

(0) = 0, (1) = 1

(n) =f(n- 1) + (n- 2) forn= 2,3,4 . . .

**a.** Write a recursive function fibonacci(n) to compute and print (*n*).

**b.** Analyze its time and storage requirements.

**19. a.** Translate the program of Exercise 18 and obtain as efficient a version as you can.

**b.** Analyze its time and storage requirements.

**20. **Write a nonrecursive program fibonacci(n), which takes *O*(*n*) time and uses only four local variables.

**21. a.** Write a function element with parameter *k*, which returns the value of the *k*th element on the stack of integers implemented as in Figure 4.8. For instance, if *k* is 1, it returns the value of the current first element. It does not disturb the stack at all. Assume you do not have access to the stack directly, but only through the push, pop, and empty routines.

**b.** Same as Exercise 21(a), except assume you do have direct access to the stack.

**22.** Two stacks are implemented in one array of length 1,000 as shown. The tops of the stacks are pointed to by top1 and top2 and grow toward each other. Write a procedure push that pushes the contents of v onto the stack indicated by s. s will have a value of 1 or 2. If the stack to which v is to be added is full, then push should not add it, but should return with s set to 0.

**23. **Write a function maxstack that returns in m the maximal element on a stack of integers implemented with pointer variables. Maxstack will return *true* when the stack is not empty, and *false* otherwise.

**24 **What does the following do?

pop(&s,&value);

push(&value,&s)

**25. **Why are parentheses not needed when prefix or postfix notation is used?

**26. **How do conventions eliminate ambiguity in infix notation?

**27. **Evaluate the postfix expression 3 6 + 6 2 / *8+.

**28. **Simulate the execution of the algorithm of Section 4.6.2 for evaluation of an infix expression on (*a * b*/(*c* + *d*)) + *e ** **.*

**29. **Simulate the execution of the translation algorithm of Section 4.6.3 on (*a * b*/(*c* + *d*)) + *e ** **.*

**30. **What priority must be given to the assignment operator, =, if the evaluation and translation algorithms for infix to postfix are to work on assignment statements as well as arithmetic expressions?

**31. **Write the function evaluate.

**32. **Describe how evaluate must be modified if arithmetic expressions are allowed to include function calls.

**33. **What will the pairing generated by the function determine be for the input sequence aa([[]()])zz?

**34. **Modify the function determine so that it outputs the pairs as follows:

1 2 3 4 5 6 7 8

if ( ( ( ) ) ( ) ) is the input sequence,

then the output will be the pairs 3 4, 2 5, 6 7, 1 8.

**35. **Modify function determine so that it also outputs ( ( ( ) ) ( ) ), for example, if the input is ( ( ( ) ) ( ) ).

**36. **How must determine be modified if some left characters may also be right characters, and they will always match each other? For example, let the left characters be a, (, [,b, with the "right" characters being a, ), ], b. Here a is matched with a, b with b, "("with ")," and "[" with "]." Then a[a] is not valid, but a[CC](aa)a and ab()aab[]a are.

**37. **Write the remove function for the array implementation of a queue.

**38. **Write the insert function for the pointer variable implementation of a queue.

**39. **Write the remove function for the pointer variable implementation of a queue.

**40.** Suppose function buffer has three parameters, q of type queue, e of type whatever, and op of type character. If op is r, then buffer returns after removing the top record of the queue and copying its value into e. If op is *n*, then buffer returns after inserting the value in e at the bottom of the queue. Write an implementation of buffer, assuming that access to the queue is only through the empty, remove, and insert routines.

**41. **A *deque* (pronounce like "deck") is a data abstraction that retains ordered information, but allows insertion and deletion at both its front and rear.

**42. **Suppose there is a program to keep track of the current board configuration in a game of Monopoly by using a circular array of records, each record representing a board position (such as Boardwalk), and queues for Community Chest and Chance. Discuss how the records should be defined, what pointers to records will be convenient, and how these pointers and the circular array should be processed on each turn.

**1. **Write and simulate a recursive program to reverse a list.

**3.** Write the permutation program so it treats the permutation as a data abstraction.