Two of the more common data objects found in computer algorithms are stacks and queues. They arise so often that we will discuss them separately before moving on to more complex objects. Both these data objects are special cases of the more general data object, an ordered list which we considered in the previous chapter. Recall that *A* = (*a*_{1},* a*_{2},* ...*,*a _{n}*), is an ordered list of elements. The

| procMAIN| |procA1||procA2||procA3|

| ___| | ___|| ___|| ___|

| ___| | ___|| ___|| ___|

| ___| | ___|| ___|| ___|

| callA1| |callA2||callA3|| ___|

|r:| |s:||t:|||

| ___| | ___|| ___|| ___|

| ___| | ___|| ___|| ___|

| end | | end || end|| end|

Associated with the object stack there are several operations that are necessary:

CREATE (*S*) which creates *S* as an empty stack;

ADD (*i,S*) which inserts the element *i* onto the stack *S* and returns the new stack;

DELETE (*S*) which removes the top element of stack *S* and returns the new stack;

TOP (*S*) which returns the top element of stack *S*;

ISEMTS (*S*) which returns true if *S* is empty else false;

These five functions constitute a working definition of a stack. However we choose to represent a stack, it must be possible to build these operations. But before we do this let us describe formally the structure STACK.

structureSTACK(item)

1declareCREATE( )stack

2ADD(item,stack)stack

3DELETE(stack)stack

4TOP(stack)item

5ISEMTS(stack)boolean;

6for allSstack,iitemlet

7ISEMTS(CREATE) :: =true

8ISEMTS(ADD(i,S)) :: =false

9DELETE(CREATE) :: =error

10DELETE(ADD(i,S)) :: =S

11TOP(CREATE) :: =error

12TOP(ADD(i,S)) :: =i

13end

endSTACK

The five functions with their domains and ranges are declared in lines 1 through 5. Lines 6 through 13 are the set of axioms which describe how the functions are related. Lines 10 and 12 are the essential ones which define the last-in-first-out behavior. The above definitions describe an infinite stack for no upper bound on the number of elements is specified. This will be dealt with when we represent this structure in a computer.

CREATE( ) :: =declareSTACK(1:n);top0

ISEMTS(STACK) :: =iftop= 0then true

else false

TOP(STACK) :: =iftop= 0thenerror

elseSTACK(top)

procedureADD(item,STACK,n,top)

//insert item into theSTACK of maximum size n;topis the number

of elements curently inSTACK//

iftopnthen callSTACK_FULL

toptop+ 1

STACK(top)item

endADD

procedureDELETE(item,STACK,top)

//removes the top element ofSTACKand stores it in item

unlessSTACKis empty//

iftop0then callSTACK_EMPTY

itemSTACK(top)

toptop- 1

endDELETE

(i) line 7: *ISEMTS*(*CREATE*):: = **true**

(ii) line 8: *ISEMTS*(*ADD(i,S*)):: = **false**

(iii) line 9: *DELETE*(*CREATE*):: = *error*

Queues, like stacks, also arise quite naturally in the computer solution of many problems. Perhaps the most common occurrence of a queue in computer applications is for the scheduling of jobs. In batch processing the jobs are ''queued-up'' as they are read-in and executed, one after another in the order they were received. This ignores the possible existence of priorities, in which case there will be one queue for each priority.

As mentioned earlier, when we talk of queues we talk about two distinct ends: the front and the rear. Additions to the queue take place at the rear. Deletions are made from the front. So, if a job is submitted for execution, it joins at the rear of the job queue. The job at the front of the queue is the next one to be executed. A minimal set of useful operations on a queue includes the following:

CREATEQ(*Q*) which creates *Q* as an empty queue;

ADDQ(*i*,*Q*) which adds the element *i* to the rear of a queue and returns the new queue;

DELETEQ(*Q*) which removes the front element from the queue *Q* and returns the resulting queue;

FRONT(*Q*) which returns the front element of *Q*;

ISEMTQ(*Q*) which returns true if *Q* is empty else false.

A complete specification of this data structure is

structureQUEUE(item)

1declareCREATEQ( )queue

2ADDQ(item,queue)queue

3DELETEQ(queue)queue

4FRONT(queue)item

5ISEMTQ(queue)boolean;

6for allQqueue,iitemlet

