Chapter 4
Stacks and Queues
CHAPTER OUTLINE
4.1 STACKS
We are familiar with arrays and the operations performed on them. The various elements can be accessed from any position in a list, stored in an array. Some practical applications require that the additions or deletions be done only at one end. For example, the packets of wheat floor received in a super bazaar are put on top of another in the order of their arrival. Now, a customer can remove only the packet currently lying on the top, i.e., the last packet arrived in the bazaar is the first one to leave. The second customer would get the second last packet and so on. In the mean time, if more packets arrive then they will be added on the current top as shown in Figure 4.1.
Fig. 4.1 The stack
It may be noted that in this kind of arrangement, all additions and deletions are made only from one end called top. In general, this activity is called stacking and the structure that allows deletions and additions from one end (top) is called a stack. It is also called LIFO (Last In First Out) data structure.
In a restaurant, the dish washing unit maintains the washed plates in a spring-loaded container. The newly washed plate is pushed on the top of the container and the customer may pop a plate from the top only. Therefore, the addition and deletion operations from a stack are accordingly also called Push and Pop, respectively as shown in Figure 4.2.
Fig. 4.2 The stack operations
Similarly, the nested calls to functions and procedures are also handled in LIFO fashion in the sense that control from last called procedure is handled first.
A stack can be more precisely defined as a linear collection of items which allows addition and dele-tion operations only from one end called top.
The push operation adds an item onto the top of the stack whereas the pop operation removes an element from the current top of the stack. The size of the stack depends upon the number of items present in the stack. With the addition and deletion of items, the size of stack accordingly increases or decreases. Therefore, stack is also called a dynamic data structure with a capacity to enlarge or shrink.
4.1.1 Stack Operations
As already discussed, there are two main operations (push and pop) associated with a stack. The push operation adds an item on the top of the stack whereas the pop operation removes an item from the top of the stack. Let us consider the stack shown in Figure 4.3 (a). Currently the Top, a variable, is point-ing to the item ‘D’. Let us now push an item ‘E’ on the stack. The Top is incremented to next location and the item is added at the pointed location as shown in Figure 4.3(b).
Fig. 4.3 Push operation on stack
It may be noted that the variable called Top keeps track of the location where addition can be done. If there is a bound on the size of the stack (say N) then as soon as the Top be-comes equal to N, the stack is said to be full.
Let us now apply pop operation three times in succession and see the results. The following three items will be removed from the stack in LIFO fashion:
The variable top is also decremented accordingly after each Pop operation as shown in Figure 4.4.
Fig. 4.4 Pop operations on the stack
It may be noted that if more pop operations are done on the stack then a stage will come when there will be no items left on the stack. This condition is called stack empty.
The algorithms for push and pop operations are given below. These algorithms use an array called Stack[N] to represent a stack of N locations. A variable called Top keeps track of the top of the stack, i.e., the location where additions and deletions are made. Another variable called item is used to store the item to be pushed or popped from the stack.
The algorithm for push is given below:
Algorithm Push()
{
Step
1. If (Top >= N) then { prompt (“Stack Full”); exit}
2. Top = Top + 1;
3. Stack [Top] = item;
4. Stop
}
It may be noted that the item is added to the stack (i.e., push operation) provided the stack is not already full, i.e., at step1, it is checked whether or not the stack has room for another item.
The algorithm for pop is given below:
Algorithm Pop()
{
Step
1. if (Top < 0) then prompt (“Stack Empty”);
else
Item = Stack [Top];
Top = Top - 1;
2. stop
}
It may be noted that in the above algorithm, before popping an item from the top, it is checked at step 1 to see if there is at least one item on the stack that can be removed.
The performance of the stack data structure for ‘n’ elements is:
- The space complexity is O(n).
- The time complexity of each operation is O(1).
- The size of the stack, implemented using array, must be defined in advance, i.e., a priori. Moreover, the size cannot be changed.
Example 1: Write a program in ‘C’ that uses the following menu to simulate the stack operations on items of int type.
| Menu – stack operations | |
| Push an item | 1 |
| Pop an item | 2 |
| Display stack | 3 |
| Quit | 4 |
Solution: The above defined algorithms Push() and Pop() would be employed to write the program. The menu would be created using printf () statements and displayed within a do-while loop. In fact, a do-while loop is the most appropriate loop for display and manipulations of menu items.
- The Push() function would return 1 if the operation is successful and 0 otherwise, i.e., 0 indicates that the stack was full.
- The Pop() function would return the popped value if the operation is successful and 9999 otherwise, i.e., the unusual value ‘9999’ indicates that the stack was empty.
The required program is given below:
/* This program simulates stack operations */
#include <stdio.h>
#include <conio.h>
int push (int stak[], int *top, int val, int size);
int pop (int stak[], int *top);
void display (int stack[], int top);
void main()
{
int stack[20]; /* the stack declaration */
int top = −1; /* initially the stack is empty */
int val;
int size;
int choice;
int result;
printf(“
Enter the size of the stack”);
scanf (“%d”, & size);
size−−; /* adjusted for index = 0 */
/* create menu */
do
{
clrscr();
printf (“
Menu – Stack Operations”);
printf (“
Push 1”);
printf (“
Pop 2”);
printf (“
Display stack 3”);
printf (“
Quit 4”);
printf (“
Enter your choice:”);
scanf (“%d”, & choice);
switch (choice)
{
case 1: printf (“
Enter the value to be pushed”);
scanf (“%d”, & val);
result = push( stack, &top, val, size);
if (result == 0)
printf (“
The stack full”);
break;
case 2: result = pop( stack, &top);
if (result == 9999)
printf (“
The stack is empty”);
else
printf (“
The popped value = %d”, result);
break;
case 3: display (stack, top);
break;
}
printf (“
Press any key to continue”);
getch();
}
while (choice != 4);
}
int push (int stack[], int *top, int val, int size)
{
if (*top >= size)
return 0; /* the stack is Full */
else
{
*top= *top + 1;
stack[*top]= val;
return 1;
}
}
int pop (int stack[], int *top)
{int val;
if (*top < 0)
return 9999; /* the stack is empty */
else
{
val = stack[*top];
*top = *top − 1;
return val;
}
}
void display (int stack[], int top)
{
int i;
printf (“
The contents of stack are:”);
for (i = top; i >=0; i−−)
printf (“%d ”, stack[i]);
}
4.2 APPLICATIONS OF STACKS
The stacks are used in numerous applications and some of them are as follows:
- Arithmetic expression evaluation
- Undo operation of a document editor or a similar environment
- Implementation of recursive procedures
- Backtracking
- Keeping track of page-visited history of a web user
4.2.1 Arithmetic Expressions
An arithmetic expression is a combination of variables and/or constants connected by arithmetic operators and parenthesis. The valid arithmetic operators are given in Table 4.1.
Table 4.1 Arithmetic operator
| Symbol | Stands for | Example |
|---|---|---|
| ^ | Exponentiation | X^8 |
| / | Division | X/Y |
| * | Multiplication | X*Y |
| + | Addition | X + Y |
| – | Subtraction | X – Y |
The rules for an arithmetic expression are:
- A signed or unsigned variable or constant is an expression.
- An expression connected by an arithmetic operator to a variable or constant is an expression.
- Two expressions connected by an arithmetic operator is also an expression.
- Two arithmetic expressions should not occur in continuation.
Examples of some valid arithmetic expressions are:
- Sum + 10
- Total – 100
- Total/Rate*Interest
- X^Y – B*C
Examples of some invalid arithmetic expressions are:
- X*/Y (two operators in continuation)
- X Y (expression without an operator)
The order of evaluation, known as operator precedence, is carried out according to the priority of the arithmetic operators given in Table 4.2.
Table 4.2 Operator precedence
| S. No. | Operator(s) | Priority |
|---|---|---|
| 1 | ^ , exponentiation | 3 |
| 2 | / *, division, multiplication | 2 |
| 3 | + −, addition, subtraction | 1 |
Note:
- The operators of same priority like (*, /) or (+, –) are performed from left to right.
- The operators contained within parentheses are evaluated first. When the parentheses are nested, the innermost is evaluated first and so on.
- The exponential operators are evaluated from right to left. For example, in the following expression,
The sub-expressions are evaluated from right to left as shown in Figure 4.5.
Fig. 4.5 Evaluation of exponential operator
The arithmetic expression, as discussed above, is called an infix expression wherein the operator is placed between two operands. The evaluation takes place according to priorities assigned to the operators (see Table 4.2). However, to overrule the priority of an operator, parenthesis is used. For example, the two infix expressions given below are entirely different because in Expression 2, the priority of the division operator ‘/’ has been overruled by the embedded parenthesis.
- X – Y/Z
- ( X – Y )/Z
The order of evaluation of above infix expressions is shown in Figure 4.6.
Fig. 4.6 Evaluation order of infix expressions
Thus, parenthesis play an important role in the evaluation of an infix expression and the order of evaluation depends upon the placement of parentheses and the operator precedence. Therefore, the infix representation of arithmetic expressions becomes inefficient from the compilation point of view. The reason being that to find the sub-expression with highest priority, at each step, repeated scanning of the expression is required from left to right.
A Polish logician J. Lukasicwicz introduced a notation which permits arithmetic expressions without parentheses. The absence of embedded parentheses allows simpler compiler interpretation, translation, and execution of arithmetic expressions. This notation is also called Polish notation. It appears in two forms: prefix and postfix forms.
4.2.1.1 Prefix Expression (Polish Notation)
In the prefix form, an operator is placed before its operands, i.e., the operators are prefixed to their operands. For example, the infix expression A + B is written as ‘+AB’ in prefix form.
Examples of some valid prefix expressions with their equivalent infix expressions are given in Table 4.3.
Table 4.3 Some prefix expression
| Prefix expression | Equivalent infix expression |
| +AB | A + B |
| *+ABC | (A + B)*C |
| +/A + BC*D – EF | A/(B + C) + D*(E – F) |
4.2.1.2 Postfix Expression (Reverse Polish Expression)
In the postfix expression, the operator is placed after its operands, i.e., the expression uses suffix or postfix operators. For example, the infix expression ‘A + B’ is written as ‘A B +’ in postfix form.
Examples of some valid postfix expressions with their equivalent infix expressions are given in Table 4.4.
Table 4.4 Some postfix expression
| Postfix expression | Equivalent infix expression |
| AB+ | A + B |
| AB + C* | (A + B)*C |
| ABC +/DEF –*+ | A/(B + C) + D*(E – F) |
It may be noted that in Polish and reverse Polish notations, there are no parentheses and, therefore, the order of evaluation will be determined by the positions of the operators and related operands in the expression.
A critical look at the postfix expressions indicates that such representation is excellent from the execution point of view. The reason being that while execution, no consideration has to be given to the priority of the operators rather the placement of operators decides the order of execution. Moreover, it is free from parentheses. Same is true for prefix expressions but in this book, only the postfix expressions would be considered.
Thus, there is a need for conversion of infix to postfix expression. The subsequent section discusses two methods to convert the infix expressions to postfix expressions.
4.2.1.3 Conversion of Infix Expression to Postfix Expression
An infix expression can be converted into postfix by two methods: parenthesis method and stack method.
- Parenthesis method The following steps are used to convert an infix expression to postfix expression by parenthesis method:
- Fully parenthesize the infix expression.
- Replace the right hand parenthesis by its corresponding embedded operator.
- Remove the left hand parenthesis. The resultant expression is in postfix notation.
Consider the infix expression A/(B + C) + D*(E − F). Let us apply the above steps to convert this expression to postfix notation. The operations are shown in Figure 4.7.
The method discussed above is rather inefficient because it requires following two passes over the expression:
- The first pass to fully parenthesize the expression.
- The second pass to replace the right hand parentheses by their corresponding embedded operators.
It may be noted that the infix expression within innermost parentheses should be the first to be converted into postfix before expressions in outermost parentheses are picked. This successive elimination of parentheses is done until whole of the expression is converted into postfix. This LIFO nature of the 2nd pass suggests that a stack can be used for the conversion process.
- The stack method In this method, two priorities are assigned to the operators: instack priority and incoming priority as shown in Table 4.5.
Table 4.5 Priorities assigned to operator in the stack method
Fig. 4.7 Conversion of infix to postfix expressions
It may be noted that the left hand parenthesis ‘(’ has the highest incoming priority and least instack priority.
Let us assume that an infix expression is terminated by the character ‘;’. We shall call operators and operands of an expression by a general name element. The following broader level algorithm convert() can be used to convert an infix expression to postfix expression.
Algorithm convert()
{
Step
1. Scan the expression from left to right.
2. If the element is an operand, then store the element into the target area.
3. If the element is an operator, then push it onto a stack with following rules:
3.1 While the incoming priority is less than or equal to instack priority, pop the operators and store into the target area.
3.2 If the element is right hand parenthesis ’)’, then pop all the elements from the stack till left hand parenthesis ’(’ is popped out. The popped elements are stored in the target area.
4. If the element is ’;’, then pop all the elements till the stack is empty and store them into the target area.
5. Stop
}
Example 2: Write a program that uses a stack to convert an infix expression to a postfix expression.
Solution: We would employ the algorithm convert(), given above. The following data structures would be used:
The list of allowed binary operators along with their icp and isp is stored in an array of structures called ‘opTab[]. An array called stack of type operator A is the main data structure. match() function is being used to find out as to whether a given element is an operator or an operand depending upon the result (res) of match operation. The required program is given below:
/* This program converts an infix expression to a postfix expression */
#include <stdio.h>
#include <conio.h>
struct operator { /* operator declaration*/
char opName;
int isp;
int icp;
};
int push (struct operator stak[], int *top, struct operator val, int size);
struct operator pop (struct operator stak[], int *top);
void display (struct operator stack[], int top);
int match(struct operator opTab[8], char element, struct
operator *op);
void main()
{
char infix[20];
char target[20];
struct operator stack[20]; /* the stack declaration */
int top = −1; /* initially the stack is empty */
int res;
char val;
int size;
int pos;
int i;
struct operator op, opTemp;
struct operator opTab[8] = {’(’, 0, 6, /* The operators
information */
’)’, 0, 0,
’^’, 4, 5,
’*’, 3, 3,
’/’, 3, 3,
’+’, 2, 2,
’−’, 2, 2,
’;’, 0, −1,
};
printf (“
Enter the size of the infix expression”);
scanf (“%d”, &size); size--;
printf (“
Enter the terms of infix expression one by one”);
for (i= 0; i <= size; i++)
{fflush(stdin); /* flush the input buffer */
scanf (“%c”, &infix[i]);
}
pos = 0; /* position in target expression */
for (i=0; i <= size; i++)
{
res = match(opTab, infix[i], &op); /* find whether operator/operand */
if (res==0)
{target[pos] = infix[i]; /* store into target expression */
pos++;
}
else
{if (top < 0)
push (stack, &top, op, size); /* first time Push */
else
{opTemp.opName=’#’; /* place any value to opTemp */
if (op.opName == ’)’)
{ while (opTemp.opName != ’(’ )
{
opTemp = pop (stack, &top);
if (opTemp.opName != ’(’ ) /* omit ’(’ */
{ target [pos] = opTemp.opName;
pos++;
}
}
}
else
{while (stack[top].isp >= op.icp && top >=0)
{
opTemp = pop (stack, &top);
target [pos] = opTemp.opName;
pos++;
}
push(stack, &top, op, size);
}
}
}
}
/* print the postfix expression */
printf (“
The postfix expression is:”);
for (i = 0; i < pos; i++)
{
printf (“%c”, target[i]);
}
}
int push (struct operator stack[], int *top, struct operator val, int size)
{
if ( *top >= size)
return 0; /* the stack is full */
else
{
*top= *top + 1;
stack[*top]= val;
return 1;
}
}
struct operator pop (struct operator stack[], int *top)
{struct operator val;
if (*top < 0)
{val.opName =’#’;
return val; /* the stack is empty */
}
else
{
val = stack[*top];
*top = *top − 1;
return val;
}
}
void display (struct operator stack[], int top)
{
int i;
printf (“
The contents of stack are:”);
for (i = top; i >=0; i--)
printf(“%c ”, stack[i].opName);
}
int match(struct operator opTab[8], char element, struct operator*op)
{
int i;
for (i =0; i <8; i++)
{
if (opTab[i].opName == element)
{
*op = opTab[i];
return 1;
}
}
return 0;
}
For following given infix expressions, the above program produces the correct output as shown below
| Infix expression | Postfix expression |
| (1) A ^ B ^ C + D; | A B C ^ ^ D + |
| (2) (A – B)*( C/D ) + E; | A B – C D/* E + |
Example 3: Use a stack to convert the following infix arithmetic expression into a postfix expression. Show the changing status of the stack in tabular form.
Solution: We would use the algorithm convert(). The simulation of this algorithm for the above expression is given in Table 4.6.
Table 4.6 Conversion of A + B*C into its postfix form
The output postfix expression is ABC* +
Example 4: Use a stack to convert the following infix arithmetic expression into a postfix expression. Show the changing status of the stack in tabular form.
Solution: We would use the algorithm convert(). The simulation of this algorithm for the above expression is given in Table 4.7.
Table 4.7 Conversion of (A – B)*(C/D) + E into its postfix form
The output postfix expression is AB – CD/* E+
Example 5: Use a stack to convert the following infix arithmetic expression into a postfix expression. Show the changing status of the stack in tabular form.
Solution: We would use the algorithm convert(). The simulation of this algorithm for the above expression is given in Table 4.8.
Table 4.8 Conversion of X + Y*Z ^ P – (X/Y + Z)
The output postfix expression is XYZP^* + XY/Z+–
Note: Since a postfix expression has no parentheses, its evaluation becomes a very easy exercise. In fact, a stack can be suitably used for this purpose.
4.2.1.4 Evaluation of Postfix Expressions
A stack can be conveniently used for the evaluation of postfix expressions. The expression is read from left to right. Each encountered element is examined. If the element is an operand, then the element is pushed on to the stack. If the element is an operator, then the two operands are popped from the stack and the desired operation is done. The result of the operations is again pushed onto the stack. This process is repeated till the end of the expression (i.e., ‘;’) is encountered. The final result is popped from the stack.
An algorithm for the evaluation of a postfix expression is given below:
Algorithm eval Postfix()
{
Step
1. pick an element from the postfix expression
2. if (element is an operand)
if ( element != ’;’)
{push element on the stack}
else
{
pop result from the stack;
print the result;
exit to step 4;
}
else
{
pop operand1 from stack;
pop operand2 from stack;
perform the operation;
push result on the stack;
}
3. repeat steps 1 and 2
4. stop
}
Example 6: Write a program that uses a stack to evaluate a postfix expression.
Solution: The algorithm evalPostfix() and the following data structures would be used for the required program. The postfix expression will be stored in an array called postfix[] of following structure type.
struct term /* structure to store an element */
{
char element;
float val;
};
where
’element’ stores an operand or an operator.
’val’ stores the actual value of the operand or 0 for an operator.
For instance, the expression ABC*+; for values A = 10, B = 15, C = 8 will be stored in postFix[] as shown below:
postFix
An array called stack of type float would also be used.
The required program is given below:
/* This program uses a stack to evaluate a postfix expression */
#include <stdio.h>
#include <conio.h>
struct term /* structure to store an element */
{
char element;
float val;
};
/* array to store the postfix expression*/
int push (float stack[], int *top, float val, int size);
float pop (float stack[], int *top);
void main()
{
float stack[20];
struct term postFix[20];
int top = −1;
int i;
int size;
float result;
int temp;
float op1, op2; /* the operands */
printf (“
Enter the number of elements in the postfix expression”);
scanf (“%d”, & size);
printf (“
Enter the expression as element value pair”);
printf (“
Enter 0 for an operator including ’;’”);
for (i = 0; i<size; i++)
{
printf (“
Enter element – val pair”);
fflush (stdin);
scanf (“%c %f”, &postFix[i]. element, &postFix[i].val);
}
for (i=0; i< size; i++)
{
switch (postFix[i].element)
{
case ’+’ : op2 = pop (stack, &top);
op1 = pop (stack, &top);
result = op1 + op2;
temp = push (stack, &top, result, size);
if (temp ==0) printf(“
stack full”);
break;
case ’*’ : op2 = pop (stack, &top);
op1 = pop (stack, &top);
result = op1*op2;
temp = push (stack, &top, result, size);
if (temp ==0) printf(“
stack full”);
break;
case ’−’ : op2 = pop (stack, &top);
op1 = pop (stack, &top);
result = op1 − op2;
temp= push (stack, &top, result, size);
if (temp ==0) printf(“
stack full”);
break;
case ’/’ : op2 = pop (stack, &top);
op1 = pop (stack, &top);
result = op1/op2;
temp = push (stack, &top, result, size);
if (temp ==0) printf(“
stack full”);
break;
case ’;’ : result = pop (stack, &top);
printf (“
The result = %8.2f ”, result);
break;
default: temp= push (stack, &top, postFix[i].val,size);
if (temp ==0) printf(“
stack full”);
}
}
}
int push (float stack[], int *top, float val, int size)
{
if (*top < size)
{
*top = *top +1;
stack [*top] = val;
return 1;
}
else
return 0;
}
float pop (float stack[], int *top)
{
float term;
term = 0;
if (*top >=0)
{
term = stack[*top];
*top=*top−1;
return term;
}
else
return term;
}
For following given input:
A 8
B 6
C 20
* 0
− 0
; 0
the program gives the following output:
The Result = –112.00
Example 7: Use a stack to evaluate the following postfix arithmetic expression. Show the changing status of the stack in tabular form.
Solution: We would use the algorithm evalPostfix(). The simulation of this algorithm for the above expression is given in Table 4.9.
Table 4.9 Evaluation of A B C * –
Example 8: Use a stack to evaluate the following postfix arithmetic expression. Show the changing status of the stack in tabular form.
Solution: We would use the algorithm evalPostfix(). The simulation of this algorithm for the above expression is given in Table 4.10.
Table 4.10 Evaluation of X Y Z P ^ * + A B/C + –
4.3 QUEUES
A queue is the most common situation in this world where the first person in the line is the person to be served first; the new comers join at the end. We find that in this kind of arrangement, all additions are made at one end and the deletions made at the other. The end where all additions are made is called the rear end. The other end from where the deletions are made iscalled the front end as shown in Figure 4.8.
Fig. 4.8 The queue
The queue is also a linear data structure of varying size in the sense that the size of a queue depends upon the number of items currently present in it. With additions and/or deletions, the size of the queue increases or decreases, respectively. Therefore, the queue is also a dynamic data structure with a capacity to enlarge or shrink.
Consider the queue of processes shown in Figure 4.9. The operating system maintains a queue for scheduled processes that are ready to run. The dispatcher picks the process from the front end of the queue and dispatches it to CPU and a new process joins at the rear end of the queue.
Fig. 4.9 Queue of processes maintained in the main memory
It may be noted that when the new processes join in, the size of the queue increases whereas the size of the queue will reduce when processes finish their job and leave the system.
4.3.1 Queue Operations
A queue, being a linear data structure, can be comfortably mapped on a one-dimensional array. Let us consider a queue maintained in an array called Queue[N], shown in Figure 4.10. A variable called Front is pointing to the logical front end of the queue from where the removal or deletion of an element takes place. Currently, Front is pointing to an empty location in the queue. Similarly, a variable called Rear is pointing to the logical rear end of the queue where the new elements can be added. Currently, Rear is pointing to a location containing the item ‘G’.
Fig. 4.10 An array representation of a queue
Let us now add an item ‘H’ into the queue. Before the item is added into the queue, the Rear is incremented by one to point to the next vacant location as shown in Figure 4.11. The new item ‘H’ is added at location currently being pointed by Rear.
Fig. 4.11 Addition of the item ‘H’ at the rear end
It may be noted that if more additions are made on the queue, then a stage would come when Rear = N − 1, i.e., last location of the array. Now, no more additions can be performed on the queue. This condition (Rear = N − 1) is called Queue-Full.
Let us now delete an item from the queue. Before an item is deleted or removed, the Front is incremented by one to point to the next location, i.e., the location containing item ‘A’. The item (i.e., ‘A’) is then deleted as shown in Figure 4.12.
Fig. 4.12 Deletion of the item ‘A’ from the front end
It may be noted that if more deletions are done on this queue, then a stage would reach when there will be no items on the queue, i.e., Front = Rear as shown in Figure 4.13. This condition (Front = Rear) is called Queue_empty.
Fig. 4.13 No item in the queue
The algorithms for addition and deletion operations on the queue are given below. These algorithms use an array called Queue[N] to represent a queue of size N locations. A variable called Front keeps track of the front of the queue, i.e., the location from where deletions are made. Another variable called Rear keeps track of the rear end of the queue, i.e., the location where additions are made. Another variable called item is used to store the item to be added or deleted from the queue.
The algorithm for addition is given below:
Algorithm addQ()
{
Step
1. if (Rear >= N) then {prompt (“Queue Full”); exit}
2. Rear = Rear + 1;
3. Queue [Rear] = item;
4. stop
}
It may be noted that the item is added to the queue (i.e., addition operation) provided the queue is not already full, i.e., it is checked at step1 whether or not the queue has room for another item.
The algorithm for deletion is given below:
Algorithm delQ()
{
Step
1. if (Front == Rear) then prompt (“Queue Empty”);
else
Front = Front + 1
Item = Queue [Front];
2. stop
}
Note that in the above algorithm, before removing an item from the queue, it is checked at step 1 to see if there is at least one item on the queue that can be removed.
The performance of the queue data structure for ‘n’ elements is given below:
- The space complexity is O(n).
- The time complexity of each operation is O(1).
- The size of the queue, implemented using array, must be defined in advance, i.e., a priori. Moreover, the size cannot be changed.
Example 9: Write a program in ‘C’ that uses the following menu to simulate the queue operations on items of int type.
| Menu – Queue operations | |
| Add an item | 1 |
| Delete an item | 2 |
| Display Queue | 3 |
| Quit | 4 |
Solution: The above defined algorithms addQ() and delQ() would be employed to write the program. The menu would be created using printf () statements and displayed within a do-while loop. In fact, a do-while loop is the most appropriate loop for display and manipulations of menu items.
Note:
- The addQ() function would return 1 if the operation is successful and 0 otherwise, i.e, 0 indicates that the queue was full.
- The delQ() function would return the deleted value if the operation is successful and 9999 otherwise, i.e., the unusual value ‘9999’ indicates that the queue was empty.
The required program is given below:
/* This program simulates queue operations */
#include <stdio.h>
#include <conio.h>
int addQ (int Queue[], int *Rear, int val, int size);
int delQ (int Queue[], int *Front, int *Rear);
void display (int Queue[], int Front, int Rear);
void main()
{
int Queue[20]; /* the queue declaration */
int Front;
int Rear;
int val;
int size;
int choice;
int result;
Front = Rear=0; /* initially the queue set to be empty */
printf(“
Enter the size of the queue”);
scanf (“%d”, & size);
size--; /* adjusted for index = 0 */
/* create menu */
do
{
clrscr();
printf (“
Menu - Queue Operations”);
printf (“
Add 1”);
printf (“
delete 2”);
printf (“
Display queue 3”);
printf (“
Quit 4”);
printf (“
Enter your choice:”);
scanf (“%d”, & choice);
switch (choice)
{
case 1: printf (“
Enter the value to be added”);
scanf (“%d”, & val);
result = addQ(Queue, &Rear, val, size);
if (result == 0)
printf (“
The queue full”);
break;
case 2: result = delQ(Queue, &Front, &Rear);
if (result == 9999)
printf (“
The queue is Empty”);
else
printf (“
The deleted value = %d”, result);
break;
case 3: display (Queue, Front, Rear);
break;
}
printf(“
Press any key to continue”);
getch();
}
while (choice != 4);
}
int addQ (int Queue[], int *Rear, int val, int size)
{
if ( *Rear >= size)
return 0; /* the queue is Full */
else
{
*Rear= *Rear +1;
Queue[*Rear] = val;
return 1;
}
}
int delQ (int Queue[], int *Front, int *Rear)
{ int val;
if (*Front == *Rear)
return 9999; /* the queue is empty */
else
{
*Front = *Front + 1;
val = Queue[*Front];
return val;
}
}
void display (int Queue[], int Front, int Rear)
{
int i;
printf (“
The contents of queue are:”);
for (i = Front+1; i <= Rear; i++)
printf (“%d ”, Queue[i]);
}
Note:
- The drawback of a linear queue is that a stage may arrive when both Front and Rear are equal and point to the last location of the array as shown in Figure 4.14.
Now, the queue is useless because the queue is full (Rear > = N − 1) as well as empty (Front =Rear). Thus, no additions and deletions can be performed. This situation can be handled by resetting Front and Rear to 0th location, i.e., Front = Rear = 0.
- The major drawback of linear queue is that at a given time, all the locations to the left of Front are always vacant and unutilized.
Fig. 4.14 The queue is empty as well as full
4.3.2 Circular Queue
The drawback of the linear queues, as discussed above, can be removed by making the queue spill over the elements from last position of array to the 0th element. This arrangement of elements makes the queue as circular queue wherein as soon as Rear or Front exceeds N − 1, it is set to 0. Now, there is no end of the queue. The Rear and Front will move around in the queue in the circle and no locations shall be left vacant.
Let us add an item ‘C’ to the queue of Figure 4.14. The Rear is pointing to location N−1. After incrementing Rear (i.e., Rear = Rear + 1 = N − 1 + 1 = N), we find that it is pointing to a location equal to N, which does not exist. Therefore, Rear is set to location 0, the beginning of the array and the item ‘C’ is stored at this location pointed by Rear as shown in Figure 4.15.
Fig. 4.15 The rear is made to move to the 0th location.
Now, this arrangement ensures that there will be no space left unutilized in the queue. For instance, let us add one by one the items ‘I’, ‘R’, ‘C’, ‘U’, ‘L’, ‘A’ and ‘R’ to the queue (see Figure 4.16). We find that the locations left of Front are now being filled, removing the drawback of linear queues.
Fig. 4.16 More additions to circular queue
It may be noted that after more additions, a stage will come when Rear becomes equal to Front (Rear = Front), indicating that the queue is full.
Let us now delete an element from the queue. The Front is pointing to location N−1. After incrementing Front (i.e., Front = Front + 1 = N − 1 + 1 = N), we find that it is pointing to a location equal to N, which does not exist. Therefore, Front is set to location 0, the beginning of the array and the item ‘C’ is deleted from this location pointed by Front as shown in Figure 4.17.
Fig. 4.17 For deletion, Front is set to 0th location
It may be noted that after more deletions, a stage will come when Front becomes equal to Rear (Front = Rear), indicating that the queue is empty.
It may be further noted that a very interesting situation has turned up, i.e., for both events—queue ‘full’ and ‘empty’—the condition to be tested is (Rear = Front). This conflict can be resolved by the following decisions:
- The queue empty condition remains the same, i.e., ‘Front == Rear’.
- In case of queue full, the condition ‘Rear + 1 == Front’ would be tested.
- In this arrangement one location, being pointed by Front, shall remain vacant.
- The following formulae would be used for automatic movement of the variables ‘Front’ and ‘Rear’ within the circular queue:
Rear = (Rear + 1) mod N
Front = (Front + 1) mod N
where N is the size of the queue.
The algorithms for addition and deletion operations in a circular queue are given below. These algorithms use an array called cirQ[N] to represent a queue of size N locations. A variable called Front keeps track of the front of the queue, i.e., the location from where deletions are made. Another variable called Rear keeps track of the rear end of the queue, i.e., the location where additions are made. Another variable called item is used to store the item to be added or deleted from the queue.
The algorithm for addition is given below:
Algorithm addQ()
{
Step
1. if ( ((Rear + 1) % N) == Front)
then { prompt (“Queue Full”); exit}
2. Rear = (Rear + 1) % N;
3. cirQ [Rear] = item;
4. stop
}
It may be noted that the item is added to the queue (i.e., addition operation) provided the queue is not already full, i.e., at step1 it is checked whether or not the queue has room for another item.
The algorithm for deletion is given below:
Algorithm delQ()
{
Step
1. if (Front == Rear) then prompt (“Queue Empty”);
else
Front = (Front + 1) % N
Item = Queue [Front];
return Item;
2. stop
}
Note that in the above algorithm, before removing an item from the queue, it is checked at step 1 to see if there is at least one item on the queue that can be removed.
Example 10: Write a program in ‘C’ that uses the following menu to simulate the circular queue operations on items of int type.
| Menu – Circular Queue operations | |
| Add an item | 1 |
| Delete an item | 2 |
| Display Queue | 3 |
| Quit | 4 |
Solution: The above defined algorithms addQ() and delQ() for circular queue would be employed to write the program. The menu would be created using printf () statements and displayed within a do-while loop.
Note:
- The addQ() function would return 1 if the operation is successful and 0 otherwise, i.e., 0 indicates that the queue was full.
- The delQ() function would return the deleted value if the operation is successful and 9999 otherwise, i.e., the unusual value ‘9999’ indicates that the queue was empty.
The required program is given below:
/* This program simulates Circular Queue operations */
#include <stdio.h>
#include <conio.h>
int addQ (int cirQ[],int *Front, int *Rear, int val, int size);
int delQ (int cirQ[], int *Front, int *Rear, int size);
void display (int cirQ[], int Front, int Rear, int size);
void main()
{
int cirQ[20]; /* the queue declaration */
int Front;
int Rear;
int val;
int size;
int choice;
int result;
Front = Rear=0; /* initially the queue set to be empty */
printf (“
Enter the size of the queue”);
scanf (“%d”, & size);
/* create menu */
do
{
clrscr();
printf (“
Menu – Circular queue operations”);
printf (“
Add 1”);
printf (“
Delete 2”);
printf (“
Display queue 3”);
printf (“
Quit 4”);
printf (“
Enter your choice:”);
scanf (“%d”, & choice);
switch (choice)
{
case 1: printf (“
Enter the value to be added”);
scanf (“%d”, & val);
result = addQ(cirQ, &Front, &Rear, val, size);
if (result == 0)
printf (“
The queue full”);
break;
case 2: result = delQ(cirQ, &Front, &Rear, size);
if (result == 9999)
printf (“
The queue is Empty”);
else
printf (“
The deleted value = %d”, result);
break;
case 3: display (cirQ, Front, Rear, size);
break;
}
printf(“
Press any key to continue”);
getch();
}
while (choice != 4);
}
int addQ (int cirQ[],int * Front, int *Rear, int val, int size)
{
if ( ((*Rear + 1) % size) == *Front)
return 0; /* the queue is Full */
else
{
*Rear= (*Rear + 1) % size;
cirQ[*Rear]= val;
return 1;
}
}
int delQ (int cirQ[], int *Front, int *Rear, int size)
{int val;
if (*Front == *Rear)
return 9999; /* the queue is empty */
else
{
*Front =(*Front + 1) % size;
val = cirQ[*Front];
return val;
}
}
void display (int cirQ[], int Front, int Rear, int size)
{
int i;
printf (“
The contents of queue are:”);
i=Front;
while ( i != Rear)
{
i = (i + 1) % size;
printf (“%d ”, cirQ[i]);
}
}
It may be noted that the circular queue has been implemented in a one-dimensional array, which is linear by nature. We only view the array to be a circle in the sense that it is imagined that the last location of the array is immediately followed by the 0th location as shown in Figure 4.18.
Fig. 4.18 The circular queue
The shaded area shows the queue elements. When the queue is full, then it satisfies the condition: (Rear + 1) % N == Front. The queue empty condition is indicated by the condition: Front == Rear. However, at least one location remains vacant all the time.
4.3.3 Priority Queue
Sometimes, a queue does not operate on strictly first in first out (FIFO) basis. On the contrary, it stores the elements according to the priority associated with each stored element. In a post office, the airmail has a higher priority than the speed post and speed post in turn has more priority than an ordinary mail. Therefore, the post office makes a queue of mail ordered by their priority, i.e., all airmail letters are placed at the head of the queue followed by speed post letters. The speed post letters are followed by registered parcels and so on. The ordinary mail with least priority lies at the end of the queue.
Let us take an example from operating system. A priority scheduling policy would store the processes as per their priority in a queue. The scheduler will add a new process to the queue according to its priority and the highest priority process would be served first as shown in Figure 4.19.
Fig. 4.19 The priority queue maintained by operating system
In fact, the operating system will have to maintain such priority queues at all non-shareable devices such as printers, plotters, etc.
Note: Since every element in the queue is ordered on priority, an entry into the priority queue has to be a pair (e, p) where ‘e’ is the name of the element and ‘p’ is its priority. In case of records of items, the ‘e’ is chosen to be a field or key of the record.
Consider the job pool given in Table 4.11. The processes opened by the operating system have been assigned priorities.
Table 4.11 Job pool
| Process No. | Priority |
| P8 | 2 |
| P5 | 1 |
| P7 | 9 |
| P4 | 6 |
| P2 | 5 |
Now, the scheduler shall create a priority queue that can store a list of pairs (Process No., priority). It has two possible choices to store the pairs as shown in Figure 4.20.
Fig. 4.20 The choices to store the job pool
Choice (a): The addition operation simply adds the newly arrived job at the rear end, i.e., in the order of its arrival. This operation is O(1).
The deletion operation requires the process with higher priority to be searched and removed, P7 in this case. This operation is O(n) for n elements in the queue as we have to traverse the queue to find the element.
Choice (b): The addition operation requires the process with higher priority to be inserted at its proper position in the queue. This operation is O(n) for n elements in the queue as the location has to be found where the insertion can take place.
The deletion operation simply removes the process from the front of the queue because the process with highest priority is already at the front of the queue. This operation is O(1).
Let us now use the choice (b) to implement a priority queue for processes called ‘proc’ of following structure type
struct proc
{
char process [3];
int priority;
};
The following menu would be used to interact with the users:
| Menu – Priority Queue operations | |
| Add an item | 1 |
| Delete an item | 2 |
| Display Queue | 3 |
| Quit | 4 |
A function called addPq() inserts an ith process ‘pi’ with priority ‘pr’ at its proper position in the priority queue represented using the array pQ[N] where N is the size of the queue. A variable ‘Rear’ points to rear end of the priority queue, i.e., the least priority process.
A function called delPq() removes a process from the current ‘Front’ of the priority queue.
The required program is given below:
/* This program simulates priority queue operations */
#include <stdio.h>
#include <conio.h>
struct proc{
char process[3];
int priority;
};
int addPq (struct proc pQ[], int *Rear, struct proc val, int size);
int delPq (struct proc pQ[], int *Front, int *Rear, struct proc *val);
void display (struct proc pQ[], int Front, int Rear);
void main()
{
struct proc pQ[20]; /* the priority queue declaration */
int Front;
int Rear;
struct proc val;
int size;
int choice;
int result;
Front = Rear=0; /* initially the queue set to be empty */
printf (“
Enter the size of the queue”);
scanf (“%d”, & size);
/* create menu */
do
{
clrscr();
printf (“
Menu – Priority queue operations”);
printf (“
Add 1”);
printf (“
Delete 2”);
printf (“
Display queue 3”);
printf (“
Quit 4”);
printf (“
Enter your choice:”);
scanf (“%d”, & choice);
switch (choice)
{
case 1: printf (“
Enter the process number and its priority to be added”);
scanf (“%s %d”, & val.process, &val.priority);
result = addPq( pQ, &Rear, val, size);
if (result == 0)
{printf (“
The queue full”);}
break;
case 2: result = delPq(pQ, &Front,& Rear, &val);
if (result == 0)
printf (“
The queue is empty”);
else
printf (“
The deleted proc = %s with priority %d”, val. process, val.priority );
break;
case 3: display (pQ, Front, Rear);
break;
}
printf(“
Press any key to continue”);
getch();
}
while (choice != 4);
}
int addPq (struct proc pQ[], int *Rear, struct proc val, int size)
{
int i;
if ((*Rear + 1)>= size)
return 0; /* the queue is Full */
else
{
*Rear= (*Rear + 1);
i=*Rear − 1;
while (val.priority > pQ[i].priority)
{
pQ[i+1] =pQ[i];
i = i − 1;
}
i++;
pQ[i] = val;
}
return 1;
}
int delPq (struct proc pQ[], int *Front, int *Rear, struct proc *val)
{
if (*Front == *Rear)
return 0; /* the queue is empty */
else
{
*Front = (*Front + 1);
*val = pQ[*Front];
return 1;
}
}
void display ( struct proc pQ[], int Front, int Rear)
{
int i;
printf (“
The contents of queue are:”);
i=Front;
while ( i != Rear)
{
i = i + 1;
printf (“(%s , %d) ”, pQ[i].process, pQ[i].priority);
}
}
It may be noted that in order to keep it simple, the priority queue has been implemented as a linear queue. A sample input is given below:
Enter the process number and its priority to be added P4 7
where ‘P4’ is the name of the process and ‘7’ is its priority.
4.3.4 The Deque
A deque is a queue that allows additions and deletions from both ends (see Figure 4.21). This data struc-ture is suitable for implementing the ‘redo and undo’ operations of software such as word processor, paint program, drawing tools, etc.
Fig. 4.21 The deque
A one-dimensional array can be suitably used to implement a deque wherein the following four operations need to be designed:
- addRear(): adds an item at the rear end
- delRear(): removes an item from the rear end
- addFront(): adds an item at the front end
- delFront(): removes an item from the front end
Some programmers view a deque as two stacks connected back to back as shown in Figure 4.22.
Fig. 4.22 The deque (stack view)
For deque arrangement shown in Figure 4.22, the following four operations need to be designed:
- pushRear(): adds an item at the rear end
- popRear(): removes an item from the rear end
- pushFront(): adds an item at the front end
- popFront(): removes an item from the front end
Example 11: Write a program in ‘C’ that uses the following menu to simulate the deque operations on items of int type.
| Menu – deque Queue operations | |
| Add an item at Rear | 1 |
| Add an item at Front | 2 |
| Delete an item from Rear | 3 |
| Delete an item from Front | 4 |
| Display Queue | 5 |
| Quit | 6 |
Solution: A one-dimensional array called dQ[] would be used to implement the deque wherein the following four functions would be used. The algorithms for these functions are same as used in a linear queue.
- addRear(): adds an item at the rear end
- delRear(): removes an item from the rear end
- addFront(): adds an item at the front end
- delFront(): removes an item from the front end
The menu would be created using printf() statements and displayed within a do-while loop.
The required program is given below:
/* This program simulates deQue operations */
#include <stdio.h>
#include <conio.h>
int addRear (int dQ[], int *Rear, int val, int size);
int addFront (int dQ[], int *Front, int val);
int delRear (int dQ[], int *Rear, int *Front, int *val);
int delFront (int dQ[], int *Front, int *Rear, int *val);
void display (int dQ[], int Front, int Rear);
void main()
{
int dQ[20]; /* the queue declaration */
int Front;
int Rear;
int val;
int size;
int choice;
int result;
Front = Rear=0; /* initially the queue set to be empty */
printf(“
Enter the size of the queue”);
scanf (“%d”, & size);
size−−; /* adjusted for index = 0 */
/* create menu */
do
{
clrscr();
printf (“
Menu - dQue Operations”);
printf (“
Add item at Rear 1”);
printf (“
Add item at Front 2”);
printf (“
Delete item from Rear 3”);
printf (“
Delete item from Front 4”);
printf (“
Display deque 5”);
printf (“
Quit 6”);
printf (“
Enter your choice:”);
scanf (“%d”, & choice);
switch (choice)
{
case 1: printf (“
Enter the value to be added”);
scanf (“%d”, & val);
result = addRear(dQ, &Rear, val, size);
if (result == 0)
printf (“
The queue is full”);
break;
case 2: printf (“
Enter the value to be added”);
scanf (“%d”, & val);
result = addFront(dQ, &Front, val);
if (result == 0)
printf (“
The queue is full”);
break;
case 3: result =delRear(dQ, &Rear,& Front, &val);
if (result == 0)
printf (“
The queue is empty”);
else
printf (“
The deleted value = %d”, val);
break;
case 4: result =delFront(dQ, &Front, &Rear, &val);
if (result == 0)
printf (“
The queue is empty”);
else
printf (“
The deleted value = %d”, val);
break;
case 5: display (dQ, Front, Rear);
break;
}
printf(“
Press any key to continue”);
getch();
}
while (choice != 6);
}
int addRear(int dQ[], int *Rear, int val, int size)
{
if (*Rear >= size)
return 0; /* the queue is Full */
else
{
*Rear= *Rear + 1;
dQ[*Rear]= val;
return 1;
}
}
int addFront (int dQ[], int *Front, int val)
{
if (*Front <= 0)
return 0; /* the queue is full */
else
{
dQ[*Front] = val;
*Front = *Front − 1;
return 1;
}
}
int delRear (int dQ[], int *Rear, int *Front, int *val)
{
if ( *Rear==*Front)
return 0; /* the queue is empty */
else
{
*val = dQ[*Rear];
*Rear= *Rear − 1;
return 1;
}
}
int delFront (int dQ[], int *Front, int *Rear, int *val)
{
if (*Front == *Rear)
return 0; /* the queue is empty */
else
{
*Front = *Front + 1;
*val = dQ[*Front];
return 1;
}
}
void display (int Queue[], int Front, int Rear)
{
int i;
printf (“
The contents of queue are:”);
for (i = Front+1; i <= Rear; i++)
printf (“%d ”, Queue[i]);
}
Example 12: The items can be iteratively removed from both ends of a deque and compared with each other. Therefore, the deque can be easily used to determine whether a given string is a palindrome or not. Write a program in ‘C’ that uses a deque to determine whether a given string is a palindrome or not.
Solution: An array called String[N] would be used to store the string. As one location in a queue necessarily remains vacant, an array called dQ[N+1] would be used to implement a deque. The functions developed in Example 11 would be used to do the required task, i.e., to determine whether the input string is palindrome or not.
The required program is given below:
/* This program uses deQue to determine whether a given string is a palindrome or not */
#include <stdio.h>
#include <conio.h>
int addRear (char dQ[], int *Rear, char val, int size);
int delRear (char dQ[], int *Rear, int *Front, char *val);
int delFront (char dQ[], int *Front, int *Rear, char *val);
int addFront (char dQ[], int *Front, char val);
void display (char dQ[], int Front, int Rear);
void main()
{
char String[10];
char dQ[11]; /* the queue declaration */
int Front;
int Rear;
char val, val1,val2;
int i, size;
int flag;
int result;
printf (“
Enter the string”);
scanf (“%s”, String);
i =0;
size=10; /* adjusted for index = 0 */
Front = Rear = 0; /* initially deque is empty */
while ( String[i] != ’ ’) /* Add the string to deque */
{
result = addRear( dQ, &Rear, String[i], size);
if (result == 0)
printf (“
The queue full”);
i++;
}
size = i − 1;
flag = 1; /* Assuming that the string is
while ( flag && result)
{
result = delRear(dQ, &Rear, &Front, &val1);
result = delFront(dQ, &Front, &Rear, &val2);
if (val1 != val2) {flag = 0; break;} /* string is not a palindrome */
}
if (flag==1) printf (“
The string is palindrome”);
else printf (“
The string is not a palindrome”);
}
int addRear(char dQ[], int *Rear, char val, int size)
{
if ( *Rear >= size)
return 0; /* the queue is full */
else
{
*Rear= *Rear + 1;
dQ[*Rear]= val;
return 1;
}
}
int addFront (char dQ[], int *Front, char val)
{
if (*Front <= 0)
return 0; /* the queue is full */
else
{
dQ[*Front] = val;
*Front = *Front − 1;
return 1;
}
}
int delRear (char dQ[], int *Rear, int *Front, char *val)
{
if ( *Rear==*Front)
return 0; /* the queue is empty */
else
{
*val = dQ[*Rear];
/* If the size of string is odd then do not decrement Rear*/
if ( (*Rear − 1) > *Front) *Rear = *Rear−1;
return 1;
}
}
int delFront (char dQ[], int *Front, int *Rear, char *val)
{
if (*Front == *Rear)
{
return 0;
} /* the queue is empty */
else
{
*Front = *Front + 1;
*val = dQ[*Front];
return 1;
}
}
void display (char Queue[], int Front, int Rear)
{
int i;
printf (“
The contents of queue are:”);
for (i = Front+1; i <= Rear; i++)
printf (“%c ”, Queue[i]);
}
Note: The function addFront() of deque system is redundant in this application.
The function delRear() has been suitably modified for strings having odd number of characters.
Example 13: Two stacks can be implemented using a single array. Write a program in ‘C’ that allows push and pop operations from the specified stack. It must also check the conditions ‘stack empty and full’ for a specified stack.
Solution: In a single array, two stacks can be implemented by making them grow from both ends towards the middle as shown in Figure 4.23. It may be noted that 0th element becomes the bottommost element of 1st stack, i.e., stack1. Similarly, the (N − 1)th element becomes the bottommost element of the 2nd stack, i.e., stack2.
Fig. 4.23 Two stacks that grow towards middle of the array
An array called twoStack[N] would be used to implement the required task. Two variables called Top1 and Top2 would keep track of the top locations of stack1 and stack2, respectively. Initially, Top1 and Top2 would be set to locations −1 and N, respectively to suggest that both the stacks are initially empty.
Note: The stack full condition for both the stacks would be: ‘*top1 + 1 = = *top2’
The required program is given below:
/* This program simulates two stacks operations */
#include <stdio.h>
#include <conio.h>
int pushStack1 (int stak[], int *top1,int *top2, int val);
int pushStack2 (int stak[], int *top1,int *top2, int val);
int popStack1 (int stak[], int *top1);
int popStack2 (int stak[], int *top2);
void dispStack1 (int stack[], int top1);
void dispStack2 (int stack[], int top2);
void main()
{
int twoStack[10]; /* the stack declaration */
int top1 = −1; /* initially the stack1 is empty */
int top2 = 10; /* initially the stack2 is empty */
int val;
int choice;
int result;
/* create menu */
do
{
clrscr();
printf (“
Menu − twoStack Operations”);
printf (“
PushStack1 1”);
printf (“
PushStack2 2”);
printf (“
PopStack1 3”);
printf (“
PopStack2 4”);
printf (“
DispStack1 5”);
printf (“
DispStack2 6”);
printf (“
Quit 7”);
printf (“
Enter your choice:”);
scanf (“%d”, & choice);
switch (choice)
{
case 1: printf (“
Enter the value to be pushed”);
scanf (“%d”, & val);
result = pushStack1(twoStack, &top1, &top2, val);
if (result == 0)
printf (“
The stack is full”);
break;
case 2: printf (“
Enter the value to be pushed”);
scanf (“%d”, & val);
result = pushStack2(twoStack, &top1, &top2, val);
if (result == 0)
printf (“
The stack is full”);
break;
case 3: result = popStack1( twoStack, &top1);
if (result == 9999)
printf (“
The stack is empty”);
else
printf (“
The popped value = %d”, result);
break;
case 4: result = popStack2( twoStack, &top2);
if (result == 9999)
printf (“
The stack is empty”);
else
printf (“
The popped value = %d”, result);
break;
case 5: dispStack1 (twoStack, top1);
break;
case 6: dispStack2 (twoStack, top2);
break;
}
printf(“
Press any key to continue”);
getch();
}
while (choice != 7);
}
int pushStack1 (int stack[], int *top1, int *top2, int val)
{
if (*top1 + 1 == *top2)
return 0; /* the stack is full */
else
{
*top1= *top1 + 1;
stack[*top1]= val;
return 1;
}
}
int pushStack2 (int stack[],int *top1, int *top2, int val)
{
if (*top1 + 1 == *top2)
return 0; /* the stack is full */
else
{
*top2= *top2 − 1;
stack[*top2]= val;
return 1;
}
}
int popStack1 (int stack[], int *top1)
{ int val;
if (*top1 < 0)
return 9999; /* the stack is empty */
else
{
val = stack[*top1];
*top1 = *top1 − 1;
return val;
}
}
int popStack2 (int stack[], int *top2)
{ int val;
if (*top2 >10)
return 9999; /* the stack is empty */
else
{
val = stack[*top2];
*top2 = *top2 + 1;
return val;
}
}
void dispStack1 (int stack[], int top1)
{
int i;
printf (“
The contents of stack1 are:”);
for (i = top1; i >=0; i−−)
printf(“%d ”, stack[i]);
}
void dispStack2 (int stack[], int top2)
{
int i;
printf (“
The contents of stack2 are:”);
for (i = top2; i <=10; i++)
printf (“%d ”, stack[i]);
}
EXERCISES
- Give static implementation of stack by writing push and pop routine for it.
- Explain overflow and underflow conditions of a stack with examples.
- How can a stack be used in checking the well-formedness of an expression, i.e., balance of the left and right parenthesis of the expression?
- Write down an algorithm to implement two stacks using only one array. Your stack routine should not report an overflow unless every slot in the array is used.
- Write a non-recursive program to reverse a string using stack.
- Explain prefix, infix, and postfix expressions with examples.
- Describe a method to convert an infix expression in to a postfix expression with the help of a suitable example.
- Translate following infix expressions to their equivalent postfix expressions:
- (x + y – z)/(h + k)*s
- j – k/g^h + (n + m)
- a*(b – c)/d + e*f
- Write a program that evaluates an expression represented in postfix form.
- Evaluate the following postfix expressions for the provided data:
- ab^c*d/e + where a = 5, b = 3, c = d = 2, e = 9
- abcde+* +– where a = 12, b = 4, c = 7, d = 5, e = 2
- ab + cd* + e* where a = 2, b = 6, c = 3, d = 5, e = 9
- What are the applications of a stack? Support your answer with suitable examples.
- What is a linear queue? What are the limitations of linear queue?
- What do you understand by a queue? Write algorithm for inserting and deleting of a data element from the queue.
- Write the functions insert() and delete() for a circular queue.
- Write a menu driven main() program that tests the functions developed in Exercise 14.
- Differentiate between linear queue and circular queue. Which one is better and why?
- Describe the applications of queues.
- What are priority queues? Write their applications.
- What is doubly ended queue? Write a program/algorithm to implement a doubly ended queue (deque).