6
STACKS AND QUEUES
In the earlier chapters we have seen the primitive data structures that are available in C. We have also looked through arrays and strings. The array data structure is implemented with storage structure as memory, while string data structure is implemented with arrays as their storage structures. There are many other simple but important data structures. These are simple because they can be implemented using arrays as their storage structures. Other implementations of these data structures are also possible. In this chapter, we have considered two such important data structures, stacks and queues.
6.1 INTRODUCTION TO STACK
Consider the problem of reading 50 integers and printing them in reverse order. This problem inherently requires to push the read numbers into an array one by one. Then the numbers are to be retrieved and displayed one by one from the last of the array in reverse order. This means the number read last is displayed first and the number read first is displayed last. This type of last-in-first-out or last-come-first-serve processing is inherent to a wide variety of applications. Consequently, an abstract data structure that incarnates this idea is of great importance. This last-in-first-out (LIFO) or last-come-first-serve (LCFS) data structure is called a stack data structure. For illustration, we consider a little serious problem. We know that binary representation of a data item in memory plays an important role while storing data. Specifically, a positive integer is stored in memory with its binary representation in base-two. So while storing a positive integer, the integer in decimal is to be converted to binary. A simple algorithm to convert from decimal to binary needs to divide the integer number by 2 repeatedly until the quotient becomes 0 (zero), and then the remainders generated at each step is taken in reverse order. For example, for the integer 46 in decimal, the binary equivalent is 101110. (see Fig. 6.1).
Fig. 6.1 Binary equivalent of integer 46
Fig. 6.2 A trace of Algorithm 6.1
This example clearly shows that to convert a decimal positive integer to its binary equivalent, the remainder (after dividing by 2) is to be taken on last-generate-first-take basis which is nothing but like a stack. Now we define a stack formally. A stack is a list or sequence of data items in which all insertions and deletions take place at one end, called the top of the stack. With this background we can now write an algorithm that converts a decimal positive integer to its binary equivalent and display it. One such algorithm is given below.
Algorithm 6.1: Decimal to binary conversion algorithm
/* Algorithm to convert a decimal positive integer to its equivalent binary form and display it* /
Step 1: Create a stack of remainders.
Step 2: While (Number is not zero) perform the following:
(i) Compute Remainder when Number is divided by 2.
(ii) Push Remainder on top of the stack of remainders.
(iii) Replace Number by the quotient of the division (Number/2).
Step 3: While (the stack of remainder is not empty) perform the following:
(i) Remove the remainder at stack top.
(ii) Display remainder.
A trace of the above algorithm is given in Fig. 6.2. The arrows in the figure indicate the stack top.
Operations on stack: The decimal to binary conversion algorithm given above suggests that we need to have four operations on stack which are the four basic operations that can be performed. These are given below.
(1) create: creates an empty stack.
(2) push: inserts an item onto the top of the stack.
(3) pop: removes the item from stack top.
(4) empty: determines whether a stack is empty.
Each of these operations is implemented by a C function. Consider that a stack of remainders stack is defined. Then we may have the following functions in C that can implement the above basic operations.
(i) create(&stack) /* Creates an empty stack called stack */
(ii) push(&stack, item) /* Pushes item into stack at the top */
(iii) pop(&stack) /* Returns the item at stack top */
(iv) empty(stack) /* Returns non-zero value if stack
is empty, otherwise returns zero */
If we assume that the above functions are available, the C code for Algorithm 6.1 may simply be written as
create(&stack);
while(number)
{
remainder = number %2 ;
push(&stack, remainder) ;
number/=2 ;
printf(“Equivalent binary representation is”);
while(!empty(stack))
{
remainder=pop(&stack);
(printf ("%d", remainder);
}
putchar ('
'),
6.2 ARRAY IMPLEMENTATION OF STACKS
As we have already seen, the primary step to implement a data structure is to choose a proper storage structure. In our case since a stack is nothing but a sequence of data elements, to implement a stack storage structure we can safely choose an array as its storage structure. Each element of the stack will occupy one array element. Let us now try to visualize how a stack looks after storing the remainders of our decimal to binary conversion algorithm after four steps (say) for the integer number 46. We consider our stack to be array stack[ ] with its top at position zero (0). After pushing four (4) remainders the stack will look like as in Fig. 6.3.
Fig. 6.3 Stack configuration after pushing four remainders
The next remainder that will be generated by our algorithm is 0 for the integer number 46. To push this remainder to stack top we must first shift the values between stack [0] and stack [3] to stack [1] and stack [4] respectively, and then put the remainder 0 to stack [0]. Clearly, as the stack grows, this shifting becomes a real overhead. On the other hand, when we try to pop an element from the stack top we must shift up the stack elements one step each time. This is required so that we can pop the next element from the stack top. This also creates an overhead of shifting up the stack elements while popping. So now the question is how to get rid of this overhead? One trivial solution is to use a variable top to keep track of the array index where the top element of the stack is stored. In our case, this implementation works like the following. As and when a remainder is pushed to the stack, first the variable top is increased by 1 and the remainder is stored in stack [top]. Fig. 6.4(a) shows the stack after storing the first four remainders to the stack.
Fig. 6.4 Revised stack
When the next remainder 0 is pushed, the variable top is increased to 4 from 3 and then the remainder is stored in stack [4]. This is shown in Fig. 6.4(b). So in this implementation the storage structure for the stack is an array that holds the stack elements and there is a variable top that holds an array index indicating the stack top element. This structure tells us to choose the following declarations and definitions in C.
#define STACKLIMIT ....../* Maximum size of stack */
typedef int elemtype; */ Type of item in the stack */
struct stacktype {
int top; /* Stack top index */
elemtype item[STACKLIMIT];
};
struct stacktype stack;
Let us revisit our above implementation with the idea that we want to store either an integer or a floating-point number or a string. In such a situation the typedef given above will not be sufficient, because a stack element may be of either int or float or a pointer to character string type. In this case we need to take the help of union feature of C also. Moreover, we must keep the information that as to what type of element is stored at a particular array index of the stack. This discussion suggests to revise our above declaration and definitions as in the following.
#define STACKLIMIT ...... /* Maximum size of stack */ #define INT 1 #define FLOAT 2 #define CHAR 3 struct stackitem { int itemtype; union { int i; float f; char *pc; } element; }; struct stacktype { int top; struct stackitem item[STACKLIMIT]; }; struct stacktype stack;
With this background we can now write the C code to implement the four basic stack operations easily. Here we should notice the fact that when a stack is just created it is empty and at that time the value of the variable top should be –l(minus one). This is because when we push an element to the stack we must increase this top and then store the element to stack.
To create an empty stack we must set the top member of the variable stack to -1. In fact, this is the only thing that we need to do within the function. So if a pointer to the stack ptrstk is passed as the argument to function create, then the only statement within the function should be ptrstk-> top = -1;
The function empty must check whether the top member of the stack which is to be passed as argument to the function is -1. If that is so, return 1, otherwise return 0. Hence, the statement within empty is of the form
return ((stack.top == -1)?1:0) ;
The push function must receive two arguments. One of them is a pointer to the stack within which an element is to be pushed and the other one is the element itself which is to be pushed. Within the function we must check whether the stack is already full. In such a situation an error message must be given. Otherwise, we push the element to the stack top. We achieve this by first increasing the top member of the stack by 1, and then copying the element to the top of the stack. The C code to do so is of the form
ptrstk -> top++;
ptrstack -> item[ptrstack->top] = element;
The pop function is just the opposite to push function. It also requires two arguments, one of which is a pointer to the stack from which an element is to be popped. The second argument should again be a pointer to element (say ptrelement) which will actually hold the popped element from the stack. In this case first the element is popped and then the top member of the stack is to be decreased by 1. The function must check whether the stack is empty before popping because in such a case it is an error. The program code will look like
if (empty(stack))
printf ("Attempt to pop from an empty stack
");
else {
*ptrelement = ptrstack->item[ptrstack->top];
ptrstack -> top--;
}
A complete program for decimal to binary conversion using these stack functions is given in Example 6.1.
Example 6.1
/* C program listing for converting a decimal positive integer to its equivalent binary form */
#include <Stdio.h>
#define STACKLIMIT 100
#define INT 1
#define FLOAT 2
#define CHAR 3
struct stackitem {
int itemtype;
union {
int i;
float f;
char *pc;
} element;
};
struct stacktype {
int top;
struct stackitem item[STACKLIMIT];
};
main( )
int number, c, dum;
struct stackitem info;
struct stacktype stack;
do {
printf (“Enter the positive integer to convert:”);
scanf (“%d”, &number)
create (&stack);
while (number)
{
info.itemtype = INT ;
info.element.i = number % 2
push ( &stack, info ) ;
number >> = 1 ;
}
printf (“The equivalent binary representation is : ” );
while ( !empty (&stack))
{
pop ( &stack, &info ) ;
printf (“%d”, info.element . i ) ;
}
printf (“
Once more (Y/N) ?”)
c =getchar ( ) ;
if ( ( c = getchar ( ) ) == 'Y' | | c == 'y' )
dum = getchar( ) ;
} while ( tolower(c) == 'y' ) ;
}
create ( struct stacktype *ptrstk )
{
ptrstk -> top = - 1;
return;
}
empty (struct stacktype *ptrstk )
{
return (( ptrstk ->top == -1) ? 1 : 0 );
}
pop(struct stacktype *ptrstk, struct stackitem *ptrinfo)
{
if (empty (ptrstk ))
{
printf (“Convert : illegal attempt to pop from empty stack
”) ;
exit (1);
}
*ptrinfo ptrstk->item[(ptrstk - >top)--);
return ;
}
push (struct stacktype *ptrstk, struct stackitem x)
{
if (ptrstk -> top == STACKLIMIT-1)
{
printf (“convert : illegal attempt.to push
to full stack
w)
exit (1) ;
}
ptrstk -> item[++(ptrstk -> top) ] = x ;
return ;
}
By definition, a list does not have any upper limit on the number of members of the list. Hence a stack should also have no upper limit on the number of members of the stack. So as an abstract data structure there should not be any condition as to whether a stack is full. But as an array is of fixed size and here we chose this as the storage structure of the stack, we have to impose an upper limit on the number of members in the stack. Thus it is clear that this implementation of stack data structure is not completely a faithful representation. Later in the chapter 9 we will see an alternative representation of stack using linked list that puts no such upper limit and is more flexible.
6.3 APPLICATION OF STACK
In this section we look through a major application of stack which illustrates various types of stacks and operations on them. Ordinarily a programming language allows to write arithmetic expressions of the form
x*y+z
The above expression is written in infix notation in the sense that the operators (binary) are placed in between the operands. But there are other ways of writing an expression. They are prefix and postfix notation expressions. In prefix the operator is placed before the operands and in postfix the operator is placed after the operands.
For example, the infix expression
x*y
may be written in other forms as follows:
* x y (prefix)
x y * (postfix)
To evaluate an infix expression, many compilers convert this infix expression into its equivalent postfix form first and then evaluate it, which generates the code for evaluating the transformed postfix expression. If we examine an infix expression little carefully we see that parentheses must be used to indicate the priorities of the operators involved in the expression. For example, in the infix expression 4 * (5 – 3 ), we imposed a higher priority of minus (−) operator over multiplication (*) operator by introducing parentheses. If we remove the parentheses the expression looks like 4 * 5-3 and is a completely different expression.
It has been found by the Polish logician Jan Lukasiewicz around 1950s that such parentheses are not necessary to set the priorities of operators in postfix notation. This notation is also called as Reverse Polish Notation (RPN). Because of this fact, evaluation of an expression in RPN is, in general, much easier than evaluating an infix expression in a mechanical way. Lastly, the conversion from an infix notation to RPN is straightforward. To illustrate this, let us choose the infix expression
4*(5 – 3)
The infix expression is scanned in left-to-right order. When an operand is found, it is sent to the output. Initially, for the above input 4 is encountered and is sent to output immediately. Next, the * operator is found. At this point, another operand is expected after * on which it must be applied. So it must be stored and hence * is pushed on to a stack of operators. Note that before pushing this operator the stack was empty. In general, when an operator is encountered it must be checked against the top stack element. The operator is pushed to the stack if either the stack is empty or if the operator is having a higher priority than the stack's top element. In our case * is pushed to the stack. Next an open parenthesis'(‘ is encountered and is pushed to the stack. Then the operator 5 is found and it is sent to the output. At this stage the output and stack look like the following.
Now the operator'-' is encountered. It is pushed to the stack since the stack top symbol '('is assumed to have lower priority than any other operator. The operand 3 is found next and it is sent to output directly. Now the output and stack take the following form.
Finally, the right parenthesis ')' is encountered. When a')' is encountered, the symbols are popped from the stack and sent to output until a'(' is found in stack top. This'(' is popped from the stack but not sent to output. After doing this the output and stack become
There is no other symbol left in the input now. At this stage, the operators are popped from stack and sent to output until the stack is empty. Hence the output will look like
and the stack is empty. The output now shows the RPN expression for the given infix expression. Notice that though there is a set of parentheses in the infix expression, it is not present in our RPN expression. An algorithm is presented to transform an infix notation arithmetic expression to its equivalent RPN expression below, in its general form. This algorithm may always be extended to include logical infix expression conversion by incorporating the logical operators.
Algorithm 6.2: Infix to RPN conversion algorithm
/* Algorithm to transform an arithmetic infix notation expres
sion to RPN expression */
Step 1: Create an empty stack of operators
Step 2: While not (any error) and not (end of infix expression) do
the following:
Get next token in infix expression;
/* A token may be a constant, variable, '(',')' or an
arithmetic operator.
if (token is '(' )
Push it onto stack
else if (token is ')')
pop stack top element and send it to output
until a '(' is encountered. Pop this '(' but
do not send it to output.
(If no '(' is found and stack becomes empty
it is an error).
else if (token is an operand)
send it to output
else /* it is an operator */
if (stack is empty or token has higher priority
than the top stack element)
push token onto stack
else
repeat
pop and output top stack element;
until (the top stack element is of lower
priority than the token)
push token onto stack;
/* operators have higher priority than a '('
in the stack */
Step 3: if (end of infix expression)
pop stack elements and send to output until the
stack is empty.
To illustrate the above algorithm let us choose the infix expression
8 + (((7–5) * (9–4) + 6)/4)
Fig. 6.5 shows the execution of Algorithm 6.2 on the above infix expression. Current input position is indicated by an upward arrow (↑) in the figure.
Fig. 6.5 Execution of Algorithm 6.2
The Figure 6.5 shows that for the infix expression the RPN expression takes the form
875-94-*6+4 / +
Let us take this RPN expression to illustrate the process of evaluating an RPN expression.
To do this, the RPN expression is scanned from left to right. When an operator is found, the operator and the last two operands are removed from the expression and joined with the operator to yeild a new sub-expression. This sub-expression is then replaced in RPN expression at the point from which the operands and the operator are removed. Scanning is then resumed. Finally there will be only one operand remaining in RPN and there will be no operators. This operand's value is the value of the expression. The process is executed below with the above expression. The left to right scan is indicated by underlining.
After evaluating the RPN expression we reached at the value 12, which is the value of the expression. This method suggests that in the left to right scan the operands must be stored until an operator is encountered. At this situation the last two operands must be retrieved to operate on the operator. This means that the order in which the operands are retrieved is in last-in-first-out order and hence a stack should be used to store the operands. Thus each time an operand is found it should be pushed to a stack. When an operator is found, two operands are popped from the stack, the operator is applied on these operands and the resulting value is pushed back onto the stack. This process is continued and finally there will be one element in the stack which will give the value of the expression.
In the following a formal algorithm is presented that evaluates an RPN expression.
Algorithm 6.3: Evaluation of an RPN expression
/* Algorithm to evaluate RPN expression*/ Step 1: Create an empty stack /* stack elements must be of type of operands */ Step 2: Repeat the following i. Get next token from RPN expression; /* Token may be a constant, variable or arithmetic expression */ ii. If (token is an operand) push it onto stack else do the following: a. pop two elemetns from stack; (If not available there is an error due to malformed RPN expression) b. apply the operator on these two elements; c. push the resulting value onto stack; until (end of RPN expression); Step 3: Pop the only value on stack top and send it to output as the value of the expression. (In fact, there will be only one value in the stack.)
An execution of the above algorithm is given in Fig. 6.6 for illustration purpose. Here also an upward arrow (↑) is used to indicate the current token in RPN expression. The same RPN expression is considered for a good understanding of the algorithm.
Fig. 6.6 Execution of Algorithm 6.3
Example 6.2
/* C listing to convert an infix arithmetic expression
to its equivalent RPN exxpression and evaluate it . */
#include <stdio.h>
#include <string.h>
#define STACKLIMIT 100
#define SIZE 100
#define FALSE 0
#define TRUE 1
#define INT 1
#define FLOAT 2
#define CHAR 3
struct stackitem {
int itemtype;
union {
int i;
float f;
char c;
} element ;
};
struct stacktype {
int top ;
struct stackitem item [STACKLIMIT];
};
main( )
{
char rpn[SIZE], infix[SIZE];
int value;
printf (“Enter the infix expression:”);
gets(infix); /* read infix expression*/
rpn [ 0 J = ' 0 ';
infix_to_rpn(infix, rpn );
printf ("
The RPN expression is %s
', rpn );
value= evaluate(rpn);
printf ("
The expression value is= %d
", value);
return;
}
create (struct stacktype *ptrstk)
{
ptrstk->top = -1 ;
return;
}
empty (struct stacktype s)
{
return ( (s. top == -1 )? 1 : 0);
}
pop(struct stacktype *ptrstk, struct stackitem *ptrinfo)
{
if (empty ( *ptrstk))
{
printf(“convert : illegal attempt to pop from empty stack
”);
exit(1);
}
*ptrinfo = ptrstk->item((ptrstk-> top)--] ;
return;
}
push (struct stacktype *ptrstk, struct stackitem x)
{
if (ptrstk->top == STACKLIMIT - 1 )
{
printf ( "convert : illegal attempt to push to full stack
");
exit(1);
}
ptrstk->item(++(ptrstk->top)] = x;
return;
}
priority (char operartor)
{
int p;
switch (operator )
{
case '(' p 0; break ;
case '+'
case '-' p 1; break ;
case '*'
case '/' p 2 ; break ;
}
return p;
}
infix_to_rpn (char infix[], char rpn[])
{
static int index=O ;
struct stacktype opstack;
struct stackitem info ;
char tokenop, tokenstr[10];
int token, errflag, overflag ;
errflag = overflag = FALSE;
create(&opstack) ;
token gettoken(infix, &index, &tokenop, tokenstr);
while !errflag && token != - 1 ) {
switch ( token )
{
case 1: strcat(rpn, tokenstr);
break;
case 2: info. itemtype = CHAR;
info . element . c = tokenop;
push(&opstack, info);
break;
case 3: overflag = FALSE;
do {
if (empty(opstack)) {
printf ("Parentheses mismatch in infix
expression
");
errflag = TRUE;
exit (1);
}
pop(&opstack, &info) ;
if ( info . element . c != '(' )
tokenstr[O] info . element.c ;
tokenstr[l] = ' ';
tokenstr[2] = ' ';
strcat (rpn, tokenstr);
} else
overflag = TRUE ;
} while ( !overflag && !errflag );
break ;
case 4: overflag = FALSE;
while { !empty(opstack) && !overflag) {
pop(&opstack, &info) ;
if (priority (tokenop) <=
priority (info.element.c))
tokenstr [0]= info . element.c;
tokenstr [1]= ' ';
tokenstr [2]= 1 ';
strcat (rpnl tokenstr);
} else {
push (&opstack, info);
overflag = TRUE ;
}
}
info. itemtype = CHAR;
info. element. c = tokenop;
push (&opstack, info);
break;
}
token= gettoken (infix, &index, &tokenop, tokenstr) ;
}
while (!empty (opstack) ) {
pop (&opstack ~ &info);
tokenstr[O] = info .element . c ;
tokenstr[l] = ' ';
tokenstr [2] = ' ';
strcat (rpn, tokenstr );
}
return;
}
evaluate (char rpn[ ] )
{
static int index = 0;
struct stacktype opstack;
struct stackitem info ;
char tokenop, tokenstr(lO);
int token, vall, val2, errflag FALSE;
create (&opstack);
token gettoken (rpn, &index, &tokenop,tokenstr);
while ( token ! = -1 ) {
if (token == 1) {
info.itemtype =INT;
info.element . i = atoi(tokenstr);
push ( &opstack, info) ;
} else { I* token is an operator *I
if ( !empty(opstack) ) {
pop(&opstack, &info);
val2 = info.element.i;
} else
err flag =TRUE ;
if (!empty(opstack)) {
pop (&opstack, &info ) ;
vall = info.element.i;
} else
errflag = TRUE;
if (errflag) {
printf (“Error due to malformed RPN
expression
”);
}
switch (tokenop)
{
case , +, : vall += val2; break;
case , -, : vall -= val2; break;
case , *, : vall *= val2; break;
case , /, : vall /= val2; break;
}
info.itemtype = INT;
info.element.i =vall;
push (&ops tack, info);
}
token gettoken(rpn, &index, &tokenop, tokenstr);
}
if (opstack.top != 0)
{ /* if stack does not contain one element only */
printf (“Error in evaluation or malformed RPN
expression
”);
exit (1);
}
pop (&opstack, &info);
return (info.element.i);
}
gettoken (chars[], int *ptri, char *ptrop, char str[])
{
int i, j, token;
char c ;
for (i=*ptri; (c=s[i])== ' ' || c == '
'),
i++) i
switch (c)
{
case ' (' : ')' token = 2;
*ptrop = c ;
*ptri = ++i;
break;
case ' )' : token =3;
*ptrop = c;
*ptri = ++i;
break;
case ' +' :
case ' -' :
case ' *' :
case ' /' : token = 4;
*ptrop = c;
*ptri = ++i;
break;
default : if (c >= '0' && c <= '9' ) {
for(j=O; (s[i] >= '0' && s[i] <= '9') ;
j++)
{ Str [j++] = ' ';
Str [j] = ' 0';
*ptri = i;
token = 1 ;
} else
token = -1 ;
break;
}
return token;
}
A complete C program that receives an infix expression and then evaluates it after converting the expression into RPN expression is given in Example 6.2. The main program calls two functions. The first function is infix-to-RPN which translates an infix expression to its equivalent RPN expression using Algorithm 6.2 mentioned above. The function evaluate takes the generated RPN expression and evaluates it using Algorithm 6.3. The infix expression is assumed to have its operands as integer only. The program may always be extended for logical expressions also.
6.4 INTRODUCTION TO QUEUE
A queue is basically a waiting line, for example, a line of customers in front of a counter in a bank. Notice that a customer joins in a line at one end of the line and the customer in front of the line gets the service first. After getting the service the customer in front of the line leaves the line (or bank). This indicates that a customer gets service in first-come-first-served (FCFS) (or first-in-first-out (FIFO) ) basis. This is unlike the LIFO structure of stack. So if we think a waiting line of customers as an array of customers, then one end of that array must be used for inserting (joining) a customer to the line called rear or tail of the queue and the other end must be the point from which a customer gets the service called the front or head of the queue.
As a data structure, a queue is an ordered list of elements from which an element may be removed at one end, called front of the queue, and into which an element may be inserted at the other end, called the rear of the queue.
Pictorially, a queue containing three integer values 70, 90, and 50 may look like as in Fig. 6.7(a). 70 is the element in front of the queue. Now the rear of the queue is just the next cell to 50 where a new integer may be inserted. Fig. 6.6(b) shows the queue after removing two elements from the queue. Since an element is removed always from the front, the integers 70 and 90 are removed and the integer 50 is now in front of the queue. Fig. 6.6(c) shows the status of the queue after inserting two new integers 60 and 80 into the queue.
Fig. 6.7 The status of queue at various stages
6.5 QUEUE IMPLEMENTATION USING ARRAYS
The above discussion suggests that we can safely use an array to implement a queue. In continuation to our earlier discussion let us choose the array size is defined by a constant MAX and consider the value of MAX as 6. This indicates that at any point of time there cannot be more than six elements in our queue. Let us also consider that we have two variables, front and rear, to indicate the front and rear of the queue. In our previous queue if we now insert a new integer 85 the queue will take the form as in Fig. 6.8. At this point rear holds the value 6 and only four integers are there in the queue. Now if we try to insert another new integer it will not be possible to do so unless we shift the queue elements to the left side. Clearly this shifting is a slow process. Obviously, it would be a good solution to this problem if we can bring the rear to the beginning of the array instead of setting its value to MAX in this situation. So we must treat our array as a circular one as in Fig. 6.9.
Fig. 6.8 Status of the queue after inserting 85
Fig. 6.9 Circular view of the queue in Fig. 6.8
Let us now look at the whole process from the beginning, keeping in mind that our array is circular. The initial queue is shown in Fig. 6.10(a), where the front and rear have the same value 0. After inserting 70, 90, and 50 the queue looks like in Fig. 6.10(b). Here front holds the index 0 and rear holds the index 3. After removing two elements from the queue (from front of the queue) the queue takes the form of Fig. 6.10(c). Now if we insert five more integers to the rear of the queue, say the values 60, 80, 85, 95, 99, then the queue takes the form of Fig. 6.10(d). In the last situation it can easily be noticed that front and rear hold the same value 2. This again creates a difficulty that with this implementation we cannot differentiate the status of empty queue and full queue, because in both the situations the front equates to rear. For clarification, if all the six integers are removed from the front of the queue it will take the form given in Fig. 6.10(e).
Fig. 6.10 Queue status at different stages
Note that when front and rear hold the value (MAX–1) the very next value that front and rear get is 0. This means that after removing an element, the front is changed using the assignment
front = (front +1) % MAX;
Similarly, rear changes after inserting an element to the queue by the assignment
rear = (rear +1) % MAX;
To avoid the anomaly between an empty queue and a full queue, we can introduce a restriction that a queue implemented using an array of size MAX must not have more than (MAX–1) elements. Then the status of a queue is full when the condition
((rear + 1) % MAX == front)
is fulfilled. Obviously, the status of the queue is empty if
(rear == front)
is fulfilled.
Summing up the discussions above, to implement a queue we may use the storage struc-ture as a structure in C containing a circular array that can store the queue elements, front and rear, to hold the position of the starting element and the position following the last element of the queue, respectively.
#define MAX.............. /*Maximum size of the queue array*/ typedef .......... Q_type; /* the type of element stired in queue*/ struct Q_type int front, rear; struct Q_type element[MAX]; }; struct Q_type queue;
A C program that implements all basic queue operations is given in Example 6.3. The program is a multiplication skill test program that gives you some multiplication problems. Wrongly answered problems are queued and asked again at the end of the session.
Example 6.3
/* C listing to show all basic queue operations. This is a
multiplication skill test program */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 25
#define NUMBER 100
struct problem {
int nl;
int n2;
};
struct q_type {
int front;
int rear;
struct problem element[MAX];
};
main ( )
{
struct q_type wrong_queue;
/* queue of problems answered wrong */
struct problem question;
int num, wrong=0, count=0, wrong1=0, score=0;
printf (“This will test your multiplication skill
”);
printf (“For a multiplication if you can answer correctly in the first chance
”);
printf (“you score 2 points. You will be given a second chance. For a correct
”);
printf (“answer in this chance you score 1 point.
”);
printf (“
”);
printf (“Enter number of questions(1 to 24) : ”);
scanf (“%d”, &num);
printf (“
Now the problems follows:
”);
createQ (&wrong_queue);
randomize( );
do{
++count;
question.nl=rand( )%NUMBER;
question.n2=rand( )%NUMBER;
if (!query(question,1))
{
wrong++;
addQ(&wrong_queue, question);
}
else
score +=2;
} while (count < num);
if (wrong)
{
printf (“You now get one more chance to answer the problems/n”);
printf (“which were incorrect in the first chance
”);
count=0;
do{
++count;
removeQ (&wrong_queue, &question);
if(!query(question, 2))
wrong1++;
else
score++;
} while (count < wrong);
}
printf(“You made %d correct out of %d
”, num-wrong1, num);
printf (“You scored %d points.
”, score);
exit(0);
}
createQ (struct q_type *ptrq)
{
ptrq->front = ptrq->rear = 0;
return;
}
emptyQ(struct q_type queue)
{
return(queue.front==queue.rear);
}
addQ(struct q_type *ptrq, struct problem item)
{
int gen_rear;
gen_rear = (ptrq->rear + 1)%MAX;
if (gen_rear == ptrq->front)
{
printf (“QUEUE : Attempt to insert in a full queue
”);
exit(1);
} else {
ptrq->element[ptrq->rear]=item;
ptrq->rear=gen_rear;
}
return;
}
removeQ(struct q_type *ptrq; struct problem *ptr_item)
{
if (emptyQ(*ptrq))
{
printf (“QUEUE : Attempt to delete from an empty queue
”);
exit(1);
} else {
*ptr_item = ptrq->element[ptrq->front];
ptrq->front = (ptrq->front+1)%MAX;
}
return;
}
query(struct problem prob, int n)
{
int response,answer;
printf(“%d * %d = ”, prob.nl, prob.n2);
scanf (“%d”, &response);
answer = prob.nl * prob. n2;
if(answer==response)
{
if(n==l)
printf (“Correct…in first chance
”);
else
printf (“Correct…in second chance
”);
return 1;
} else {
if(n==l)
printf(“Wrong…in first chance
”);
else
{
printf(“Wrong…in second chance
”);
printf(“Correct answer is %d
”, answer);
}
return 0;
}
}
The program above is self-explanatory and involves all the standard queue operations. On execution of the program, one gets the information on how to use it.
E
XERCISES
1. Convert each of the following infix expressions to postfix.
(a) X-Y +Z
(b) X+Y/Z +W
(c) (X+Y)/Z +W
(d) X- (Y- (Z- (W-U )))
2. Convert each of the following postfix expressions to infix.
(a) X Y +Z-
(b) XY + Z - WU*/
(c) XYZW-+*
(d) XY / Z W / /
3. Write C functions to convert
(a) A prefix string to infix notation
(b) A postfix string to prefix notation
4. Convert the following boolean expressions to Reverse Polish Notation.
(a) X && (Y ||! Z )
(b) (X || (Y&&!Z)&&(W || U)
(c) ((X< 7 ) && (X >9)) II ! (X > 0)
(d) (X!= Y) && ( Z!= W)
5. Modify the program in Example 6.2 so that it can accept the binary operator % (mod) and unary operator – (minus).
6. Write an expression evaluator in C that accepts an infix expression involving logical operators ( &&, ||,!) and relational operators (<, >, <=, >=, ==, != ), converts to RPN, and then evaluates to 1 or 0 depending on true or false, respectively.
7. A stack is to be implemented so that a stack member should hold a list of integers. Implement such a stack. Also write the push and pop routines that can be used on such a stack.
8. Instead of a stack, implement a queue so that each element of the queue holds a list of integers. Write the functions addQ and removeQ for such a queue.