7ISEMTQ(CREATEQ) :: =true

8ISEMTQ(ADDQ(i,Q)) :: =false

9DELETEQ(CREATEQ) :: =error

10DELETEQ(ADDQ(i,Q)):: =

11ifISEMTQ(Q)thenCREATEQ

12elseADDQ(i,DELETEQ(Q))

13FRONT(CREATEQ) :: =error

14FRONT(ADDQ(i,Q)) :: =

15ifISEMTQ(Q)thenielseFRONT(Q)

16end

17endQUEUE

The axiom of lines 10-12 shows that deletions are made from the front of the queue.

Q(1) (2) (3) (4) (5) (6) (7) ... Remarks

front rear

0 0 queue empty Initial

0 1 Jl Job 1 joins Q

0 2 J1 J2 Job 2 joins Q

0 3 J1 J2 J3 Job 3 joins Q

1 3 J2 J3 Job 1 leaves Q

1 4 J2 J3 J4 Job 4 joins Q

2 4 J3 J4 Job 2 leaves Q

CREATEQ(Q):: =declareQ(l:n);frontrear0

ISEMTQ(Q) :: =iffront=rearthen true

else false

FRONT(Q) :: =ifISEMTQ(Q)then error

elseQ(front+ 1)

The following algorithms for ADDQ and DELETEQ result:

procedureADDQ(item,Q,n,rear)

//insert item into the queue represented inQ(l:n)//

ifrear=nthen callQUEUE_FULL

rearrear+ 1

Q(rear)item

endADDQ

procedureDELETEQ(item,Q,front,rear)

//delete an element from a queue//

iffront=rearthen callQUEUE_EMPTY

frontfront+ 1

itemQ(front)

endDELETEQ

ifrear=n- 1thenrear0

elserearrear+ 1.

procedureADDQ(item,Q,n,front,rear)

//insertitemin the circular queue stored inQ(0:n- 1);

rearpoints to the last item andfrontis one position

counterclockwise from the first item inQ//

rear(rear+ l)modn//advance rear clockwise//

iffront=rearthen callQUEUE-FULL

Q(rear)item//insert new item//

endADDQ

procedureDELETEQ(item,Q,n,front,rear)

//removes the front element of the queueQ(0:n- 1)//

iffront=rearthen callQUEUE-EMPTY

front(front+ 1)modn//advance front clockwise//

itemQ(front) //set item to front of queue//

endDELETEQ

The rat-in-a-maze experiment is a classical one from experimental psychology. A rat (or mouse) is placed through the door of a large box without a top. Walls are set up so that movements in most directions are obstructed. The rat is carefully observed by several scientists as it makes its way through the maze until it eventually reaches the other exit. There is only one way out, but at the end is a nice hunk of cheese. The idea is to run the experiment repeatedly until the rat will zip through the maze without taking a single false path. The trials yield his learning curve.

MOVE 1 2

-- --

(1) -1 0 north

(2) -1 1 northeast

(3) 0 1 east

(4) 1 1 southeast

(5) 1 0 south

(6) 1 -1 southwest

(7) 0 -1 west

(8) -1 -1 northwest

*g* *i* + MOVE(6,1); *h* j* + MOVE(6,2)*

For example, if we are at position (3,4), then position (3 + 1 = 4, 4 +(-1) = 3) is southwest.

set list to the maze entrance coordinates and direction north;

whilelist is not emptydo

(i,j, mov)coordinates and direction from front of list

whilethere are more movesdo

(g,h)coordinates of next move

if(g,h) = (m,n)thensuccess

ifMAZE (g,h) = 0 //the move is legal//

andMARK(g,h) = 0 //we haven't been here before//

then[MARK(g,h) 1

add(i,j,mov)to front of list

(i,j,mov) (g,h,null)]

end

end

print no path has been found

procedurePATH(MAZE,MARK,m,n,MOVE,STACK)

//A binary matrixMAZE(0:m+ 1, 0:n+ 1) holds the maze.

MARK(0:m+ 1, 0:n+ 1) is zero in spot (i,j) ifMAZE(i,j) has not

yet been reached.MOVE(8,2) is a table used to change coordinates

(i,j) to one of 8 possible directions.STACK(mn,3) holds the

