104 casi Dar Siractures REFERENCES Donal B. Knuth, The Art of Computer Programming, Addison-Wesley, Reading, Massochusets, 1984. Jean Paul Tremblay and G, Paul, Sorenson, An Introduction to Data. Structures with Applications, McGraw-Hill, New York, 1987. John Welsh, John Elder and David Bustrd, Sequential Program Structures, Prentice Hal, Englewood Cliffs, New Jersey, 1981. R. Hind, Effient Dynamic Stotige Matiagerient Wi Bidy System, Proceedings of IEEE ‘Symmposin.on Foundations of Compute Sclence, Vol. 19, 123-130, A978)... yt “Phiomas! L Naps, Introduction to. Data 'Sirutures with: Cy West Puplishing Company, Iv West Virginia 1986. / fat tn Stacks 4 INTRODUCTION |A stack is linear data strcture and Yery much useful in various applications of computer science. The implementation of the majoiy.of systems programs i simplified using this data structure. Before discussing this date structure, letus first consider a few examples ofthe stack Phenomenon ‘Shunting of trans in a railway yard Suppose there is a railway yard with a single wack, Trains enter into the railway yard for placement, and when they esti is justin opposte oder to that they had entered, i. the lst tan comes out fist (se Figure 4.1) Shipment in a cargo For the shipment of goods, they are loaded into < cargo compartment. At the destination hey are unloaded exactly in the opposite sequence to that in which they were loaded. That i, the g00ds loaded last get unloaded firs. Plates on a tray Suppose chef placed the dishes on a tay one sbove the other. The waiter served the dishes ‘othe customers in the opposite order that the chef placed them, that is, the dish a the top which Ms106 Casi Date Sructures Gonds in aca rraneina alley yard Figure 44 Some examples of stacks. Pes on aay was placed last by the chef is serviced first. The frst dish placed by the chef on the tray is seeviced last by the waiter ‘From the above examples, itis clear that a stack is something which follows the latin fist- cout strategy. This is why a stack is altematively termed LIFO (Last-In-Fist-Ou0. 42 DEFINITION [A stack isan ordered collection of homogeneous data elements where the insertion and deletion operations take place at one end onl. ‘Like am aray and linked list, a stack is also a linear data stracture but the only difference is that in the case of the former two, insertion and a deletion operations can take place at any position. The insertion and deletion operations in the case ofa stack are specially termed PUSH and POP, respectively, and the postion of the stack where these operations are performed is known a the TOP of the stick, An element in a stack is tenmed an ITEM, The maximum ‘number of elements that a stack ean accommodate is termed SIZE. Figure 4.2 shows a typical view of a stack data structure ust PoP 10° Botm|__ Figure 42. Schematic dagram of a stack Stacks_107 43. REPRESENTATION OF A STACK [A sack may be represented in the memory in various ways. There are two main ways: using ‘one-dimensional array and a single linked list. Representations of stacks in s memory are discussed in the following two sections. 43:1. Array Representation of Stacks First we have to allocate a memory block of sufficient size to accommodate the full capacity ofthe stack. Then, starting from the frst location ofthe memory block, the items ofthe stack can be stored in @ sequential fashion. Tn Figure 4.32), ITEM, denotes the th item inthe stack; and u denote the index range ofthe array in use; usually the values of these indices are 1 and SIZE respectively. TOP is @ pointer to point the position of the array up t> which itis filled with the items of the stack. With this representation, the following two ways can be stated: EMPTY: TOP <1 FULL: TOP2u Index 10 ray ‘Stack Head [tent —]Be%0" real tem 2 eG + =f nef | Tet (2) Ary representation ota tack (0) Like it eresentation ofa stack Figure 43 Two ways of representing stacks 432 Linked List Representation of Stacks Although array representation of stacks is very easy and convenient but it allows the representation of only fixed sized stacks. In several applications, the sizeof the stack may vary dating program execution. An obvious soluion to this problem is to represent a stack using linked list. A. single linked list structure is sufficient to represent any stack. Here, the DATA field is forthe ITEM, and the LINK field is, as usual, to point to the next item. Figure 4.3(b) depicts such a stack using a single linked fst. . Tn the linked list representation, te first node on the lists the curent tem that is the item ‘at the top ofthe stack and the last node is he node containing the bottom-most item, Thus, & PUSH operation wll add a new node in the front and a POP operation will remove 2 node from the front of the list. The SIZE of the stack is not important here because this representation allows dynamic stacks instead of stale stacks, as with arrays108 _classiDateSractures In the linked list representation of a stack, whether a stack is empty or not can be ascertained by testing the LINK field ofthe STACK_HEAD node. Note that atest for overflow is not applicable in this case 44 OPERATIONS ON STACKS ‘The basic operations required to manipulate a stack are: PUSH To insert an item into stack POP To remove an item from a slack STATUS To know the present state of a stack Let us define all these operations of a stack. Fist, we will consider the above-mentioned operations for a stack represented by an aray : Algorithm Push_Array Input: The new item ITEM to be pushed onto it ‘Output: A stack with a newly pushed ITEM at the TOP position Data structure: An array A with TOP as the pointer. [Se SCSCSSSCSCSSC“SstsSSCti‘SSWY WTOP 2 SIZE then 1 2. Print Stack is full” 3. Else 4 Top=T0P +1 5. A{TOP)= ITEM 6. Boalt 1. Stop Here, we have assumed that the aray index varies ftom 1 to SIZE and TOP points the location of the current top-most item inthe stack, The following algorithm Pop_ Array defines the POP of an item from a stack which is represented using an amay A. Algorithm Pop_Array Input: A stack with elements. (Output: Removes an ITEM from the top of the stack if it is not empty Data structure: An array A with TOP as the pointer. Steps: WTOP < | then 1 | 2. Print Stack is empty” 3. Ble 4. EM = AITO?) 5. TOP=TOP-1 6 Boalt 1. Stop stats 109 In the following algorithm Stans Array, we test the various states of @ stack such as whether itis full or empty, how many items ae right nw ini, and read the current element a the top without removing it, ec. Algorithm Status_Array Input: A. stack with elements Ouaput: States whether itis empty or full, available free space and item at TOP. Data structure: An array A with TOP as the sointe. | Steps: 1, WTOP < 1 then 2. Print “Stack is empty” 3. Else 4 W(ToP 2 SIZE) then 5 Print "Stack is ful” 6 1 8 Be Print “The clement at TOP is, AITOP] fee = (SIZE ~ TOPYSIZE * 100 D Print "Percentage of fee stack is 10. Endl HL, Endlt 22. Stop [Now let us see how the same operations can be defined fora stack represented with a single linked list Algorithm Push_LL Input: ITEM isthe item to be inserted. Ourput: A single linked list with a newly inserted node with data content ITEM. Data strcture: A single linked list structure whose pointer tothe header is known from STACK HEAD and TOP is the pointer to the first node ‘Stepae 1 new = GetNode(NODE) | Inert at from 47 TOP = new STACK_HEAD-LINK = TOP Stop | ‘Algorithm Pop LL Input: stack with elements, Ouiput: The rewoved item is stored in ITEM. ata siructure: A single linked list structure whose pointer to the header is known from STACK HEAD and TOP isthe pointer tothe first node120 _ClasieDota Sucre “Stools 111 ‘Steps: 1, IETOP = NULL. 2. riot “Stack is empty” 3. Est 4. Hse 5. py =TOPLINK 6 ITEM = TOP-»DATA | 7. STACK HEADLINK = ptr 8 TOP=prr 9. Endl | 10. Stop ‘The operation Stanes now can be defined 25 follows: Algorithm Status LL) Inputs A stack with elements. Ourput; Status information such as its state (empty or full), numberof items, item atthe TOP. ‘Data structure: A. single linked list structure whose pointer to the header is known from STACK HEAD and TOP is the pointer to the first node. STACK_HEAD-LINK If (ptr = NULL) then Priot "Stack is empty” e 1 2. 3 4 5. nodeCount = 0 6 While (pr # NULL) do 1 8 9. 0. Print “The item at the front is", TOP-DATA, “Stack consis”, nodeCount, “Number of items” [Assignment 4.2 (Multiple stack) 1a several applications, more than one stack may be required together. Some stacks overflow svhereas others are nearly empty. Suppose an application requires two stacks X and Y {Figure 44), One can define an array A wih N elements for tack X and another aay with _Nyelements for stack Y. Now instead of defining two separate aay A and B, we can define a single aay, say AB, with N = N, + N, elements for X and ¥.together. Let us define the Savting locations of items for stack X anc stack, ¥ as AB and ABN] respectively and X "grows tothe right whereas ¥ ‘grows’ tothe let lf frome sored | | | : ‘Sax ‘Seay Figure 44 A multiple stack ‘With this scheme: Sverflow will occor ealy wihén X and ¥ together have! more than Nv | elements. "This technique will usually decrease the number of situations ‘of occurrence of ‘overflow even though we have not increased the total amount of space reserved forthe two Using this scheme, we ed the modified veisions of PUSH_A and POP_A operations as | \PUSHLX, PUSH_Y; POP:X, and POP-Y: Similarly, the operation’ SPATUS:AB has'to be defined to test the state of empty’ full, percentage of space occupied by X and Yet Write the basic operations for the implementation of such-a muli-stack. 45 APPLICATIONS OF STACKS Various applications of stacks are known, A classical application in a compiler design is the evaluation of arithmetic expressions; here the compiler uses a stack to translate an input arithmetic expression into its comtesponding object code. Some machines are also known which use built-in stack hardware called ‘stack machine’, Another important application of a stack is ‘uring the execution of recusive programs; some programming languages use stacks to run recursive programs. One importa feature of any programming language is the binding of memory variables, Such binding is determined by the scope rules. There are two scope rules knowin: the static scope rale and the dyna scope rule. Implementation of such scope rules is possible using a stack known as a run rine stack ‘The following subsections highlight the above-mentioned application of stacks. 45.1 valuation of Arithmetic Expressions ‘An atithmetic expression consists of operands and operators. Operands ae vassbes or Constants and opertars are of varius types suchas arithmetic unary and binary operators (or example, — (unary), + (addition), ~ (subtraction), * (multiplication), 1 (vision, * (exponentiation), % (remainder modulo), et), relational operators (for example, <, >, <=,A12__ClusieData Structures <>, >, ee), end Boolean operators (such as, AND, OR, NOT, XOR, etc). In addition to these, parentheses such as “(° and ‘Y' are also used. A simple arithmetic expression is cited below: ASB*C/D-E*F*G ‘The problem to evaluate this expression isthe order of evaluation. Thee are two Ways {0 fix it. First, we can assign to each operator a precedence and associativity. For example, a set of usual operators with their precedence and associativity is given in Table 4.1, ‘Table 41 Precedence and associaity of operators Operators Precedence ‘Associatvny = (enan), xunary), NOT 6 ~ * (exponentiation) 6 Right to et + (oukipicaton,/ (vision) 5 Left to sght 4 (edition), ~(@dbuasion) 4 Left wo sight Sa hOe 3 Left wo it AND 2 Left ight, 8, XOR 1 Left wo sight “Thus, with the above rules of precedence and associativity of operators, the evaluation will take place for the above-mentioned expression in the sequence (sequence is according to the number 1, 2,3, .., et) stated below: It should be noted that the above rules for precedence and associativity vary from one programming language to another "Another way of fixing the order of evaluation is parenthesizing the expression fully; this allows one to override the rules for precedence and associativity. The following is the parenthesized version of the same expression: Input: (A + B) * (CID) ~ (E* * GY) (A fully parenthesized expression) ‘With this parenthesizatin, the innermost parenthesis pat (called sub expression) will be evaluated first, then the next innermost, and so on; such a sequence of evaluations is shown below: Sects 113. Whatever way we may specify the order of evaluations, the problem is that we must scan the expression from left to right repeatedly. Hence, the above-mentioned processes are inefficient because ofthe repeated scanning recuired, Another problem isthe ambiguity about how the compiler can resolve to generate a comect code for a given expression. The fast ‘problem mainly occurs for a parially parntheszed expression. These problems can be solved in the following two steps: 1. Conversion of a given expression into < special notation 2. Evaluaion/production of an object code using a stack [Notations for arithmetic expressions “There are thre notations to represent an arithmetic expression, viz. infix, prefix and postfix (or suffi). The conventional way of writing an expression is called infix. For example, A+B, C-D, E*F, Gilt,ete ere, the notation is < “This is called inf because the operator comes in between the operands on the other hand, uses the convention The pref notation, Here, the operator come before the operands. The following are simple expressions in prefix rotation AB, ~CD, ‘The prefix notation was introduced by the Polish mathematician Jan Lukasiewicz and hence also termed Polish notation “The last notation is called the postfix (or sfx) notation where the operator is suffixed by operands *EF, IGH, ec The following expressions are in postfix notaion: ABH, CD-, EF, GH), ete. “The posix notations just eves ofthe Polish rotation, hence tis also termed reversed Polish f114 _caesioData Sacre 1 may be noted that in all of the above notations, a unary operator precedes its operand. ‘An expression given in infix notation can easily be converted into its equivalent prefix or postin notion. The flowing ri aplie tcone an infix expen into a pots ‘¢ Assume the fully parenthesized version of the infix expression ‘¢ Move all operators so that they replace their corresponding right part of parentheses ‘¢ Remove all parentheses. ‘The following example illustrates this conversion. For simplicity, Jet us consider a ful i ene plicty, let us consider a fully Input: (A + ((B * €) ~ D)) * (E ~ (AC) (A fully parenthesized expression) (As{(BAC)~0))(E-(AC))) Hl ot LU LU) (Arrows point from operators to their corresponding right parenthesis.) (A(@BCAD-+EAC/-* (Operators are moved to their respective right parentheses.) Ourput: ABC*D-+EAC/~* (All parentheses are removed yielding the postfix expression.) AA similar technique can be applied to obtain the prefix notation fora given infix notation but moving the operators corresponds to the left parenthesis ‘Three notations for the given arithmetic expression ate listed below: Inf: (A + (B 4 €) ~ D)) * (E ~ (AC) Prefix: * +A BCD ~ B/AC Postfix: ABC“ D = + EAC/- * ‘The following points may be observed from the above three notations: 1. In both pref and postfix equivalents of an infix expression, the variables are in the same relative positions 2, The expressions in prefix or postfix form are completely parenthesis free 3, The operators are reaanged according tothe rules of precedence of operators. ‘Out of these three notations, the postfix notation has certain advantages over the other rotations from the computational point of view. The main advantage of postfix isis evaluation, During the evaluation of an expression in postfix notation it i no longer required to scan the expression from left to right several times, but scanning is required exactly once. This is possible using a stack and will be discussed shortly. sds 185 “Thus, evaluation of an expression is a tworstep process. First, we have t convert the expression int its postfix notation, and then etluate this expression in pstix notation In each Step. the stack is the main data stractre that s sed to accomplish these tasks “The uses of the stack for the purpose ani the above-mentioned procedures are discussed below. We will assume the array representation of a stack in our discussions. Conversion of an infix expression fo postfix expression ‘To formalize the conversion method, we will assume simple arithmetic expressions and * (exponentiation) operators only (i.e. without unary operators, The expression may be parenthesized or containing the +, Boolean operators and relational operatots) anparenthesized ist, we have to append the symbol *) as the delimiter at the end of a given infix expression and intlize the stack with °C. These symbols ensure that either the input o he stack is exhausted ‘Our nent step is iterative: read one input symbol at atime and decide whether it has to be ‘pushed ono the stack or not. This decision willbe govered by Table 4.2. Table 4.2 Instack and h-coming pies of symbols ‘Smbol| Trsteck Tecoming priory value priority value operand ¢ ) aS 8 From te tbl, it canbe noted that fora synbol we have considered two prt values, siz innucl puoi and incoming prot valves. A symbol wil be pushed onto the stack if i incoming pony valve fs geste than te in-stack poy vale ofthe topmost element Sina, bol wl be popped from te stack is in-stck privy vale greater than treat io te incoming provi valve ofthe incoming clement, In order to define the tlgonthm, we will assume the following factions ReadSymbol(): From a given infix expesion, this wil ead the next symbol ISP. Returns the in-stck pony vale fora symbol X CRUX, Tis funtion ret the in-coning pioty valve fora symbol X Output: Append the symbol X ito the resultant expression. Leas assume that a stack of capacity SIZE’ known and TOP isthe came pointer in it PUSH and POP ae wsual operations of the stack : Algorithm tnfxToPostix Input: E, simple arithmetic expression in infix notation delimited at the end by the right parenthesis incoming and in stack prion values for ll possible symbols in an aided expression,116 cose Date structures Ouput: An arithmetic expression in postfix notation Data structure: Array representation of a stack with TOP as the pointer to the top-most element. ‘Steps: 1. TOP = 0, PUSH((’) 1 Wiitze the stack 2. While (TOP > 0) do 3. item = EReadSymbol() 1 Scan the next symbol in infix expression ee) 11 Get the next item from the stack 5. Case item = operand ‘TE the symbol is an operand 6 PUSH) Tee sige al remsin same 1 Ovtputiem) 11 Ada the symbol into the output expression & Case item =), Scan teaches to its end 9. While x4 °C do ‘Till the left match isnot found 10. Outputs) i POR) | 2. EnaWhile 13, Case: ISPQ) 2 ICP(vem) 4 While (ISP(x) > ICPGitem)) do 15, Output(s) 16. POPC) v, EndWhile 8, PUSH) 19. PUSH (item) 20." Case: ISPtx) < ICP(item) 2. PUSH) 2, PUSH (tem) 23, Otherwise: Print “lnvalid expression” 24. RndWhile }25. Stop Note: This is @ procedure irespective of the type of memory representation ofthe stack to convert an infix expression to its postfix form using the basic operations of the stack, namely PUSH and POP. These operations can be replaced with their respective versions and hence implementable to stack with any type of memory representation EXAMPLE 4.1 Let ws illustrate the procedure InfixToPostfx with the following arithmetic expression Input: (A+B) * C ~ D*E)/F) Gali form) Symbol reading: 123 45 67 8 910111213 1415 16 sats 117 Read Stack Oupus symbol Inia 1 2 « A 3 a 4 AB 5 c ape 7 ts AB 4 a AB+c 3 iS ABeC* 9 (6 ABeCS 0 (6 AB+CSD i ee AB+CAD 2 co AB ECS DE ia C AB+C*DE* 18 cr AB SCA DE* 15 cr ABYC" DEF 6 AB YC* DES F/— Oupu: AB+C*EE*F/~ (gostix form) ‘The above procedure assumes thatthe input infix expressions are according to the right syntax So, ifthe input expression is not coeet its postfix form will not be correet. Extending the same idea, we can incorporete relational, Boolean and unary operators in the above procedure ‘ei the algo fe a an Ue Ras . GaeMACADSE-R/G. : GyA+*B—C ‘ F 2 il) (A$ BYE C-—D) a sto WANED) OLD 2 Rew a ee eye ‘ |i Ney goin ie 7oPonf 0 Snir api evrelson ninngBooleen m ne lial opesy td -opetaié to their equivalent postix form, gorithm IafeTOPOsite, we ssume thatthe inpot expression is omet. That is tee is Sick rete. But tpt eseson may wel om 10. Pdr “ADD 79 Ii ete AL PUSH (i) —— Ceetiem re Pom u ror IS. ProduceCode(y, x, ‘SUB’, Ti) 1 Pustie Motos tt i 2 PndaCede x MOL 2 poster [caw = 3 x 3% PredueCoe D1, 79 os —_pusHeny 2 Otrvs teat ein ip = ew 11 Read for the next symbol from E 1 The index is incremented 30. item = EReadsymbol() EXAMPLE 44 The above algorithm is usted with the following example: nfs: (A +B) * C/D Posifit: AB +C*D/ Input: B+ C*D/# sacts 128 ‘The production of codes acconding to the algorithm PasyfxToCode is given below: ‘Seameed Content of stack ‘Action Code geeraied pmo! a a PUSHA B AB Pusey + 1 =ByeA LDA PRODUTE.CODE(A, B, “ADD',T1) ADD B PUsHCT) STATI c mc PUSH) . n xeGy=T! WaT! PRODUCE, CODETI, C, ‘MUL'T2) MUL PusHCT) STAT > mp PUSH) i B x=D,y=T Lata DvD STATS ’ a ‘Assignment 4.4 (@) Consider en expression which contains relational and Boolean operators. Formulate the precedence values required for these operators to convert such an expression to reversed Polish notation. {b) Moidfy the slgorthit PostfoxToCode so'that it will also handle the vnary operators. (©) Modify the algorithm PostfoxToCode Tor the six relational operators <, > <=, >=, <>, ) and four Boolean operators (AND, OR, NOT, XOR). 452. Code Generation for Stack Machines In Section 45.1, we discussed the generation of codes for a given arithmetic expression in postfix form. The codes are ofthe type called single address codes. These codes are for those machines which maintain a numberof registers; the egsters are to store the temporaries. One problem using other machines, which have a very limited numberof registers, is how to handle the storage of intermediate result ‘Some machine architectures are known which use a stack instead of registers to store ‘emporaies or intermediate results; obviously the stack size inthis ease should be adequate enough to handle a large expression, Here, we will present the description of a simple hypothetical machine to illustrate the comept of code generation for the postfix form of ahmetic expressions. Let us assume the following set of instuctions (given in mnemonic forms) ofthe stack machine,152 Case Data Sructres ()-A#B-CIA for 3.¢ (@) (A+B)*C+DIB+A*C)+D (@ AB*C+D*E-A*C Convert the above expression into (i) Postfix notation (ii) Prefix notation 4.12 List all the prime factors of the given integers in descending onder. (Hints Use stack} 4.13 Devise a method that will produce all permutations ofthe fist V integers using tack. 4.14 ‘There i a variation inthe original Eulid’s algorithm for computing the greatest common divisor of two integers Mand N. According tothe modified Euclid’s algorithm, GCD(M-N,N) if MN iM ity=0 (GCDM,N = Mt) EN > GcD(at,N) Using only a stack, write a procedure to compute the GCD as per the modified Euclid’s rethod. REFERENCES Bruno, J. L, and T. Lassagne, The generation of optimal code for a stack machine, Journal of the ACM, July 1975, Donald E. Knuth, The Art of Computer Programming, Vol. 2, Addison-Wesley, Reading, ‘Massachusetts, 1984, Forsythe, Ad., T.A. Keenan, et al, Computer Science: A First Course, John Wiley & Sons, New York, 1986. Harrison, M.C., Data Structures and Programming, Glenview, Berkeley, California, 1985. Sethi, Rajeev and J. Ullman, The generation of optimal code for arithmetic expressions, Journal of the ACM, Vol. 10, October 1970. Queues SA INTRODUCTION A. queue is simple but very powerful data strctue to solve numerous computer applications Like stacks, queues are also useful 1 solve various system programs. Let us discuss some simple applications of queues in our everyday life a8 well as in computer science before undertaking the study this data structure. Queuing in front of a counter Suppose there aze a number of customers in font of counter to get service (Say, to elect tickets or to withdraw/deposit money in a teller of a bank), Figure 5.1(a). The customers are fomning a queue and they willbe served in the oder they atived, tat is, a customer who comes fist will be served first. Figure 6.1(a) Cueve of customers 183154 Cassie Dota Stracrres Traffic control at a tuning point ‘Suppose there isa turning point in «highway where the trafic has to tur. See Figure 5.1(b). All the trafic will have wait inline tl it gets the signal for moving. On geting the °Go' signal the vehicles will tur on a frst come, fist tum basis, Figure &:1(0) Traffe passing at a turing point Process synchronization in multiuser environment In a multi-user environment, more than one process is handled by the monitor (operating system), See Figure 5.1(c) The tnee different states that a process may have are the following READY, RUNNING, and AWAITED. A process isin the READY state when it is submitted to the system for execution. A process is in the RUNNING state if itis curently under ‘execution. Similarly, 2 process will be transfered to the AWAITED state when it requires resource(s) which islare busy. In order to synchronize the execution of processes, the monitor has to maintain to queues, namely QU and Q2, for READY and AWAITED states respectively where & process which entered a queve frst will be exited first ‘runing Figure §:1(c) Queues of processes Resource sharing In a computer centre In a computer cente, where resources are limited compared to the demand, users must sign & waiting egiste, See Figure 5.1(4). The user who has been waiting fora terminal forthe longest quewes 155 period of time gets Hold of the resource firs, then the second candidate, and so on. Here the Waiting list maintains a quewe and the first siged willbe the frst allowed. += Watieg roger Figure 5:1(8) A waltng quove of users in 2 computer centre 52 DEFINITION Like a stack, a queve isan ordered collection of homogeneous data elements; in contrast with the stack, here, insertion and deletion opeatios take place at two extreme ends. ‘A queve is also linear data structure like an aray, a stack and a linked list where the cowdering of elements isin a liner fashion, The only difference between a stack and a queue is that inthe ease of stack insertion and deletion (PUSH and POP) opertions are at one end (TOP) only, but in a queue insertion (called ENQUEUE) and deletion (called DEQUEUE) ‘operations take place at two ends called the REAR and FRONT of the queue, respectively. Figure 5.2 represents a model of « queue structure, | Ene —e| « Figure 6.2. Model of 2 queue An element in a queue is termed ITEM: the umber of elements that a queve can accommodate is termed LENGTH. rom the examples mentioned in Section 5.1 and the definition as stated above, iis evident that a data in a queue is processed inthe same order as it had entered, that is on a first-n, Fist- Out basis, This is why a queue is also termed firs-in first-out (FIFO).156 cassie Datasiractures 5.3 REPRESENTATION OF QUEUES ‘There are two ways to represent a queue in memory 1. Using an array 2, Using a linked list ‘The first kind of representation uses @ one-dimensional aray and it is a better choice where a ‘queue of fixed size is requied. The other representation uses & double linked list and provides 4 queue whose size can vary during processing ‘The following two subsections describe the representation of queues in memory. 53.1 Representation of a Queue using an Array ‘A one-dimensional array, say Q[l ...N] can be used to representa quete. Figure 5.3 shows ‘an instanceof such a queve. With this epresentaton, two pointers, namely FRONT and REAR, ‘re used to indicat the two ends of the queve. For the insertion ofthe next element, the pointer REAR will be the consultant and for deletion the pointer FRONT will be the consultant. (= TT) I Frnt Few Figure $3. Aray rpresentaon of a queve. ‘Three states of a queue with this representation ae given below: Queue is empty REAR = 0 (andlor) Queue is full (when full by compact) Queue contains elements > 1 j FRONT < REAR i Number of elements = REAR - FRONT + 1 4 "Now let us define the operation ENQUEUE to insert an element into & queue Algorithm Enqueue “Input: An element ITEM that has to be inserted, Output: The ITEM is atthe REAR of the queue. Data structure: Q is the aay representation of a queue stractue; two pointers FRONT and REAR of the queue Q are known, Queues _157 Sess If REAR = N) then 1 Queue is fll Print “Queue is full” 1 Queve is empey “Inset the item into the queue at REAR The deletion operation DEQUEUE can be defined as given below. Algorithm Dequene Input: A queue with elements, FRONT and REAR are the two pointers of the queue Q. Ouiput: The deleted element is stored in ITEM, Data structures: Q is the aray representation af @ queue structure Steps 1. If FRONT = 0) then 2 Print “Queue is empty” 3. 4 8 (FRONT) 1 Get the element 6 I @RONT = REAR) ‘1 When the queue contains single element 1 REAR = 0 1 The queve becomes empty 8 FRONT = 0 9. Else 0 FRONT = FRONT + 1 UL Enalt 12, Enalt 1B. Stop Let ws trac the above two sgortims with a gucue of size ~ 10, Suppose the caren state of tbe queue is FRONT = 8, REAR = 9, Ter operations ae requested a under 1. DEQUEUE 2. ENQUEUE 3. ENQUEUE : 4, DEQUEUE 5. DEQUEUE 6, DEQUEUE 7. ENQUEUE 8, ENQUEUE 9, DEQUEUE 10, DEQUEUE Figure 54 presents the status of the queue when these operations are cartied out.158 Casi Data Stractres Queues 159 ‘Queue ais osrent state “There is one potential problem with this representation. From Figure 54, we can see tha 123 4 5 6 7 8 8 0 wih tus vepreentaton, a queue may note ull ila request for insertion operation may be dened por example, on request (3) (in Figure 5) 8 rooms are avllable but insertion i no posible a he insertion pone reaches heen f the que. Tis is simply wats of He eae, This typeof representation canbe reccmmended for an application whee the queue is emptied at cerain intervals. | Tit [sosinmetaa ‘2 Request: ENQUEVE FR = lgoritim Enqueue may fail eventhough kere is memory space avallable. One way 10 rl I a0 oa rei ont be sign Engen snd Deuce, Two soos egeted opie below 8. Requat: ENOUELE ‘ | Suggestion 1; Rewaiting the algorithm, Engueve ‘henever the REAR pointer els to te end ofthe queue Figure 5.) est whether the Tnessage Queve sb + alter FRONT is at loeation 1 oF ao; if ao, shift all the elements so that they are wrapped. 4, Request; DEQUEUE, FOR ‘om the beginning ‘and thus make room for + new item. ; Silom» fog De sae : su | se om rh Bef ma iz atl hs | . Hi Fag OUELE igure 85. Shing elements won roaches 1 be end at l Liter the end of each deletion ll the-elements atthe trail ate sifted once towards the front tt ivarags Gos Sey [Rae te deaf to Hx the FRONT pointer alway at 1. ‘The queve which fellows seh +. Faueck; ENQUEUE eae is termed a dynamic queue. Rewie operations ENQUEUE and DEQUEUE for @ + 7 ‘yma queue. mS 532 Representation of a Queve using ¢ Linked List ferent: ENON ‘One more imitation of «queue, other than the nadequate service of insertion represented with 22 “ELI I crate riidness of is eng. In sever. applications, the length of the queue cans be pro. =a Mrafcaed before and it varies sbrply. 7 overme this problem, another prefenble FoR rcneation of queue i wth a inked Uist Here, we select a double inked Uist whic allows os 9 Reuse: OEQUEUE trove bah ays, Figure 5 6 shows the Goole inked Uist epresentation of a quee, The pointers T T TI FRONT and REAR. poiot the fist node and the ast node inthe lis — Tt Header Front ow FA . 10, Request: DEQUEVE i Pitt EES oh 1 c Figure 86 A double inked bt representation of a queue Figure 54 Operations on a queve. : ae160 _GassicDato Sires _ ‘Two states of the queue, either empty or containing some elements, can be judged by the following tests: Queue is empty FRONT = REAR = HEADER HEADER-»RLINK = NULL Queue contains at least one element HEADER-RLINK # NULL ‘The insertion and deletion operations are straightforward and the same as in the algorithm InseriEnd_DL (Gor Engueue) and algorithm DeleteFront_DL (for Dequeue); these two algorithms are already defined in Section 3.4 of Chapter 3. [ Assignment 5.2 july single linked ist“ 54 VARIOUS QUEUE STRUCTURES So far we have discussed two different ueve structures, that is, either using an array or using a Tink list (and a variation of a queue structure using an array as an assignment), Other than these, there are some more known queve structures. This section discusses them, 54.1 Cirenlar Queue [As pointed atthe end of Section 53.1, fora queue represented using an array when the REAR pointer reaches the end, insertion will be denied even if room i availabe at the font. One way fo avoid this is to use a circular aay. Physically, a cicular aay is the same as an ordinary aay, say A[I .. N), but logically it implies that A(I] comes after ALN] of after AINI, AI] appears, Figure 5.7 shows logical and physical views of a cireular array. (2) ret queve oi Figure 5:7. Logical and physical views of a creular queue. (2) ves sy pyc) _ ewes 161 ‘The principle underlying the representation of a circular aray is as stated below: Both pointers will move in a clockwise direction. Ths is controlled by the oo operation; for example, if the current pointer is ati then shift 10 the next location will be i Moo LENGTH + I, 1 << LENGTH (where LENGTH is the queue length). Thus, if = LENGTH (that is atthe end), then the next postin forthe pointer is 1 ‘With this principle the two states ofthe queve regarding, Le. empty or ful, willbe decided 28 follows: Cireular queue is empty FRONT REAR = 0 lar quene is ful (REAR woo LENGTH) + 1 ‘The following two algorithms describe the insertion and deletion operations ona circular queue. Algorithm Engueue_CQ Input: An element ITEM to be inserted into the circular queve. Oxaput: Circular queve with the ITEM a: FRONT, ifthe queue is not fll. Data structures: CQ be the array to represent the circular queue. Two pointers FRONT and REAR ate known, ‘Steps: 1. IE(FRONT = 0) then JF When the queue is empty 2. FRONT=1 3. REAR=1 4. CQ(FRONT) = ITEM 5. Else 1 Queae is not empty 6. next = (REAR woo LENGTH) +1 7. If (oext # FRONT) then INF the queue is not fll 8 REAR = next 8 COMREAR 10. Ee n Print “Queue is full” 2 Endl 13. Endl [6 Step Algorithm Dequeue_CQ Input: & queve CQ with elements. Two pointers FRONT and REAR aze known, Ouiput: The deleted element is ITEM if the queue is not empty. ata structures: CQ is the array representation of circular queue.162 Close Date smoetres we SSS ae 1, IE(FRONT = 0) then 2. Print "Queve is empty” 3. Exit 4. Else 5, ITEM = CQ(FRONT) 6 If (FRONT = REAR) then 1 1f the queue contains a single element 1 8. REAR = 0 9. Ese 0. FRONT = (FRONT so LENGTH) + 1 1. Endl . 12. Endit 13. Stop In order to trace these two algrithms, let us consider a circular queue of LENGTH “The following operations are requested. Different states of the queve while processing these requests are illustrated in Figure 53. 1 ENCQUELE 2 ENCQUEEE ©) 3. ENCQUEUE (C) 4, ENCQUEUE (D) 5: Dengue ¢ ENCQUELE 1 becoueve £ ReMuEtE 3 DeCUUEUE 1. bECuUEtE 1 DECREE "2 becouse kytetnroy tHE | [esa | tt et [fe ig fT T nga ey flelele ( Al t : t Figure 6.8 Continued (ey Request: ENOVEVE) ele{ele Queues 163 ot ft RF (@) Request: ENQUEVE () ele{e[o| > tT af (ryreqnt beCaUEUE (1) Regt OEOUELE ieee _ TT 7 TT ron tes (12) Request: BECOUEVE tt FR TT [bee Figure 58 Tracing inseton and deeton operations on a cicular queue Assignment 5.3 the following two algorithms. are proposed for a circular queue, ‘Algorithm 1 Enquevel_CQ lps: “LS We (REAR + 1) moo\LENGTH = FROND then 2 Print “Queue is fll” 3 Exit 4. Be 5. CQIREAR] = ITEM 6° REAR = (REAR + 1) moo LENGTHQueues 165 164 clase Data Stratures 3 Tre = COMRONT] Steps: 6, FRONT = (FRONT + 1) woo LENGTH 1. EG@RONT = 1) then IV FRONT sat exteme left 7. Balt. pia 2. ead = LENGTH ene i 3 eke 11, FRONT isa exteme right or he dou is empty 4. (FRONT ~ LENGTH) or GRONT = 0) then (@) Desite the queve that fis with these algorithms oc id cereal (0) De they algoins tlie propery th whole avalble nemo? If your & me angyee i NO, ten, devise he necessary ndificaton S tha this defies 7 eal = FRONT —1 11 FRONT ia an itrmeit poson overcome? : & endif a 9. abead = REAR) then 10. Print Deg is al 542 Deque . Mo Bxt oth fh own a deque ay b ed ‘deck’. Unlike a a othe variation ofthe queue is known a deque (may be pronoun ikea ques, ae ee pre in dequ, both insertion and deletion operations canbe made at eter end of the suc, i eed eae ‘Actual, he term dequ has orginnted fom double ended que, Sich astute is shown is nom in Figure 59, 16. Boat 1. Sop owt - eee ‘Algorithm Pop_DQ boson > + ban ‘This algorithm is the same asthe algoritim Degueue_CO */ besten <_— | +—reoton Algorithm Inject Figure £9 A doqu suc. ‘This alot i he same as he algritim Exqueue CQ */ Algoitum Eject_DQ It is clear from the deque structure that itis a general representation of both stack and ‘queue. In other words, a deque can be used as a stick as well b a queue. Thete are various ways of representing a deque on the computer. One simpler way t0 represent itis by using a double linked list. Another popular representation is using a circular aay (as used in a circular queue) ‘The following four operations are possible on a deque which consists ofa list of items: 1. Push DQUTEM): To insert ITEM at the FRONT end of a deque. 2, Pop_DQ(): To remove the FRONT item from a deque 3, InjectTTEM): To insert ITEM at the REAR end of a doque. 4. Bject(): To remove the REAR ITEM from a deque. ‘These operations are described for @ deque based on a circular array of length LENGTH. Let the aray be DQ{I .. LENGTH} Algorithm Push DQ Input: ITEM to be inserted at the FRONT. ‘Ouput: Deque with a newly inserted element ITEM if it is not full already. Data structures: DQ being the cicular aay representation of a deque, Input: A deque with elements init. Output: The item is deleted from the REAR end Data structures: DQ being the circular array representation of deque If (FRONT = 0) then Print "Degue is emery" 14 The deque contains single element 1 Deque becomes empty 1 REAR js at extreme let 1 REAR is at extreme right |166 Cisse Data stutures REAR is at an intermediate postion ‘There are, however, two known variations of deque: 1. Inpotresrcted deque 2. Outputestricted deque. ‘These two types of variations are actually intermediate between a queve and a deque ‘Specifically, an input-estrcted deque is Geque which allows insertions atone end (say REAR tend) only, bat allows deletions at both ends. Similarly, an outpu-restrcted deque is a deque “here deletions take place at one end only Say FRONT end), bu allows insertions at both ends Figure 5.10 represents two such variations of deque a on = = —— ~ Insertion —> | —_— a ‘b) Oupatvesticied eave Figure 5:10. Types of equ. ues 167 543. Priority Queue 'A priority queue is another variation of queue structure. Here, each clement has been assigned 4 value, called the priority of the element, ane an element can be inserted or deleted not only at the ends but at any position on the queue. Figure 5.11 shows a priority queue rox ron i i lel fal [la Figure 5.11 View ofa pony quous. With this structure, an element X of prioity p, may be deleted before an element which is at FRONT. Similarly insertion of an elements based on is priority, that i, instead of adding it after the REAR it may be inserted at an inermediate postion dictated by its priority value [Note thet the name priority queue is a misnomer in the sense thatthe data structure is not queue as per the definition; a priority queve does not strictly follow the firs-in first-out (FIFO) Principle which is the basic principle of a queve. Nevertheless the name is now firmly associated with this particular datatype. However, thece ae various models of privity queue known in different applications. Let us considera particular model of priority queve. 1. An element of higher priority is processed before any element of lower priority 2. ‘Two elements with the same priority ae processed according o the order in which they were added to the queue. Here, process means two basic operations namely insertion or deletion. There are various ways of implementing the structure ofa priority qxeue. These are @ Using a simplefcireulararay (ii) Malt-queue implementation (Gi) Using a double linked list (iv) Using heap we. ‘We will now see what each of these implementations is. (Heap tee implementation of Priority queue will be discussed in Chapter 7 ofthis txt) Priority queue using an array With tis presentation, an aray canbe mained to hold the item and its priority vale. The clement willbe inserted at the REAR end as uswal. The deletion operation will then be Psfonned in either ofthe two following ways . (@) Staring from the FRONT pointer, averse the aray for an element of the highest priority, Delete this element from te queue. I this is othe font-most element, shift fltits tailing elements ater the debted element one stoke each to fill up te vacant poston (ee Figure 5.12)168 case Data Sra PPDPL Deion < "Sartore Figure §:12. Deleon operation in an aray representation of a prsty queve. ‘This implementation, however, is very inefficient as it involves searching the queue forthe highest priority element and shifting the tailing elements after the deletion. A better implementation is a follows: (b) Add the elements at the REAR end as earlier. Using a stable sorting algorithm’, sort the elements of the queue so thatthe highest priority element is at the FRONT end, When a deletion is required, delete it from the FRONT end only (see Figure 5.13) FRONT “ | ston er oe Figure 5.13 Another array implementation of a pronty queve. ‘The second implementation is comparatively better than the first one; ere the oly burden is to sort the elements, The algorithms of the above two implementations are lft as assignments to the reader, ‘Mutt-queue implementation ‘This implementation assumes N different priority values. For each prisity p, there are two pointers F and R, corresponding tothe FRONT and REAR pointers respectively. The elements between F and R, are all of equal priority value p. Figure 5.14 represents a view of such a structure Figure 6:14 Mul-quoue representation of a proniy queue. With this representation, an element with priority value p; will consult F; for deletion and A, for insertion. But this implementation is associated with a number of dificult: _ ueues 169 (@ Tt may lead to huge shifting in order to make room for an item to be inserted (i A large umber of pointers are involved when the range of priority values is large Tn addition to the above, there are 1wo ather techniques to represent a multiqueue, which are shown in Figures 5.1S(a) and 5.15(b) It is clear from Figure 5.15(a) that for each priority value a simple queue is to be ‘maintained. An element wil be added into a particular queue depending on its priority value “The priority queve as shown in Figure 5.15(b) is in some way better than the mult-queve with multiple queues. Here one can get rid of maintaining several pointers for FRONT and REAR in several queves. A multi-queue wih multiple queues has one advantage that one can have different queves of arbitrary length. In some applications, itis seen that the number of ‘occurrences of elements with some priority value is much larger than the other value, thus demanding a queue of larger size ' * Priory a, rk ate ; 7 eee ; : ara = Tt Fo ee cl Nx LENGTH (2) Mtge quae wih sgl queues Figure 5.15 Mult-quoue implementation with mutiple simple queues and mati. (t) Mate queue wih a mat Both the above representations are not economic from the memory utilization point of view; much of the memory space remains vacant Algorithms for insertion and deletion operations for multi-queve implementation are left as exercises for the student Linked list representation of a priority queue ‘This representation assumes the node struct as shown in Figure $.16, LLINK and RLINK are {wo usual link fields, DATA isto store the aca content and PRIORITY isto store the priovty ‘alueof the iter, We will consider FRONT and REAR as two pointers pointing the fist Ad last nodes in the queue, respectively. Here all the nodes are in sorted order according to the Priority values of the items in the nodes. Tie following is an instance ofa priority queue: “A sor algorihn is sable fhe relive posts of two identical items resin the same inthe unsorted 494 soe ist (for dels, see Chapter 1)170 classe Dota Structures Quewes 174 tun | para [priory] ALN PATE eT aoe PEERS PERSP De Figure 5.18 Linked lst representation of s pronty queue With this structure, to delete an item having priostyp, the list wil be searched starting fom ‘the node under pointer REAR and the frst occurring nade with PRIORITY = p willbe deleted. Similarly, to insert @ node containing an item with priority p, the search will begin from the ‘node under the pointer FRONT and the node will be inserted before a node found first with priority value p, of not found then before the node withthe next priority value. The following {wo algorithms Insert_PQ and Delete.PQ are used to implement the insertion and deletion ‘operations on a priority queue. Algoritha Insert_PQ Input: The ITEM and its procty P value of a node that is to be inserted. Ourput: A new node inserted. Dra tres: Linked Tis sca of priority ques; HEADER athe pot tothe ead. 1 Stat from he fist node 1 2 1 Avail a new node 3 1 Get initialized the node with TTEM 4. new-9PRIORITY = P 5. While (pteRLINK # NULL) and (pt PRIORITY < P) do 1! Search forthe position 6 ptr = plroRLINK 7. EndWhile 8. AP (pt-oRLINK = NULL) then 1 Ifthe ist is empty or the item is with the largest pron value pURLINK = new 10 The node is inserted as the lest node (Con) 14 15 16. 1. 18. 1. 20. 2 2. 2. I (pu-9PRIORITY 2 P) then’ 11 Fist occurence is found pel = ptr-p.LLINK, ‘Tose the nes node prRLINK = new 1 Before the node with priority > P rnew-ORLINK = per ptr oLLINK = new rnew-9LLINK = pt Endlt Endl FRONT = HEADER-DRLINK, Stop 1 Set the FRONT pointer Similarly, the algorithm for deletion can be described as follows: Algorithm Delete PQ Input: The priority P of the element whch has to be deleted Ouopur: The element that is being deleted Data structures: Linked list structure of priority queue; HEADER as the pointer to the beads. ‘Steps: If (REAR = NULL) thea Print "Queue is empry” pir = REAR While (pt-»PRIORITY > P) and (ptt * HEADER) do ptr = ptrsLLINK EndWhile If (pr = HEADER) or (pt¢)PRIORITY < P) Print *No item with prio’, P Exit Bise I (pt-prionity = P) then pel = ptroL LINK ped = pur oRLINK If (pu = REAR) REAR = ptr pirl-9RLINK = NULL Eke 1 Othe than Ist node pIr-9RLINK = pt Deleted ptLLINK = ple] Endl Endlf 1X6 the lst node tobe deleted (Coad)