current path// MARK (1,1) 1

(STACK(1,1),STACK(1,2),STACK(1,3)) (1,1,2);top1

whiletop0do

(i,j,mov) (STACK(top,1),STACK(top,2),STACK(top,3) + 1)

toptop- 1

whilemov8do

gi+MOVE(mov,1);hj+MOVE(mov,2)

ifg=mandh=n

then[forp1totopdo//goal//

STACK(p,1),STACK(p,2)

end

i,j);m,n);return]

ifMAZE(g,h) = 0andMARK(g,h) = 0

then[MARK(g,h) 1

toptop+ 1

(STACK(top,1),STACK(top,2),STACK(top,3))

(i,j,mov) //save (i,j) as part of current path//

mov0;ig;jh]

movmov+ 1 //point to next direction//

end

end

no path has been found')

endPATH

When pioneering computer scientists conceived the idea of higher level programming languages, they were faced with many technical hurdles. One of the biggest was the question of how to generate machine language instructions which would properly evaluate any arithmetic expression. A complex assignment statement such as

The first problem with understanding the meaning of an expression is to decide in what order the operations are carried out. This means that every language must uniquely define such an order. For instance, if *A* = 4, *B *= *C *= 2, *D *= *E *= 3, then in eq. 3.1 we might want *X* to be assigned the value

4/(2 ** 2) + (3 * 3) - (4 * 2)

= (4/4) + 9 - 8

= 2.

However, the true intention of the programmer might have been to assign *X* the value

(4/2) ** (2 + 3) * (3 - 4) * 2

= (4/2) ** 5* -1 * 2

= (2**5)* -2

= 32* -2

= -64.

Of course, he could specify the latter order of evaluation by using parentheses:

*X* ((((*A*/ *B*) ** (*C* + *D*)) * (*E* - *A*)) * *C*).

*X * ((*A*/(*B*** *C*)) + *(D*** E*)) - (*A* ** C*).

How can a compiler accept such an expression and produce correct code? The answer is given by reworking the expression into a form we call postfix notation. If *e* is an expression with operators and operands, the conventional way of writing *e* is called *infix*, because the operators come *in-*between the operands. (Unary operators precede their operand.) The *postfix* form of an expression calls for each operator to appear *after* its operands. For example,

infix: *A * B/C* has postfix: *AB* * *C*/.

Let us look at our previous example

infix: *A*/*B* ** *C* + *D* * *E* - *A* * *C*

postfix: *ABC* ** /*DE* * + *AC ** -

and trace out the meaning of the postfix.

Operation Postfix

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

T_{1}B **C AT_{1}/DE * + AC * -

T_{2}A/T_{1 }T_{2}DE * + AC * -

T_{3}D * E T_{2}T_{3}+ AC * -

T_{4}T_{2}+ T_{3 }T_{4}AC * -

T_{5}A * C T_{4}T_{5}-

T_{6}T_{4}, - T_{5 }T_{6}

procedureEVAL(E)

//evaluate the postfix expressionE. It is assumed that the

last character inEis an ''. A procedureNEXT-TOKENis

used to extract fromEthe next token. A token is either a

operand, operator, or ''. A one dimensional arraySTACK(l:n) is

used as a stack//

top0 // initializeSTACK//

loop

xNEXT-TOKEN(E)

case

:x= '' :return//answer is at top of stack//

:xis an operand:callADD(x,STACK,n,top)

:else:remove the correct number of operands

for operator x from STACK, perform

the operation and store the result, if

any, onto the stack

end

forever

endEVAL

1) fully parenthesize the expression;

2) move all operators so that they replace their corresponding right parentheses;

For example, *A/B* ** *C* + *D* * *E* - *A* * *C* when fully parenthesized yields

Next Token Stack Output

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

none empty none

A empty A

+ + A

B + AB

* + * AB

C + * ABC

Now the input expression is exhausted, so we output all remaining operators in the stack to get

Next Token Stack Output

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

none empty none

A empty A

* * A

( *( A

B *( AB

+ *(+ AB

C *(+ ABC

) * ABC +

* * ABC + *

D * ABC + * D

done empty ABC + * D *

Symbol In-Stack Priority In-Coming Priority

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

) - -

** 3 4

*,/ 2 2

binary +,- 1 1

( 0 4

procedurePOSTFIX(E)

//convert the infix expressionEto postfix. Assume the last

character ofEis a '', which will also be the last character of

the postfix. ProcedureNEXT-TOKENreturns either the next

operator, operand or delimiter--whichever comes next.

STACK(1:n) is used as a stack and the character '-' with

ISP('-') = -1 is used at the bottom of the stack. ISP and ICP

are functions.//

STACK(1) '-';top1 //initialize stack//

loop

xNEXT-TOKEN(E)

case

:x= '':whiletop> 1do//empty the stack//

STACK(top));toptop- 1

end

return

:xis an operand:x)

:x= ')':whileSTACK(top) '('do// unstack until '('//

STACK(top));toptop- 1

end

toptop- 1 //delete')'//

:else whileISP(STACK(top))ICP(x)do

STACK(top));toptop- 1

end

callADD(x,STACK,n,top) //insertxin STACK//

end

forever

endPOSTFIX

Up to now we have been concerned only with the representation of a single stack or a single queue in the memory of a computer. For these two cases we have seen efficient sequential data representations. What happens when a data representation is needed for several stacks and queues? Let us once again limit ourselves, to sequential mappings of these data objects into an array *V*(1:*m*). If we have only 2 stacks to represent. then the solution is simple. We can use *V*(1) for the bottom most element in stack 1 and *V*(*m*) for the corresponding element in stack 2. Stack 1 can grow towards *V*(*m*) and stack 2 towards *V*(1). It is therefore possible to utilize efficiently all the available space. Can we do the same when more than 2 stacks are to be represented? The answer is no, because a one dimensional array has only two fixed points *V*(1) and *V*(*m*) and each stack requires a fixed point for its bottommost element. When more than two stacks, say *n*, are to be represented sequentially, we can initially divide out the available memory *V*(1:*m*) into *n* segments and allocate one of these segments to each of the *n* stacks. This initial division of *V*(1:*m*) into segments may be done in proportion to expected sizes of the various stacks if the sizes are known. In the absence of such information, *V*(1:*m*) may be divided into equal segments. For each stack *i* we shall use *B*(*i*) to represent a position one less than the position in *V* for the bottommost element of that stack. *T*(*i*), 1 *i* *n* will point to the topmost element of stack *i*. We shall use the boundary condition *B*(*i*) = *T*(*i*) iff the *i*'th stack is empty. If we grow the *i*'th stack in lower memory indexes than the *i* + 1'st, then with roughly equal initial segments we have

*B* (*i*) = *T* (*i*) = *m*/*n* (*i* - 1), 1 i *n*

procedureADD(i,X)

//add elementXto thei'th stack, 1 in//

ifT(i) =B(i+ 1)then callSTACK-FULL(i)

T(i)T(i) + 1

V(T(i))X//addXto thei'th stack//

endADD

procedureDELETE(i,X)

//delete topmost element of stacki//

ifT(i) =B(i)then callSTACK-EMPTY(i)

XV(T(i))

T(i)T(i) - 1

endDELETE

**1**. Consider a railroad switching network as below

**3**. Complete the correctness proof for the stack implementation of section 3.1.

**4. **Use the queue axioms to prove that the circular queue representation of section 3.1 is correct.

**5.** A double ended queue (deque) is a linear list in which additions and deletions may be made at either end. Obtain a data representation mapping a deque into a one dimensional array. Write algorithms to add and delete elements from either end of the deque.

**6.** [Mystery function] Let *f* be an operation whose argument and result is a queue and which is defined by the axioms:

f(CREATEQ) :: = CREATEQ

f(ADDQ(i,q)) :: =ifISEMTQ(q)thenADDQ(i,q)

elseADDQ(FRONT(q), f(DELETEQ(ADDQ(i,q))))

**7.** A linear list is being maintained circularly in an array *C*(0:* n -* 1) with *F* and *R* set up as for circular queues.

a) Obtain a formula in terms of *F*, *R* and *n *for the number of elements in the list.

b) Write an algorithm to delete the *k*'th element in the list.

c) Write an algorithm to insert an element *Y* immediately after the *k*'th element .

What is the time complexity of your algorithms for b) and c)?

**8. **Let *L* = (*a*_{1},*a*_{2},* *...,*a _{n}*) be a linear list represented in the array

**9. **a) Find a path through the maze of figure 3.5.

**10. **What is the maximum path length from start to finish in any maze of dimensions *n* X *m?*

**11. **Write the postfix form of the following expressions:

d) (*A* + *B*) ** D* + *E*/(*F* + *A* * *D*) + *C*

**12.** Obtain isp and icp priorities for all the operators of figure 3.7 together with the delimiters '(',and')'. These priorities should be such that algorithm POSTFIX correctly generates the postfix form for all expressions made up of operands and these operators and delimiters.

**13. **Use the isp and icp priorities obtained in exercise 12 to answer the following:

**14.** Another expression form that is easy to evaluate and is parenthesis free is known as *prefix*. In this way of writing expressions, the operators precede their operands. For example:

infix prefix

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

A * B/C /* ABC

A/B ** C + D * E - A * C - +/A ** BC * DE * AC

A * (B + C)/D - G -/* A + BCDG

Notice that the order of operands is not changed in going from infix to prefix .

a) What is the prefix form of the expressions in exercise 11.

**15. **Write an algorithm to transform from prefix to postfix. Carefully state any assumptions you make regarding the input. How much time and space does your algorithm take?

**16. **Do exercise 15 but this time for a transformation from postfix to prefix.

**17. **Write an algorithm to generate fully parenthesized infix expressions from their postfix form. What is the complexity (time and space) of your algorithm?

**18. **Do exercise 17 starting from prefix form.

**19. **Two stacks are to be represented in an array *V*(1*:m*) as described in section 3.4. Write algorithms ADD(*i*.*X*) and DELETE(*i*) to add X and delete an element from stack *i*, 1 *i* 2. Your algorithms should be able to add elements to the stacks so long as there are fewer than *m* elements in both stacks together.

**20. **Obtain a data representation mapping a stack *S *and a queue *Q *into a single array *V*(1:*n*). Write algorithms to add and delete elements from these two data objects. What can you say about the suitability of your data representation?

**21. **Write a SPARKS algorithm implementing the strategy for STACK_FULL(*i*) outlined in section 3.4.

**22. **For the ADD and DELETE algorithms of section 3.4 and the STACK_FULL(*i*) algorithm of exercise 21 produce a sequence of adds and deletes that will require *O*(*m*) time for each add. Use *n *= 2 and start from a configuration representing a full utilization of *V*(1:*m*).

**23. **It has been empirically observed that most programs that get close to using all available space eventually run out of space. In the light of this observation, it seems futile to move stacks around providing space for other stacks to grow in if there is only a limited amount of space that is free. Rewrite the algorithm of exercise 21 so that the algorithm terminates if there are fewer than *C* free spaces*. C* is an empirically determined constant and is provided to the algorithm.

**24. **Another strategy for the STACK_FULL(*i*) condition of section 3.4 is to redistribute all the free space in proportion to the rate of growth of individual stacks since the last call to STACK_FULL. This would require the use of another array *LT*(1:*n*) where *LT*(*j*) is the value of* T*(*j*) at the last call to STACK_FULL. Then the amount by which each stack has grown since the last call is* T*(*j*) - *LT*(*j*). The figure for stack *i* is actually *T*(*i*) -* LT*(*i*) + 1, since we are now attempting to add another element to *i*.

**25. **Design a data representation sequentially mapping* n* queues into all array* V*(1:*m*). Represent each queue as a circular queue within *V*. Write algorithms ADDQ, DELETEQ and QUEUE-FULL for this representation.

**26. **Design a data representation, sequentially mapping *n* data objects into an array *V*(1:*m*). *n*_{1} of these data objects are stacks and the remaining *n*_{2} = *n* - *n*_{1} are queues. Write algorithms to add and delete elements from these objects. Use the same SPACE_FULL algorithm for both types of data objects. This algorithm should provide space for the* i-*th data object if there is some space not currently being used. Note that a circular queue with space for *r* elements can hold only *r* - 1.

iv) Try i), ii) and iii) in sequence, restarting with i) whenever a move is made.

v) If no move is made via (i)-(iv) move a card from the stock to the waste pile and retry (i).

i) all the cards have been played to the output or

ii) the stock pile has been exhausted and no more cards can be moved