Unit III
Stack and Queue
Stack is a list of elements in which insertion and deletion of elements can be done only at one end called as top of stack.
To construct a stack we insert element from top of stack.
The operation of inserting an element to stack is called as push and the operation of deleting an element from a stack is called as pop.
Imagine stacking a set of books on top of each other, we can push a new book on top of the stack, and we can pop the book that is currently on the top of the stack.
We cannot add to or remove the book from middle of the stack.
Book can only be added to the top and the only book that can be taken out of the stack is the most recently added one; Thus stack is a "Last In First Out" (LIFO) data structure.
An ADT is a collection of data and associated operations for manipulating that data. Stack ADT contains following data members
and member functions.
Data members: 1. top: Index of top of stack.
2. A[size]: Array to hold elements of stack:
Member Functions:
Operations on stack | Significance |
stack()
| Constructor to create an empty stack |
~stack()
| Destructor to destroy an existing stack
|
isEmpty() | Determines whether the stack is empty. It returns true if stack is empty, and false otherwise
|
isFull()
| Determines whether the stack is full. It returns true if stack is full, and false otherwise
|
push()
| Add an element to the top of the stack. PRECONDITION: stack cannot be full.
|
pop()
| Remove the element that is on the top of stack. PRECONDITION: stack cannot be empty.
|
peek()
| Function to return the element on top of stack without modifying the stack. PRECONDITION: stack cannot be empty.
|
stackcount() | Function to return total number of elements currently in stack. |
There are three fundamental operations on stack.
Push: Insert element to the stack
Pop: Delete element from stack
Peek: Returns element at the top of stack
We will see these operations with respect to an example.
Here we assume stack size is 3.
Initially stack is empty. If pop operation is called on empty stack then stack underflow occurs.
----- (empty stack)
Push element ‘7’ to the stack. Then stack becomes
| 7 | <-- top
-----
Push element ‘2’ to the stack. So new top of stack is 2.
| 2 | <-- top
| 7 |
-----
Push element ‘10’ to the stack. Now top of stack becomes 10.
|10 | <-- top
| 2 |
| 7 |
-----
Now the stack becomes full as we are assuming stack size is 3. If we insert one more element onto stack then stack overflow occurs.
Pop element from stack. Element 10 is popped out. Hence new top is 2.
| 2 | <-- top
| 7 |
-----
Since Stack is LIFO data structure element inserted most recently will be popped out first.
Pop element 2 from stack. Hence new top is 7.
| 7 | <-- top
-----
Pop element 7 from stack. Now stack becomes empty.
----- (empty stack)
Array implementation of stack is efficient if we know maximum size of stack.
Our stack must be able to store any type of data i.e.int, char, float or any other primitive data type.
Stack which is used to hold integer values must be able to hold float and character values.
For this we will not explicitly recode specific version of stack for each data type.
C++ provides this feature through class templates. Thus we implement stack ADT in C++ using class templates.
When we create class template, it can perform operations on any type of data.
The compiler will automatically generate correct type of object, depending on the type we specify when object is created.
Thus a stack ADT can be written as follows.
First we create node structure template.
template<class TYPE>
struct Node
{
Type value;
};
template<class TYPE> // class template
class stack
{
private:
Node<TYPE> *P; // pointer to structure
int count; // total no. of elements present in stack
int max; // total no. of elements allowed in stack
int top; // index of top of stack
public:
stack(int size=100); // constructor to create a stack
~stack(); // destructor to destroy stack
bool push(TYPE in); // function to insert element in stack
bool pop(TYPE &out); // function to delete element in stack
bool peek(TYPE& out); //return top element of stack
bool isempty(); //check if stack is empty
bool isfull(); //check if stack is full
int stackcount();// returns no. of elements currently in stack
};
Now we will see algorithms for these operations on stack in detail.
Create stack: stack()
Stack is created using constructor.
Steps
| Algorithm: stack(int size) | Description |
1 | template<class TYPE> stack<TYPE>::stack(int size) {
| Design constructor which takes stack size as an argument |
2 | max=size;
| Assign size to max. Value of size can be passed or default size of 100 is assumed. |
3 | P=new Node<TYPE>[max]; | allocate memory to P
|
4 | if(!P) { cout<<”Memory overflow”; abort(); }
| Check if memory is available. If memory is not available, abort and print “memory overflow “. |
5 | count=0; top=-1; }
| Initially stack is empty. So count is 0 and stack top is -1.
|
2. Insert element in Stack: push()
Steps
| Algorithm: bool push(TYPE in)
| Description |
1 | template<class TYPE> bool stack<TYPE>::push(TYPE in) {
| Design function push which inserts element ‘in’ to stack |
2 | if(count>=max) return false | Compare current total no. of elements with maximum stack size. If stack is full then return false to indicate element cannot be inserted. |
3 | P[top].value=in
| If stack is not full copy data to top of stack
|
4 | count++; top++; return true } | Increment count and top. Return true to indicate element is successfully inserted in stack. |
3.Remove element from stack: pop()
Steps
| Algorithm: bool pop(TYPE& out) | Description |
1 | template<class TYPE> bool stack<TYPE>::pop(TYPE& out) {
| Design function pop which deletes element on the top of stack. out is a reference variable to receive element to be popped out. |
2 | bool flag; if(count==0) flag=false; | If stack is empty then set flag to false |
3 | Else { out=P[top].value;
| If stack has elements, copy element at top of stack to variable out. |
4 | top--; count--; flag=true; }
| Decrement count and top. Set flag to true to indicate pop is successful. |
5 | return flag; } | Return flag |
4.Find top of stack(tos):peek
Steps
| Algorithm: bool peek(TYPE& out) | Description |
1 | template<class TYPE> bool stack<TYPE>::peek(TYPE& out) {
| Design function peek which returns element on the top of stack without modifying stack. out is a reference variable to receive element at the top of stack. |
2 | bool flag; if(count==0) flag=false; | If stack is empty then set flag to false |
3 | else { out=P[top].value;
| If stack has elements, copy element at top of stack to variable out. |
4 | flag=true; }
| Set flag to true. |
5 | return flag; } | Return flag |
5.Check if the stack is empty: isEmpty()
Steps
| Algorithm: bool isEmpty() | Description |
1 | template<class TYPE> bool stack<TYPE>::isEmpty() {
| Design function isEmpty() which returns true if stack is empty and false otherwise. |
2 | bool flag; if(count==0) flag=true; | If stack is empty then set flag to true |
3 | else flag=false;
| If stack has elements set flag to false. |
4 | return flag; } | Return flag |
6. Check if the stack is full: isFull()
Steps
| Algorithm: bool isFull() | Description |
1 | template<class TYPE> bool stack<TYPE>::isFull() {
| Design function isFull() which returns true if stack is full and false otherwise. |
2 | bool flag; if(count==max) flag=true; | Compare count with maximum number of elements allocated for a stack. If they are equal set flag to true. |
3 | else flag=false;
| If count is not equal to max set flag to false. |
4 | return flag; } | Return flag |
7.Find total number of elements in stack: stackcount()
Steps
| Algorithm: int stackcount() | Description |
1 | template<class TYPE> int stack<TYPE>::stackcount() {
| Design function stackcount() which returns total number of elements present in stack. |
2 | return count; } | ‘count’ specifies total number of elements present in stack so return count |
Destroy stack:~stack()
Stack is destroyed using destructor.
Steps
| Algorithm: ~stack() | Description |
1 | template<class TYPE> stack<TYPE>::~stack() {
| Design destructor to destroy stack |
2 | delete[] P P=NULL; count=0; max=0; top=-1; } | Release memory of P. Set variables count,max to 0 and top to -1. |
Program in C++ to perform various operations on stack .
#include<iostream.h>
# define int MAX 100
template< class TYPE > //class template
class Stack {
int count; //number of elements present in stack
TYPE A[Max]; // Array of size MAX
TYPE out;
int top; // index of top of stack
public:
Stack(int MAX);
~Stack();
bool push(TYPE);
TYPE pop();
bool isEmpty();
bool isFull();
int stackcount();
void display();
};
template< class TYPE > //constructor to create stack
Stack< TYPE >::Stack(int MAX)
{
count=0;
top = -1;
}
template< class TYPE > //destructor to remove stack
Stack< TYPE >::~Stack()
{ delete[] A;
count=0;
MAX=0;
top=-1;
}
template< class TYPE>// function to push elements in stack
void Stack< TYPE >::push(TYPE in)
{
if(count>=MAX)
cout<<”stack overflow”
count++;
top++;
A[ top ] = in; //copy data to top of stack
}
template< class TYPE > // Function to pop elements from stack
TYPE Stack< TYPE >::pop()
{ return A[ top-- ];
count--;
}
template< class TYPE> //Function to check if stack is full
int Stack< TYPE>::isFull()
{
return (count == Max);
}
template< class TYPE> //Function to check if stack is empty
int Stack< TYPE>::isEmpty()
{
return (count == 0);
}
template< class TYPE>
int Stack< TYPE>::stackcount()
{
return count;
}
template< class TYPE> //Function to display stack elements
void Stack<TYPE>::display()
{
if(top<0)
cout<<”stack empty”;
for(int i=top;i>=0;i--)
cout<<A[i]<<” ”;
}
void main()
{
int choice,data;
Stack<int> S; //create stack of integers
while(1)
{
cout<<”Enter choice for operation”;
cout<<”\t 1.PUSH”<<endl;
cout<<”\t 2.POP”<<endl;
cout<<”\t 3.ISFULL”<<endl;
cout<<”\t 4.ISEMPTY”<<endl;
cout<<”\t 5.Stackcount”<<endl;
cout<<”\t 6.Display”<<endl;
cin>>choice;
switch(choice)
{
case 1:
cout<<”Enter element to be pushed”;
cin>>data
S.push(data);
break;
case 2:
out=S.pop();
cout<<”Popped element is”<<out;
break;
case 3:
int flag=S.isFull();
if(flag=1)
cout<<”stack is full”;
else
cout<<”stack is not full”;
break;
case 4:
int flag=S.isEmpty();
if(flag=1)
cout<<”stack is empty”;
else
cout<<”stack is not empty”;
break;
case 5:int c=S.stackcount();
cout<<”Stack count is”<<c;
break;
case 6: S.display();
break;
} //end of switch
} //end of while
} //end of program
Data reversing is a technique of reordering data elements so that first element becomes last, second element becomes last but one and so on. Consider array A
10 | 5 | 2 | 4 | 9 |
A=
Fig. Original Array
After reversing array becomes
A=
9 | 4 | 2 | 5 | 10 |
Algorithm to reverse list of integers is as follows.
Steps
| Algorithm(Reverse) | Description |
1 | Create Stack | Create an empty stack |
2 | Read number | Accept integer from user |
3
3.1 3.2 | Loop(!fullstack(stack)) { push(stack.number) Read number } | Accept integers from user to fill the stack till it is not full. |
4
4.1 4.2 | Loop(!emptystack(stack)) { pop(stack.out) print(out) } | Pop elements from stack till stack is not empty. Print popped element to user. |
Another application of reversing data is conversion of decimal number to binary number. Algorithm for conversion of decimal to binary number is as follows.
Steps
| Algorithm(DecimaltoBinary) | Description |
1 | Create Stack | Create an empty stack |
2 | Read decimal number | Accept decimal number from user |
3
3.1 3.2 3.3
3.3.1 | Loop(number>0) { d=number%2 flag=push(stack.d) if(flag==false) { Print stack overflow } number=number/2 } | Convert the number to binary and push to stack. When stack becomes full print “stack overflow.” |
4
4.1 4.2 | Loop(!emptystack(stack)) { pop(stack.d) print(d) } | Pop elements from stack till stack is not empty. Print popped element to user |
***Program to convert decimal number to binary number****
#include <iostream>
#include <stdio.h>
#include <conio.h>
using namespace std;
struct Node
{
int value;
Node *next;
}*top = NULL, *P = NULL, *temp = NULL;
int x;
void push(int P)
{
temp = new Node;
temp->value = P;
temp->next = NULL;
if (top == NULL)
{
top = temp;
}
else
{
temp->next = top;
top = temp;
}
}
int pop()
{
if (top == NULL)
{
cout<<"underflow\n";
}
else
{
P = top;
top = top->next;
x = P->value;
delete(P);
return(x);
}
}
void main()
{
int num, a;
cout<<"enter the decimal number\n";
cin>>num;
while (num > 0)
{
a = num % 2;
num = num / 2;
push(a);
}
P = top;
cout<<"resultant binary no:";
while(1)
{
if (top != NULL)
cout<<pop()<<"\t";
else
break;
}
getch();
}
Expression Evaluation
An expression can be represented in one of the following forms.
Infix: Infix expression has operator between operands. Eg. A + B
Prefix: Prefix expression has operator before operands. Eg. + A B
Postfix: Postfix expression has operator after operands. Eg. A B +
Evaluation of an Infix Expression:
Infix expressions are always evaluated from left to right. While evaluating it we must take care of operator precedence.
Following table shows priority of operators in C++.
Priority of operators in C++
According to above table – and ! have highest priority and logical OR has least priority. If an expression consists of operators with same priority(*,/,%)then evaluation is performed from left to right. If expression consists of parentheses then they are given top priority. Innermost parentheses are evaluated first.
Eg. Evaluate following infix expression
A / B – C + D * E. Given A=4,B=2,C=1,D=5,E=6
Considering above rules infix expression becomes.
((A / B) – C) + (D * E) Putting values in it
((4/2)-1)+(5*6)
(2-1)+(5*6)
1+30
31(Output)
Evaluation of prefix expression
Prefix expression has operator before operands. Prefix expression is always evaluated from right to left.
Eg. + 1 * 2 3
Evaluating from right to left, first operator we come across is ‘*’.so evaluate 2*3.so now expression becomes
+1 6
Again start evaluating from right to left. Next operator is +.
Add 1 and 6. So final output is 7.
Evaluation of prefix expression using Stack
Steps for Evaluation of prefix expression using Stack are as follows.
Accept prefix expression from user
Scan the expression from right to left
If token is an operand then push it in a stack.
If token is an operator then pop corresponding operands and perform operation.
Push result in stack.
Move to next token
Repeat steps 3 to 6 till the end of prefix expression.
Eg. -*+5 3 1 6
Prefix Input |
Stack |
Operand 1 |
Operand 2 |
Output |
Description |
-* 5 3 + 1 6
|
| - | - | - | Initially stack is empty. Evaluate expression from right to left. |
-* 5 3 + 1
|
| - | - | - | First token is an operand hence push operand 6 in stack |
-* 5 3 +
|
| - | - | - | Next token is again operand hence push operand 1 in stack |
-* 5 3 |
|
1 |
6 |
7 |
Next token is operator +, hence pop 1 and 6 and perform addition. Result is 7 .Push it in to stack
|
-* 5 |
| - | - | - | Next token is 3. Push it into stack.
|
-*
|
| - | - | - | Next token is 5. Push it into stack.
|
- |
| 5 | 3 | 15 | Next token is operator *, hence pop 5 and 3 and perform multiplication. Result is 15 .Push it in to stack
|
|
| 15 | 7 | 8 | Next token is operator -, hence pop 15 and 7 and perform subtraction. Result is 8 .Push it in to stack
|
Eg. 2: Evaluate the following prefix expression using stack for A= 16, B= 2, C=3, D=10, and E=4.Prefix Expression is
-+/A^BC*DE*AC DEC2007
Prefix Input |
Stack |
Op 1 |
Op 2 |
Output |
Description |
-+/A^BC*DE*AC |
| - | - | - | Initially stack is empty. Evaluate expression from right to left. |
-+/A^BC*DE*A
|
| - | - | - | First token is an operand C hence push operand 3 in stack
|
-+/A^BC*DE* |
| - | - | - | Next token is an operand A hence push operand 16 in stack |
-+/A^BC*DE |
|
16 |
3 |
48 |
Next token is operator *, hence pop 3 and 16 and perform multipliaction. Result is 48 .Push it in to stack
|
-+/A^BC*D |
| - | - | - | Next token is E. Push it into stack.
|
-+/A^BC* |
| - | - | - | Next token is D. Push it into stack.
|
-+/A^BC |
| 10 | 4 | 40 | Next token is operator *, hence pop 4 and 10 and perform multiplication. Result is 40 .Push it in to stack
|
-+/A^B |
| - | - | - |
Next token is C. Push it into stack
|
-+/A^ |
| - | - | - |
Next token is B. Push it into stack
|
-+/A
|
| 2 | 3 | 8 | Next token is operator ^, hence pop 2 and 3 and perform ^. Result is 8 .Push it into stack.
|
-+/
|
| - | - | - | Next token is A. Push it into stack
|
-+ |
| 16 | 8 | 2 | Next token is operator /, hence pop 16 and 8 and perform /. Result of 16/8 is 2 .Push it into stack.
|
- |
| 2 | 40 | 42 | Next token is operator +, hence pop 40 and 2 and perform +. Result of 40+2 is 42 .Push it into stack. |
|
|
42 |
48 |
-6 |
Next token is operator -, hence pop 42 and 48 and perform - . Result of 42-48 is -6 .Push it into stack. |
Hence final result is -6.
*****program for prefix expression evaluation.***
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
template <class TYPE> //class template
class stack
{
private:
TYPE *a;
int top,max;
public:
stack()
{
max = 50;
a = new TYPE[max];
top = 0;
}
stack(int n)
{
max = n + 1;
a = new TYPE[max];
top= 0;
}
~stack()
{
delete a;
}
friend void push(stack &,TYPE); // member functions for stack
friend TYPE pop(stack &);
friend int isEmpty(stack);
};
template <class TYPE>
void push(stack <TYPE> &s, TYPE x)
{
if(s.top != s.max)
{
s.top++;
s.a[s.top] = x;
}
else
cout << "\nStack Overflow.";
}
template <class TYPE>
TYPE pop(stack <TYPE> &s)
{
TYPE temp;
if(s.top != 0)
{
temp = s.a[s.top];
s.top--;
return temp;
}
else
{
temp = -999;
return temp;
}
}
template <class TYPE>
int isEmpty(stack <TYPE> s)
{
if(s.top == 0)
return 1;
else
return 0;
}
int main()
{
char prefix[30],b[2];
int i = 0;
float e;
cout << "Enter a Prefix Expression,\n";
prefix[i - 1] ='\0';
while(prefix[i-1] != '\n')
prefix[i++] = getchar(); // prefix expression
stack <float> O(50); //call constructor to create stack
float value,operand1,operand2;
int j = i - 2,pos,k;
while(j >= 0)
{
pos = 0;
if(prefix[j] >= '0' && prefix[j] <= '9')
{
b[0] = prefix[j]; // Save Prefix[j] to b
i = j - 1;
k = 1;
if(prefix[j-1] != ' ') //Check for next character, If not Space
{
while(prefix[i] != ' ') //While space is not found
{
b[k++] = prefix[i--]; //Save Prefix[i] to b
pos++; //Increase Position
}
pos += 2;//At Last Increase Position by 2 to Skip Space
}
else //If a Single Character
pos = 2; //Skip Space
b[k] = '\0'; //End String temp
strrev(b);
x = atof(b); //Convert string b to float and store to x
push(O,x); //Push to stack
}
else if(prefix[j] == '+' || prefix[j] == '-' || prefix[j] == '*' || prefix[j] == '/' || prefix[j] == '^' ) // check for operators
{
operand1 = pop(O);
if(operand1 == -999)
break;
if(prefix[j] == '+' || prefix[j] == '-' || prefix[j] == '*' || prefix[j] == '/' || prefix[j] == '^')
{
operand2 = pop(O);
if(operand2 == -999)
break;
}
if(prefix[j] == '+')
value = operand1 + operand2;
if(prefix[j] == '-')
value = operand1 - operand2;
if(prefix[j] == '*')
value = operand1 * operand2;
if(prefix[j] == '/')
{
if(operand2 != 0)
value = operand1 / float(operand2); //Cast one operand to float
else
{
cout << "\nError ! Cannot Divide by Zero";
getch();
return 0;
}
}
if(prefix[j] == '^')
value = pow(operand1,operand2);
push(O,value);
pos = 2;
}
else
{
cout << "\nError : Illegal Character";
getch();
return 0;
}
j -= pos;
}
float output = pop(O);
if(output == -999 || !isEmpty(O)) //If Underflow Condition or stack is not empty,
{
cout << "\nError : The Given Prefix Expression is Not Valid.";
getch();
return 0;
}
else
cout << "\nOutput = " << Output;
getch();
return 0;
}
Evaluation of Postfix expression
Postfix expression has operator after operands. Postfix expression is evaluated from left to right.
Eg.6 4 2 * +
Evaluating from left to right first operator we come across is ‘*’.so evaluate 4*2.so now expression becomes
6 8 +. Again start evaluating from left to right. Next operator is +. Add 6 and 8. So final output is 14.
Evaluation of postfix expression using Stack
Steps for Evaluation of postfix expression using Stack are as follows.
Accept postfix expression from user
Scan the expression from left to right
If token is an operand then push it in a stack.
If token is an operator then pop corresponding operands and perform operation.
Store result in stack.
Move to next token
Repeat steps 3 to 6 till the end of postfix expression.
Eg. : 623+-382/+*2^3+
Postfix Input
| Stack | Op1 | Op2 | Output | Description |
623+-382/+*2^3+
|
| - | - | - | Initially stack is empty. Evaluate expression from left to right. |
23+-382/+*2^3+
|
| - | - | - | First token is an operand 6. Push it into stack. |
3+-382/+*2^3+
|
| - | - | - | Next token is an operand 2. Push it into stack.
|
+-382/+*2^3+ |
| - | - | - | Next token is an operand 3. Push it into stack.
|
-382/+*2^3+
|
| 2 | 3 | 5 | Next token is operator +, hence pop 2 and 3 and perform +. Result of 2+3 is 5 .Push it into stack. |
382/+*2^3+
|
| 6 | 5 | 1 | Next token is operator -, hence pop 5 and 6 and perform -. Result of 6-5 is 1 .Push it into stack.
|
82/+*2^3+
|
| - | - | - | Next token is an operand 3. Push it into stack.
|
2/+*2^3+
|
| - | - | - | Next token is an operand 8. Push it into stack.
|
/+*2^3+
|
| - | - | - |
Next token is an operand 2. Push it into stack.
|
+*2^3+
|
| 8 | 2 | 4 | Next token is operator /, hence pop 2 and 8 and perform /. Result of 8/2 is 4 .Push it into stack.
|
*2^3+
|
| 3 | 4 | 7 | Next token is operator +, hence pop 4 and 3 and perform +. Result of 3+4 is 7 .Push it into stack.
|
2^3+
|
| 1 | 7 | 7 | Next token is operator *, hence pop 7 and 1 and perform *. Result of 1*7 is 7 .Push it into stack.
|
^3+ |
| - | - | - | Next token is an operand 2. Push it into stack.
|
3+
|
| 7 | 2 | 49 | Next token is operator ^, hence pop 2 and 7 and perform ^. Result of 7^2 is 49 .Push it into stack.
|
+ |
| - | - | - | Next token is an operand 3. Push it into stack.
|
|
|
49
|
3 |
52 | Next token is operator +, hence pop 3 and 49 and perform +. Result of 49+3 is 52 .Push it into stack.
|
Hence final result is 52.
Eg.2: Evaluate the following postfix expression and show stack after every step in tabular form. Given A= 5, B= 6, C=2, D=12, and E=4.POSTfix Expression is
ABC+*DE\- MAY2007
Postfix Input
| stack | Op1 | Op2 | Output | Description |
ABC+*DE\- |
| - | - | - | Initially stack is Empty. Evaluate expression from left to right. |
BC+*DE\- |
| - | - | - | First token is an operand A i.e.5. Push it into stack.
|
C+*DE\- |
| - | - | - | Next token is an operand B i.e.6. Push it into stack.
|
+*DE\-
|
| - | - | - | Next token is an operand C i.e.2. Push it into stack.
|
*DE\-
|
| 6 | 2 | 8 | Next token is operator +, hence pop 2 and 6 and perform +. Result of 6+2 is 8 .Push it into stack.
|
DE\- |
| 5 | 8 | 40 | Next token is operator *, hence pop 8 and 5 and perform *. Result of 8*5 is 40 .Push it into stack.
|
E\-
|
| - | - | - | Next token is an operand D i.e.12. Push it into stack.
|
\-
|
| - | - | - | Next token is an operand E i.e.4. Push it into stack.
|
- |
| 12 | 4 | 3 | Next token is operator \, hence pop 4 and 12 and perform \. Result of 12\4 is 3 .Push it into stack.
|
|
| 40 | 3 | 37 | Next token is operator -, hence pop 3 and 40 and perform -. Result of 40-3 is 37 .Push it into stack.
|
Hence final output is 37.
*******Program to evaluate Postfix expression********
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
# define int MAX = 50 ;
class stack
{
private :
int A[MAX] ;
int top, y ;
char *s ;
public :
stack( ) ;
void exprn ( char *str ) ;
void push ( int x ) ;
int pop( ) ;
void calculate( ) ;
void display( ) ;
} ;
stack :: stack( )
{
top = -1 ;
}
void stack :: exprn ( char *str )
{
s = str ;
}
void stack :: push ( int x )
{
if ( top == MAX - 1 )
cout << endl << "Stack is full" ;
else
{
top++ ;
A[top] = x ;
}
}
int stack :: pop( )
{
if ( top == -1 )
{
cout << endl << "Stack is empty" ;
return NULL ;
}
int data = A[top] ;
top-- ;
return data ;
}
void stack :: calculate( )
{
int n1, n2, n3 ;
while ( *s )
{
if ( *s == ' ' || *s == '\t' )
{
s++ ;
continue ;
}
if ( isdigit ( *s ) )
{
y = *s - '0' ;
push ( y ) ;
}
else
{
n1 = pop( ) ;
n2 = pop( ) ;
switch ( *s )
{
case '+' :
n3 = n2 + n1 ;
break ;
case '-' :
n3 = n2 - n1 ;
break ;
case '/' :
n3 = n2 / n1 ;
break ;
case '*' :
n3 = n2 * n1 ;
break ;
case '%' :
n3 = n2 % n1 ;
break ;
case '^' :
n3 = pow ( n2 , n1 ) ;
break ;
default :
cout << "Unknown operator" ;
exit ( 1 ) ;
}
push ( n3 ) ;
}
s++ ;
}
}
void stack :: display( )
{
y = pop ( ) ;
cout << "Result is: " << y ;
}
void main( )
{
char C[MAX] ;
cout << "\nEnter postfix expression to be evaluated : " ;
cin.getline ( C, MAX ) ;
stack o ;
o.exprn ( C ) ;
o.calculate( ) ;
o.display( ) ;
}
Expression conversion is of following types
Infix to Postfix
Infix to Prefix
Postfix to Infix
Postfix to prefix
Prefix to Infix
Prefix to Postfix
Infix to Postfix
Manual Transformation
Infix expression can be manually converted to postfix in following steps.
Fully parenthesize the infix expression considering operator precedence. There should be one set of parentheses for each operator.
Evaluate innermost expression first. Replace right parenthesis with corresponding operator.
Remove left parentheses.
Eg. X+Y/Z
Step 1: (X+(Y/Z))
Step 2: (X+(YZ/)
(X(YZ/+
Step 3: XYZ/+
Stack Transformation
Infix expression can be converted to postfix using stack in following steps.
Initialize an empty stack.
While not to end of infix expression
Scan the expression from left to right.
Get the input token in the infix expression.
If the token is
A left parenthesis then push it onto the stack
A right parenthesis then Pop and display stack elements until a left parenthesis is encountered.
Note: Do not display parenthesis. Parenthesis has least priority in stack but highest priority when in input expression.
An operator: If the stack is empty or input token has higher priority than the top stack, push onto the stack. Otherwise, pop and display the top stack element. Repeat the comparison of input token with the new top stack element.
An operand: Just display it.
When end of infix expression is reached, pop and display stack elements until the stack is empty.
Eg1. 4+5*9/1
Infix | Stack | Postfix | Description |
4+5*9/1 |
|
| Initially stack is empty. scan expression from left to right. |
+5*9/1 |
| 4
| First token is an operand 4 so add to postfix expression. |
5*9/1 |
| 4 | Next token is operator + and stack is empty so push it into stack |
*9/1
|
| 45 | Next token is an operand 5 so add to postfix expression.
|
9/1
|
| 45 | Next token is operator *.Compare * with +. * has higher precedence over + so push it to stack. |
/1 |
| 459 | Next token is an operand 9 so add to postfix expression.
|
1 |
| 459* | Next token is operator /.Compare / with *. * has higher precedence over / so pop it from stack and push /.
|
|
| 459*1 | Next token is an operand 1 so add to postfix expression. |
|
| 459*1/+ | Pop remaining tokens from stack and add to postfix expression |
Hence Postfix expression is 459*1/+
Eg.2 Convert (2+4)*(5-6)/((1-2)*(9+2)) to Postfix expression.
Infix | stack | Postfix |
(2+4)*(5-6)/((1-2)*(9+2)) |
|
|
2+4)*(5-6)/((1-2)*(9+2)) | ( |
|
+4)*(5-6)/((1-2)*(9+2)) | ( | 2 |
)*(5-6)/((1-2)*(9+2)) | (+ | 24 |
*(5-6)/((1-2)*(9+2)) |
| 24+ |
(5-6)/((1-2)*(9+2)) | * | 24+ |
5-6)/((1-2)*(9+2)) | *( | 24+ |
-6)/((1-2)*(9+2)) | *( | 24+5 |
6)/((1-2)*(9+2)) | *(- | 24+5 |
)/((1-2)*(9+2)) | *(- | 24+56 |
/((1-2)*(9+2)) | * | 24+56- |
((1-2)*(9+2)) | / | 24+56-* |
(1-2)*(9+2)) | /( | 24+56-* |
1-2)*(9+2)) | /(( | 24+56-* |
-2)*(9+2)) | /(( | 24+56-*1 |
2)*(9+2)) | /((- | 24+56-*1 |
)*(9+2)) | /((- | 24+56-*12 |
*(9+2)) | /( | 24+56-*12- |
(9+2)) | /(* | 24+56-*12- |
9+2)) | /(*( | 24+56-*12- |
+2)) | /(*( | 24+56-*12-9 |
2)) | /(*(+ | 24+56-*12-9 |
)) | /(*(+ | 24+56-*12-92 |
) | /(* | 24+56-*12-92+ |
| / | 24+56-*12-92+* |
|
| 24+56-*12-92+*/ |
Eg.3:Convert the following arithmetic expression into postfix
A+(B*C-(D/E-F)*G)*H MAY 2007
Infix | stack | Postfix |
A+(B*C-(D/E-F)*G)*H
|
|
|
+(B*C-(D/E-F)*G)*H |
| A |
(B*C-(D/E-F)*G)*H | + | A |
B*C-(D/E-F)*G)*H | +( | A |
*C-(D/E-F)*G)*H | +( | AB |
C-(D/E-F)*G)*H | +(* | AB |
-(D/E-F)*G)*H | +(* | ABC |
(D/E-F)*G)*H | +(- | ABC* |
D/E-F)*G)*H | +(-( | ABC* |
/E-F)*G)*H | +(-( | ABC*D |
E-F)*G)*H | +(-(/ | ABC*D |
-F)*G)*H | +(-(/ | ABC*DE |
F)*G)*H | +(-(- | ABC*DE/ |
)*G)*H | +(-(- | ABC*DE/F |
*G)*H | +(- | ABC*DE/F- |
G)*H | +(-* | ABC*DE/F- |
)*H | +(-* | ABC*DE/F-G |
*H | + | ABC*DE/F-G*- |
H | +* | ABC*DE/F-G*-H |
| +* | ABC*DE/F-G*-H |
|
| ABC*DE/F-G*-H*+ |
EG. Convert the following expression into postfix.
(A+B)*D+E/(F+A*D)+C
A*(B+C)/D-G MAY 2008
1. (A+B)*D+E/(F+A*D)+C
Infix | stack | Postfix |
(A+B)*D+E/(F+A*D)+C
|
|
|
A+B)*D+E/(F+A*D)+C | ( |
|
+B)*D+E/(F+A*D)+C | ( | A |
B)*D+E/(F+A*D)+C | (+ | A |
)*D+E/(F+A*D)+C | (+ | AB |
*D+E/(F+A*D)+C |
| AB+ |
D+E/(F+A*D)+C | * | AB+ |
+E/(F+A*D)+C | * | AB+D |
E/(F+A*D)+C | + | AB+D* |
/(F+A*D)+C | + | AB+D*E |
(F+A*D)+C | +/ | AB+D*E |
F+A*D)+C | +/( | AB+D*E |
+A*D)+C | +/( | AB+D*EF |
A*D)+C | +/(+ | AB+D*EF |
*D)+C | +/(+ | AB+D*EFA |
D)+C | +/(+* | AB+D*EFA |
)+C | +/(+* | AB+D*EFAD |
+C | +/ | AB+D*EFAD*+ |
C | + | AB+D*EFAD*+/+ |
| + | AB+D*EFAD*+/+C |
|
| AB+D*EFAD*+/+C+ |
2. A*(B+C)/D-G
Infix | stack | Postfix |
A*(B+C)/D-G |
|
|
*(B+C)/D-G |
| A |
(B+C)/D-G | * | A |
B+C)/D-G | *( | A |
+C)/D-G | *( | AB |
C)/D-G | *(+ | AB |
)/D-G | *(+ | ABC |
/D-G | * | ABC+ |
D-G | / | ABC+* |
-G | / | ABC+*D |
G | - | ABC+*D/ |
| - | ABC+*D/G |
|
| ABC+*D/G- |
Hence postfix expression is ABC+*D/G-
*********PROGRAM FOR INFIX TO POSTFIX****************
#include <iostream.h>
#include <string.h>
#include <ctype.h>
#define int MAX = 50 ;
class stack
{
private :
char S[MAX], A[MAX] ;
char *s, *t ;
int top ;
public :
stack( ) ;
void exprn ( char *str ) ;
void push ( char c ) ;
char pop( ) ;
void convert( ) ;
int priority ( char c ) ;
void display( ) ;
} ;
stack :: stack( )
{
top = -1 ;
strcpy ( S, "" ) ;
strcpy ( A, "" ) ;
t = S ;
s = "" ;
}
void stack :: exprn ( char *str )
{
s = str ;
}
void stack :: push ( char c )
{
if ( top == MAX )
cout << "\nStack is full\n" ;
else
{
top++ ;
A[top] = c ;
}
}
char stack :: pop( )
{
if ( top == -1 )
{
cout << "\nStack is empty\n" ;
return -1 ;
}
else
{
char x = A[top] ;
top-- ;
return x ;
}
}
void stack :: convert( )
{
while ( *s )
{
if ( *s == ' ' || *s == '\t' )
{
s++ ;
continue ;
}
if ( isdigit ( *s ) || isalpha ( *s ) )
{
while ( isdigit ( *s ) || isalpha ( *s ) )
{
*t = *s ;
s++ ;
t++ ;
}
}
if ( *s == '(' )
{
push ( *s ) ;
s++ ;
}
char opr ;
if ( *s == '*' || *s == '+' || *s == '/' || *s == '%' || *s == '-' || *s == '^' )
{
if ( top != -1 )
{
opr = pop( ) ;
while ( priority ( opr ) >= priority ( *s ) )
{
*t = opr ;
t++ ;
opr = pop( ) ;
}
push ( opr ) ;
push ( *s ) ;
}
else
push ( *s ) ;
s++ ;
}
if ( *s == ')' )
{
opr = pop( ) ;
while ( ( opr ) != '(' )
{
*t = opr ;
t++ ;
opr = pop( ) ;
}
s++ ;
}
}
while ( top != -1 )
{
char opr = pop( ) ;
*t = opr ;
t++ ;
}
*t = '\0' ;
}
int stack :: priority ( char c )
{
if ( c == '^' )
return 3 ;
if ( c == '*' || c == '/' || c == '%' )
return 2 ;
else
{
if ( c == '+' || c == '-' )
return 1 ;
else
return 0 ;
}
}
void stack :: display( )
{
cout << S ;
}
void main( )
{
char Y[MAX] ;
stack O ;
cout << "\nEnter an expression in infix form: " ;
cin.getline ( Y, MAX ) ;
O.exprn ( Y ) ;
O.convert( ) ;
cout << "\nThe postfix expression is: " ;
O.display( ) ;
}
Infix to Prefix
Manual Transformation
Infix expression can be manually converted to prefix in following steps.
Fully parenthesize the infix expression considering operator precedence. There should be one set of parentheses per operator.
Evaluate innermost expression first. Replace left parenthesis with corresponding operator.
Remove right parentheses.
Eg. X+Y/Z
step 1 :(X+(Y/Z))
Step 2:(X+/YZ))
+X/YZ))
Step 3 :+X/YZ
Stack Transformation
Infix expression can be converted to prefix using stack in following steps.
Reverse the given infix expression.
Convert every opening bracket( into closing bracket ) and vice versa.
Convert the resultant expression into postfix form by following algorithm.
Initialize an empty stack.
While not to end of infix expression
Scan the expression from left to right.
Get the input token in the infix expression.
3.5 If the token is
a) A left parenthesis then push it onto the stack
b) A right parenthesis then Pop and display stack elements until a left parenthesis is encountered.
Note: Do not display parenthesis. Parenthesis has least priority in stack but highest priority when in input expression.
c) An operator: If the stack is empty or input token has higher priority than the top stack, push onto the stack. Otherwise, pop and display the top stack element. Repeat the comparison of input token with the new top stack element.
d) An operand: Just display it.
When end of infix expression is reached, pop and display stack elements until the stack is empty.
Reverse the resultant expression.
Eg. (A-(B/C))*((D*E)-F)
Step 1: Reverse the given expression
Original expression is (A-(B/C))*((D*E)-F) By reversing we get )F-)E*D((*))C/B(-A(
Step 2: Convert every opening bracket( into closing bracket ) and vice versa.
(F-(E*D))*((C/B)-A)
Step 3:Convert the resultant expression in postfix form
Infix | stack | Postfix |
(F-(E*D))*((C/B)-A) |
|
|
F-(E*D))*((C/B)-A) | ( |
|
-(E*D))*((C/B)-A) | ( | F |
(E*D))*((C/B)-A) | (- | F |
E*D))*((C/B)-A) | (-( | F |
*D))*((C/B)-A) | (-( | FE |
D))*((C/B)-A) | (-(* | FE |
))*((C/B)-A) | (-(* | FED |
)*((C/B)-A) | (- | FED* |
*((C/B)-A) |
| FED*- |
((C/B)-A) | * | FED*- |
(C/B)-A) | *( | FED*- |
C/B)-A) | *(( | FED*- |
/B)-A) | *(( | FED*-C |
B)-A) | *((/ | FED*-C |
)-A) | *((/ | FED*-CB |
-A) | *( | FED*-CB/ |
A) | *(- | FED*-CB/ |
) | *(- | FED*-CB/A |
| * | FED*-CB/A- |
|
| FED*-CB/A-* |
Step 4:Reverse the postfix expression
*-A/BC-*DEF
Hence the prefix expression is *-A/BC-*DEF
Eg.2 4*(2-(6*3+4)*2)+1
Step 1: Step 1: Reverse the given expression
Original expression is 4*(2-(6*3+4)*2)+1
By reversing we get 1+)2*)4+3*6(-2(*4
Step 2: Convert every opening bracket( into closing bracket ) and vice versa.
1+(2*(4+3*6)-2)*4
Step 3:Convert the resultant expression in postfix form
Infix | stack | Postfix |
1+(2*(4+3*6)-2)*4
|
|
|
+(2*(4+3*6)-2)*4 |
| 1 |
(2*(4+3*6)-2)*4 | + | 1 |
2*(4+3*6)-2)*4 | +( | 1 |
*(4+3*6)-2)*4 | +( | 12 |
(4+3*6)-2)*4 | +(* | 12 |
4+3*6)-2)*4 | +(*( | 12 |
+3*6)-2)*4 | +(*( | 124 |
3*6)-2)*4 | +(*(+ | 124 |
*6)-2)*4 | +(*(+ | 1243 |
)-2)*4 | +(*(+* | 1243 |
-2)*4 | +(*(+* | 12436 |
2)*4 | +(* | 12436*+ |
)*4 | +(- | 12436*+* |
*4 | +(- | 12436*+*2 |
4 | + | 12436*+*2- |
| +* | 12436*+*2- |
| +* | 12436*+*2-4 |
|
| 12436*+*2-4*+ |
Step 4:Reverse the postfix expression
+*4-2*+*63421
Hence the prefix expression is +*4-2*+*63421
***program to convert infix to prefix**************
#include <iostream.h>
#include <string.h>
#include <ctype.h>
#define int MAX = 50 ;
class stack
{
private :
char S[MAX], A[MAX] ;
char *s, *t ;
int top, len ;
public :
stack( ) ;
void exprn ( char *str ) ;
void push ( char c ) ;
char pop( ) ;
void convert( ) ;
int priority ( char c ) ;
void display( ) ;
} ;
stack :: stack( )
{
top = -1 ;
strcpy ( S, "" ) ;
strcpy ( A, "" ) ;
len = 0 ;
}
void stack:: exprn ( char *str )
{
s = str ;
strrev ( s ) ;
len = strlen ( s ) ;
* ( S + len ) = '\0' ;
t = S + ( len - 1 ) ;
}
void stack :: push ( char c )
{
if ( top == MAX - 1 )
cout << "\nStack is full\n" ;
else
{
top++ ;
A[top] = c ;
}
}
char stack :: pop( )
{
if ( top == -1 )
{
cout << "Stack is empty\n" ;
return -1 ;
}
else
{
char x = A[top] ;
top-- ;
return x ;
}
}
void stack:: convert( )
{
char opr ;
while ( *s )
{
if ( *s == ' ' || *s == '\t' )
{
s++ ;
continue ;
}
if ( isdigit ( *s ) || isalpha ( *s ) )
{
while ( isdigit ( *s ) || isalpha ( *s ) )
{
*t = *s ;
s++ ;
t-- ;
}
}
if ( *s == ')' )
{
push ( *s ) ;
s++ ;
}
if ( *s == '*' || *s == '+' || *s == '/' ||
*s == '%' || *s == '-' || *s == '^' )
{
if ( top != -1 )
{
opr = pop( ) ;
while ( priority ( opr ) > priority ( *s ) )
{
*t = opr ;
t-- ;
opr = pop( ) ;
}
push ( opr ) ;
push ( *s ) ;
}
else
push ( *s ) ;
s++ ;
}
if ( *s == '(' )
{
opr = pop( ) ;
while ( ( opr ) != ')' )
{
*t = opr ;
t-- ;
opr = pop ( ) ;
}
s++ ;
}
}
while ( top != -1 )
{
opr = pop( ) ;
*t = opr ;
t-- ;
}
t++ ;
}
int stack :: priority ( char c )
{
if ( c == '^' )
return 3 ;
if ( c == '*' || c == '/' || c == '%' )
return 2 ;
else
{
if ( c == '+' || c == '-' )
return 1 ;
else
return 0 ;
}
}
void stack :: display( )
{
while ( *t )
{
cout << " " << *t ;
t++ ;
}
}
void main( )
{
char C[MAX] ;
stack O ;
cout << "\nEnter an expression in infix form: " ;
cin.getline ( C, MAX ) ;
O.exprn( C ) ;
O.convert( ) ;
cout << "The Prefix expression is: " ;
O.display( ) ;
}
Postfix to Infix
Steps to convert postfix to infix are as follows
Scan the postfix expression from left to right.
If token is an operand push it into stack.
If token is an operator pop recent two operands. Form new subexpression with this operator and operands in infix form(operator between two operands).Place parentheses for subexpression to ensure proper order of evaluation in final expression.
Note: We place parenthesis only if it is required(operator in subexpression has lower precedence than operator used to merge two subexpressions ).Otherwise proper order of evaluation is maintained without any additional parentheses.
Push resulting subexpression in stack.
Move to next token.
Repeat steps 2 to 5 till the end of postfix expression.
Eg1.ab*cd*+e*
Postfix Expression | Stack | Description |
ab*cd*+e* | Empty | Initially stack is empty |
b*cd*+e* | A | First token is operand hence push it to stack. |
*cd*+e* | a, b | Next token is an operand. Push it into stack. |
cd*+e* | (a*b) | Next token is an operator ‘*’.Pop two recent operands(a,b) and form subexpression(a*b) in infix form. Place parentheses for Resultant subexpression(a*b).Push it into stack. |
d*+e* | (a*b), c | Next token is an operand c. Push it into stack |
*+e* | (a*b), c,d | Next token is an operand d. Push it into stack |
*+e* | (a*b), (c*d) | Next token is an operator ‘*’.Pop two recent operands(c,d) and form subexpression in infix form. Place parentheses for Resultant subexpression(c*d).Push it into stack. |
+e* | ((a*b)+ (c*d)) | Next token is an operator ‘+’.Pop two recent operands(a*b)and(c*d). Form subexpression in infix form. Place parentheses for Resultant subexpression((a*b)(c*d)).Push it into stack. |
e* | (a*b)+(c*d),e | Next token is an operand e. Push it into stack |
* | ((a*b)+(c*d))*e | Next token is an operator ‘*’.Pop two recent operands((a*b)+(c*d))and e. Form subexpression in infix form ((a*b)+(c*d))*e. Push it into stack. |
| ((a*b)+(c*d))*e |
|
Hence resultant infix expression is ((a*b)+(c*d))*e
Eg.2:Convert the following postfix expression to infix using stack.
abcde^^*- May 2006
Postfix Expression | Stack | Description |
abcde^^*- | Empty | Initially token is empty |
bcde^^*- | A | Next token is an operand a. Push it into stack. |
cde^^*- | a,b | Next token is an operand b. Push it into stack. |
de^^*- | a,b,c | Next token is an operand c. Push it into stack. |
e^^*- | a,b,c,d | Next token is an operand d. Push it into stack. |
^^*- | a,b,c,d,e | Next token is an operand e. Push it into stack. |
^*- | a,b,c,(d^e) | Next token is an operator ‘^’.Pop two recent operands(d)and(e). Form subexpression in infix form. Place parentheses for Resultant subexpression(d^e).Push it into stack. |
*- | a,b,c^(d^e) | Next token is an operator ‘^’.Pop two recent operands(c)and(d^e). Form subexpression in infix form. Push it into stack. |
- | a, b*c^(d^e) | Next token is an operator ‘*’.Pop two recent operands.Form subexpression in infix form. Push it into stack. |
| a-b*c^(d^e) | Next token is an operator ‘-’.Pop two recent operands. Form subexpression in infix form. Push it into stack. |
Hence resultant expression is a-b*c^(d^e)
Postfix to prefix
Postfix expression can be converted to prefix using following steps.
Scan the postfix expression from left to right.
If token is an operand push it into stack.
If token is an operator pop recent two operands. Form new subexpression with this operator and operands in prefix form(operator before two operands).
Push resulting subexpression in stack.
Move to next token.
Repeat step 2 to 5 till the end of postfix expression.
Eg.1: Convert the following postfix expression to prefix using stack.
abcde^^*- May 2006
Postfix Expression | Stack | Description |
abcde^^*- | Empty | Initially stack is empty |
bcde^^*- | A | Next token is an operand a. Push it into stack. |
cde^^*- | a,b | Next token is an operand b. Push it into stack. |
de^^*- | a,b,c | Next token is an operand c. Push it into stack. |
e^^*- | a,b,c,d | Next token is an operand d. Push it into stack. |
^^*- | a,b,c,d,e | Next token is an operand e. Push it into stack. |
^*- | a,b,c,^de | Next token is an operator ‘^’.Pop two recent operands(d)and(e). Form subexpression in prefix form. Push it into stack. |
*- | a,b,^c^de | Next token is an operator ‘^’.Pop two recent operands(c)and(^de). Form subexpression in prefix form. Push it into stack. |
- | a, *b^c^de | Next token is an operator ‘*’.Pop two recent operands.Form subexpression in prefix form. Push it into stack. |
| -a*b^c^de | Next token is an operator ‘-’.Pop two recent operands. Form subexpression in prefix form. Push it into stack. |
Hence resultant prefix expression is -a*b^c^de
Prefix to Infix
Steps to convert prefix to infix are as follows
Scan the prefix expression from right to left.
If token is an operand push it into stack.
If token is an operator pop recent two operands. Form new subexpression with this operator and operands in infix form(operator between two operands).Place parentheses for subexpression to ensure proper order of evaluation in final expression.
Note: We place parenthesis only if it is required(operator in subexpression has lower precedence than operator used to merge two subexpressions ).Otherwise proper order of evaluation is maintained without any additional parentheses.
Push resulting subexpression in stack.
Move to next token.
Repeat step 2 to 5 till the end of prefix expression.
Eg1. +/+AB-CDE
prefix Expression | Stack | Description |
+/+AB-CDE | Empty | Initially stack is empty |
+/+AB-CD | E | Next token is an operand E. Push it into stack. |
+/+AB-C | E,D | Next token is an operand D. Push it into stack. |
+/+AB- | E,D,C | Next token is an operand C. Push it into stack. |
+/+AB | E,(C-D) | Next token is an operator ‘-’.Pop two recent operands(C)and(D). Form subexpression in infix form. Push it into stack. |
+/+A | E,(C-D),B | Next token is an operand B. Push it into stack. |
+/+ | E,(C-D),B,A | Next token is an operand A. Push it into stack. |
+/ | E,(C-D),(A+B) | Next token is an operator ‘+’.Pop two recent operands(A)and(B). Form subexpression in infix form. Push it into stack. |
+ | E,(A+B)/(C-D) | Next token is an operator ‘/’.Pop two recent operands(A+B)and(C+D). Form subexpression in infix form. Push it into stack. |
| (A+B)/(C-D)+E | Next token is an operator ‘+’.Pop two recent operands(A+B)/(C-D) and E. Form subexpression in infix form. Push it into stack. |
Hence resultant infix expression is (A+B)/(C-D)+E
2.5.2.6 Prefix to Postfix
Steps to convert prefix to postfix are as follows
Scan the prefix expression from right to left.
If token is an operand push it into stack.
If token is an operator pop recent two operands. Form new subexpression with this operator and operands in postfix form(operator after two operands).
Push resulting subexpression in stack.
Move to next token.
Repeat step 2 to 5 till the end of prefix expression.
Eg1. +/+AB-CDE
prefix Expression | Stack | Description |
+/+AB-CDE | Empty | Initially stack is empty |
+/+AB-CD | E | Next token is an operand E. Push it into stack. |
+/+AB-C | E,D | Next token is an operand D. Push it into stack. |
+/+AB- | E,D,C | Next token is an operand C. Push it into stack. |
+/+AB | E,CD- | Next token is an operator ‘-’.Pop two recent operands(C)and(D). Form subexpression in postfix form. Push it into stack. |
+/+A | E,CD-,B | Next token is an operand B. Push it into stack. |
+/+ | E,CD-,B,A | Next token is an operand A. Push it into stack. |
+/ | E,CD-,AB+ | Next token is an operator ‘+’.Pop two recent operands(A)and(B). Form subexpression in postfix form. Push it into stack. |
+ | E,AB+/CD- | Next token is an operator ‘/’.Pop two recent operands(AB+)and(CD+). Form subexpression in postfix form. Push it into stack. |
| AB+/CD-E+ | Next token is an operator ‘+’.Pop two recent operandsAB+/CD- and E. Form subexpression in postfix form. Push it into stack. |
Hence resultant postfix expression is AB+/CD-E+
1. A queue can be defined as an ordered list which enables insert operations to be performed at one end called REAR and delete operations to be performed at another end called FRONT.
2. Queue is referred to be as First In First Out list.
3. For example, people waiting in line for a rail ticket form a queue.
Applications of Queue
Due to the fact that queue performs actions on first in first out basis which is quite fair for the ordering of actions. There are various applications of queues discussed as below.
Complexity
Data Structure | Time Complexity | Space Compleity | |||||||
| Average | Worst | Worst | ||||||
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion |
|
Queue | θ(n) | θ(n) | θ(1) | θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
Queue operations may involve initializing or defining the queue, utilizing it, and then completely erasing it from the memory. Here we shall try to understand the basic operations associated with queues −
Few more functions are required to make the above-mentioned queue operation efficient. These are −
In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing (or storing) data in the queue we take help of rear pointer.
Let's first learn about supportive functions of a queue −
peek()
This function helps to see the data at the front of the queue. The algorithm of peek() function is as follows −
Algorithm
begin procedure peek
return queue[front]
end procedure
Implementation of peek() function in C programming language −
Example
int peek() {
return queue[front];
}
isfull()
As we are using single dimension array to implement queue, we just check for the rear pointer to reach at MAXSIZE to determine that the queue is full. In case we maintain the queue in a circular linked-list, the algorithm will differ. Algorithm of isfull() function −
Algorithm
begin procedure isfull
if rear equals to MAXSIZE
return true
else
return false
endif
end procedure
Implementation of isfull() function in C programming language −
Example
bool isfull() {
if(rear == MAXSIZE - 1)
return true;
else
return false;
}
isempty()
Algorithm of isempty() function −
Algorithm
begin procedure isempty
if front is less than MIN OR front is greater than rear
return true
else
return false
endif
end procedure
If the value of front is less than MIN or 0, it tells that the queue is not yet initialized, hence empty.
Here's the C programming code −
Example
bool isempty() {
if(front < 0 || front > rear)
return true;
else
return false;
}
Enqueue Operation
Queues maintain two data pointers, front and rear. Therefore, its operations are comparatively difficult to implement than that of stacks.
The following steps should be taken to enqueue (insert) data into a queue −
Sometimes, we also check to see if a queue is initialized or not, to handle any unforeseen situations.
Algorithm for enqueue operation
procedure enqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure
Implementation of enqueue() in C programming language −
Example
int enqueue(int data)
if(isfull())
return 0;
rear = rear + 1;
queue[rear] = data;
return 1;
end procedure
Dequeue Operation
Accessing data from the queue is a process of two tasks − access the data where front is pointing and remove the data after access. The following steps are taken to perform dequeue operation −
Algorithm for dequeue operation
procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedure
Implementation of dequeue() in C programming language −
Example
int dequeue() {
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}
template <class TYPE>
struct Node //Node declaration
{
TYPE value; //data in a node
};
template <class TYPE> //class template for queue
class Queue
{
private:
Node<TYPE> * P; //pointer to node
int count;// number of elements present in queue
int max; // maximum queue size
int front; //index of element at front
int rear // index of element at rear
public:
Queue(int size=50);
~Queue();
bool enqueue(TYPE in);
bool dequeue(TYPE& out);
bool QFront(TYPE& out);
bool QRear(TYPE& out);
int QCount();
bool isEmpty();
bool isFull();
};
We will see array implementation for
1. Linear Queue
2. Circular Queue
Algorithms:
Create queue: Queue(int size)
Steps | Algorithm: Queue(int size) | Description
|
1 | template<class TYPE> Queue<TYPE>::Queue(int size) { | Design constructor to create a queue with initial capacity. |
2 | max=size; front=-1; rear=-1; count=0; | Initially queue is empty so set front and rear to -1 and count to zero. |
3 | P=new Node<TYPE>[max] | Allocate memory to node P |
4 | if(!P) { cout<<”Insufficient memory”; exit(1); } } |
If memory cannot be allocated then print memory is unavailable. |
We assume queue of size 5.Initially queue is empty. so
count=0
front=rear=-1
max=5
|
|
|
|
|
Data
Index 0 1 2 3 4
Enqueue: Insert element in queue
Steps | Algorithm: bool enqueue(TYPE in) | Description
|
1 | template<class TYPE> bool Queue<TYPE>::enqueue(TYPE in) { | Design function to insert element ‘in’ to queue. This function returns true if element is inserted successfully. |
2 | if(count==max) return false | If queue is full then return false to indicate element cannot be inserted. |
3 | rear++; | If queue is not full increment rear. |
5 | P[rear].value=in; | Insert data at rear |
6 | if(count==0) front=0 | if count is 0 it means queue is empty. Set front pointer to 0. |
7 | count++;
| Increment count |
8 | return true } | Return true to indicate successful insertion of an element in queue. |
Let us add element ’10’ to queue. After adding an element in queue
count =1
dequeue: Removes element from front of queue.
Steps | Algorithm: bool dequeue(TYPE& out) | Description
|
1 | template<class TYPE> bool Queue<TYPE>::dequeue(TYPE& out) { | Design function dequeue to remove element in queue. This function returns true if element is removed successfully. |
2 | if(count==0) return false | If count is 0 return false to indicate queue underflow. |
3 | out=P[front].value; | Pass data at front to reference parameter |
4 | front++; | Increment front |
6 | if(count==1) rear=front=-1; | if queue has only one element data set front and rear to -1. |
7 | count--;
| Decrement count |
8 | return true } | Return true to indicate successful removal of an element from queue. |
We continue with same example.
Now queue has only one element(20). Deleting it we get
count=0
front=rear=-1
QFront: Returns element at front of Queue.
Steps | Algorithm: bool QFront(TYPE& out) | Description
|
1 | template<class TYPE> bool Queue<TYPE>::QFront(TYPE& out) { | Design function QFront to find element at front . This function returns true if Queue front is found. |
2 | if(count==0) return false | if count is 0 it means queue is empty. So return false. |
3 | else { out=P[front].value; return true } } | if queue is not empty pass data at front of queue to calling function through reference parameter out. Return true to indicate success. |
QRear: Returns element at rear of Queue.
Steps | Algorithm: bool QRear(TYPE& out) | Description
|
1 | template<class TYPE> bool Queue<TYPE>::QRear(TYPE& out) { | Design function QRear to find element at rear . This function returns true if element at rear is found. |
2 | if(count==0) return false | if count is 0 it means queue is empty. So return false. |
3 | else { out=P[rear].value; return true } } | if queue is not empty pass data at rear of queue to calling function through reference parameter out. Return true to indicate success. |
isEmpty():Determines if queue is empty
Steps | Algorithm: bool isEmpty() | Description
|
1 | template<class TYPE> bool Queue<TYPE>::isEmpty() { | Design function isEmpty() to find if queue is empty. This function returns true if queue is empty and false otherwise. |
2 | if(count==0) return true; | if count is 0 it means queue is empty. So return true. |
3 | else return false; } | else return false to indicate queue is not empty. |
isFull():Determines if queue is full
Steps | Algorithm: bool isFull() | Description
|
1 | template<class TYPE> bool Queue<TYPE>::isFull() { | Design function isFull() to find if queue is full. This function returns true if queue is full and false otherwise. |
2 | if(count==max) return true; | If count equals max then return true to indicate queue is full. |
3 | else return false | else return false to indicate queue is not full |
QCount: Determines total number of elements present in queue. For this it simply returns the count in queue.
Steps | Algorithm: int QCount() | Description
|
1 | template<class TYPE> int Queue<TYPE>::QCount() { | Design function QCount() to return total number of elements in queue. |
2 | return count; } | return count . |
~Queue(): Destroy queue
Queue is destroyed using destructor.
Steps | Algorithm: ~Queue() | Description
|
1 | template<class TYPE> Queue<TYPE>::~Queue() { | Design destructor to destroy queue. |
| delete []P } } | Release array |
Write a Program to implement Linear Queue using array
#include<iostream>
#include<string>
#include<conio.h>
#include<process.h>
using namespace std;
template <class TYPE>
struct Node //Node declaration
{
TYPE value; //data in a node
};
class Queue
{
private:
Node<TYPE> * P; //
int count;// number of elements present in queue
int max; // maximum queue size
int front; //index of element at front
int rear // index of element at rear
public:
Queue(int size=50)
{ max = x;
front=-1;
rear=-1;
count=0
P = new TYPE[max];
}
~Queue();
bool enqueue(TYPE in);
bool dequeue(TYPE& out);
bool QFront(TYPE& out);
bool QRear(TYPE& out);
int QCount();
bool isEmpty();
bool isFull();
};
template <class TYPE>
bool Queue<TYPE>:: isEmpty()
{
return (count==0);
}
template <class TYPE>
bool Queue<TYPE>::isFull()
{
return (rear==(max-1));
}
template <class TYPE>
bool Queue<TYPE>:: enqueue(TYPE in)
{
if(isFull())
return false;
rear++;
P[rear].value=in;
return true;
if(count==0)
front=0;
count++;
return true;
}
template <class TYPE>
bool Queue<TYPE>::deQueue(TYPE & out)
{
if(isEmpty())
return false;
|
out=P[front].value;
|
front++; |
if(count==1) rear=front=-1; |
count--;
|
return true } |
template <class TYPE>
bool Queue<TYPE>::QFront(TYPE& out) { |
if(count==0) return false |
else { out=P[front].value; return true } } template <class TYPE> |
bool Queue<TYPE>::QRear(TYPE& out) { |
if(count==0) return false |
else { out=P[rear].value; return true } } |
int Queue<TYPE>::QCount() { |
return count; } |
template <class TYPE>
void Queue<TYPE>:: display()
{
for(int i=front;i<=rear;i++)
{
cout<<P[i]<<" <-- ";
}
cout<<endl;
}
}
void main(){
Queue<int> Q; //create queue of integers
int ch,x;
bool flag;
do{
cout<<"\nEnter your choice:\n1.enqueue\n2.dequeue\n3.queue front\
\n4.queue rear\n5.isfull\n6.isempty\n7.size\n8.display\n9.exit"<<endl;
cin>>ch;
switch(ch){
case 1:
cout<<”Enter element to be inserted”;
cin>>x;
flag=Q.enqueue(x)
if(flag==true)
cout<<"The queue is full"<<endl;
else
cout<<”element is inserted successfully ";
break;
case 2:
flag=Q.dequeue(x);
if(flag==true)
cout<< "element is dequeued"<<endl;
else
cout<<"queue is empty"<<endl;
break;
case 3:TYPE y;
flag=Q.QFront(y);
if(flag==true)
cout<<”Queue Front is”<<y<<endl;
else
cout<<"queue is empty"<<endl;
break;
case 4:TYPE z;
flag=Q.QRear(z);
if(flag==true)
cout<<”Queue Rear is” <<z<<endl;
else
cout<<"queue is empty"<<endl;
break;
case 5:
flag=Q.isFull();
if(flag==true)
cout<<Queue is full<<endl;
else
cout<<"queue is not full"<<endl;
break;
case 6:
flag=Q.isEmpty();
if(flag==true)
cout<<Queue is empty<<endl;
else
cout<<"queue is not empty"<<endl;
case 7:
int c=Q.QCount();
cout<<"size of queue is "<<c;
break;
case 8:
Q.display();
break;
case 9:exit(1);
}
}while(ch);
getch();
}
Limitation of Linear Queue:
Consider a linear queue of size 3.
Initially queue is empty.
So front,rear=-1
max=3
|
|
|
Data
Index 0 1 2
Consider trace of operations on this queue.
Here when we try to insert D, overflow occurs as rear=max-1. But actually queue is not full as first location of queue is empty. Thus here memory is not utilized efficiently.
A more suitable method of representing a queue will be circular queue where all the elements are arranged in circular fashion .In circular queue last element is logically followed by first element. Fig- shows circular queue.
In above circular queue index 0 and 1 are vacant so we can insert element at these positions when rear=max-1.
We do this by wrapping rear to first index position.
Hence now rear=0. Inserting element ‘7’we get
In this way memory can be utilized efficiently in circular queue.
2. Array implementation for Circular Queue
ALGORITHMS:
Queue():Create queue
Queue is created using constructor.
Steps | Algorithm: Queue(int size) | Description
|
1 | template<class TYPE> Queue<TYPE>::Queue(int size) { | Design constructor to create a queue with initial capacity. |
2 | max=size; front=-1; rear=-1; count=0; | Initially queue is empty so set front and rear to -1 and count to zero. |
3 | P=new Node<TYPE>[max] | Allocate memory to node P |
4 | if(!P) { cout<<”Insufficient memory”; exit(1); } } |
If memory cannot be allocated then print memory is unavailable. |
We assume queue of size 7.Intially Queue is empty. So
count=0
front=rear=-1;
Enqueue: Insert element in queue
Steps | Algorithm: bool enqueue(TYPE in) | Description
|
1 | template<class TYPE> bool Queue<TYPE>::enqueue(TYPE in) { | Design function to insert element ‘in’ to queue. This function returns true if element is inserted successfully. |
2 | if(count==max) return false | If queue is full then return false to indicate element cannot be inserted. |
3 | rear++; | If queue is not full increment rear. |
4 | if(rear==max-1) rear=0; | If rear is last element wrap to the first element of queue. |
5 | P[rear].value=in; | Insert data at rear |
6 | if(count==0) front=0 | if count is 0 it means queue is empty. Set front pointer to 0. |
7 | count++;
| Increment count |
8 | return true } | Return true to indicate successful insertion of an element in queue. |
Let us add element to circular queue. After adding an element’10’ in queue
count =1
front=rear=0
max=7
Add one more element ‘2’ to queue.
count=2
front=0
rear=1
dequeue: Removes element from front of queue.
Steps | Algorithm | Description
|
1 | template<class TYPE> bool Queue<TYPE>::dequeue(TYPE& out) { | Design function dequeue to remove element in queue. This function returns true if element is removed successfully. |
2 | if(count==0) return false | If count is 0 return false to indicate queue underflow. |
3 | out=P[front].value; | Pass element at front to reference parameter out |
4 | front++; | Increment front |
5 | if(front==max-1) front=0; | If front is last element wrap queue front to 0. |
6 | if(count==1) rear=front=-1; | if queue has only one element data set front and rear to -1. |
7 | count--;
| Decrement count |
8 | return true } | Return true to indicate successful removal of an element from queue. |
QFront: Returns element at front of Queue.
Steps | Algorithm | Description
|
1 | template<class TYPE> bool Queue<TYPE>::QFront(TYPE& out) { | Design function QFront to find element at front . This function returns true if Queue front is found. |
2 | if(count==0) return false | if count is 0 it means queue is empty. So return false. |
3 | else { out=P[front].value; return true } } | if queue is not empty pass data at front of queue to calling function through reference parameter out. Return true to indicate success. |
QRear: Returns element at rear of Queue.
Steps | Algorithm | Description
|
1 | template<class TYPE> bool Queue<TYPE>::QRear(TYPE& out) { | Design function QRear to find element at rear . This function returns true if element at rear is found. |
2 | if(count==0) return false | if count is 0 it means queue is empty. So return false. |
3 | else { out=P[rear].value; return true } } | if queue is not empty pass data at rear of queue to calling function through reference parameter out. Return true to indicate success. |
10.isEmpty():Determines if queue is empty
Steps | Algorithm | Description
|
1 | template<class TYPE> bool Queue<TYPE>::isEmpty() { | Design function isEmpty() to find if queue is empty. This function returns true if queue is empty and false otherwise. |
2 | if(count==0) return true; | if count is 0 it means queue is empty. So return true. |
3 | else return false; } | else return false to indicate queue is not empty. |
isFull():Determines if queue is full
Steps | Algorithm | Description
|
1 | template<class TYPE> bool Queue<TYPE>::isFull() { | Design function isFull() to find if queue is full. This function returns true if queue is full and false otherwise. |
2 | if(count==max) return true; | If count equals max then return true to indicate queue is full. |
3 | else return false | else return false to indicate queue is not full |
QCount: Determines total number of elements present in queue.
Steps | Algorithm | Description
|
1 | template<class TYPE> int Queue<TYPE>::QCount() { | Design function QCount() to return total number of elements in queue. |
2 | return count; } | return count . |
~Queue(): Destroy queue
Queue is destroyed using destructor.
Steps | Algorithm | Description
|
1 | template<class TYPE> Queue<TYPE>::~Queue() { | Design destructor to destroy queue. |
| delete []P } } | Release array |
****Program to implement circular queue using array****
#include<iostream>
#include<string>
#include<conio.h>
#include<process.h>
using namespace std;
template <class TYPE>
struct Node //Node declaration
{
TYPE value; //data in a node
};
class CQueue
{
private:
Node<TYPE> * P; //
int count;// number of elements present in queue
int max; // maximum queue size
int front; //index of element at front
int rear // index of element at rear
public:
CQueue(int size=50)
{ max = x;
front=-1;
rear=-1;
count=0
P = new TYPE[max];
}
~CQueue();
bool enqueue(TYPE in);
bool dequeue(TYPE& out);
bool CQFront(TYPE& out);
bool CQRear(TYPE& out);
int CQCount();
bool isEmpty();
bool isFull();
};
template <class TYPE>
bool CQueue<TYPE>:: isEmpty()
{
return (count==0);
}
template<class TYPE>
bool CQueue<TYPE>::isFull()
{
return (count==max));
}
template<class TYPE>
bool CQueue<TYPE>:: enqueue(TYPE in)
{
if(isFull())
return false;
rear++;
if(rear==max-1)
rear=0;
P[rear].value=in;
if(count==0)
front=0;
count++;
return true;
}
template<class TYPE>
bool CQueue<TYPE>::deQueue(TYPE & out)
{
if(isEmpty())
return false;
|
out=P[front].value; |
front++; |
if(count==1) rear=front=-1; |
count--;
|
return true } |
template<class TYPE>
bool CQueue<TYPE>::CQFront(TYPE& out) { |
if(count==0) return false |
else { out=P[front].value; return true } } template<class TYPE> |
bool CQueue<TYPE>::QRear(TYPE& out) { |
if(count==0) return false |
else { out=P[rear].value; return true } } template<class TYPE> |
int CQueue<TYPE>::QCount() { |
return count; }
|
template<class TYPE> |
void CQueue<TYPE>:: display()
{
for(int i=0;i<=(max-1);i++)
{
cout<<P[i]<<" <-- ";
}
cout<<endl;
}
}
void main(){
CQueue<int> CQ; //create circular queue of integers
int ch,x;
bool flag;
do{
cout<<"\nEnter your choice:\n1.enqueue\n2.dequeue\n3.queue front\
\n4.queue rear\n5.isfull\n6.isempty\n7.size\n8.display\n9.exit"<<endl;
cin>>ch;
switch(ch){
case 1:
cout<<”Enter element to be inserted”;
cin>>x;
flag=CQ.enqueue(x)
if(flag==false)
cout<<"The queue is full"<<endl;
else
cout<<”element is inserted successfully";
break;
case 2:TYPE y;
flag=CQ.dequeue(y);
if(flag==true)
cout<< y<<"element is dequeued"<<endl;
else
cout<<"queue is empty"<<endl;
break;
case 3:TYPE z;
flag=CQ.QFront(z);
if(flag==true)
cout<<Queue Front is <<z<<endl;
else
cout<<"queue is empty"<<endl;
break;
case 4:TYPE r;
flag=CQ.QRear(r);
if(flag==true)
cout<<Queue Rear is <<r<<endl;
else
cout<<"queue is empty"<<endl;
break;
case 5:
flag=CQ.isFull();
if(flag==true)
cout<<Queue is full<<endl;
else
cout<<"queue is not full"<<endl;
break;
case 6:
flag=CQ.isEmpty();
if(flag==true)
cout<<Queue is empty<<endl;
else
cout<<"queue is not empty"<<endl;
case 7:
int c=CQ.QCount();
cout<<"size of queue is "<<c;
break;
case 8:
CQ.display();
break;
case 9:exit(1);
}
}while(ch);
getch();
A Queue is a linear list in which data is inserted at one end called as rear and deleted from other end called as front. Queue removes elements in the same order in which they were inserted i.e. element inserted first is removed first. Hence they are called as First-in-First out( FIFO) data structure.
Imagine a queue of people waiting for a bus. The person in the front of queue will get a first chance to board a bus. The person at the rear will be last one to board a bus. Same case is of check out line in a grocery store or a cafeteria, list of jobs to be processed by computer or a list of calls on mobile phone.Fig.1 shows queue of alphabets. Alphabets are added at rear and removed from front end.
A front | B | C | D | E | F rear |
Fig 1. Queue of alphabets
We will see queue with respect to an example. Imagine queue of alphabets with size of three. Initially queue is empty.
front |
|
rear |
Now let us add an element in a queue. So queue becomes
Front |
| A rear |
Add one more element ’B’ in a queue. Since element can only be inserted at rear, A progresses through queue and B is inserted at rear. Now queue becomes
Front | A | B Rear |
Adding one more element ‘C’ in queue
A Front | B | C Rear |
Now queue is full. If we try to insert one more element in queue then queue overflow occurs.
Now remove elements from queue. Element in queue is always removed from front end. Currently ‘A’ is at front end and hence will be removed first.
B front | C |
Rear |
Removing ‘B’ and ‘C’ we get
front |
|
Rear |
Now queue is empty. If we try to remove elements from queue, queue underflow occurs.
Operations on Queue:
bool enqueue(TYPE in): Insert elements at rear of queue.
bool dequeue(TYPE & out): Remove elements from front of queue.
bool Front(TYPE& out): Determines element at the front of queue.
bool Rear(TYPE& in): Determines element at the rear of queue.
int Count():Determines total number of elements present in queue.
bool isEmpty():Determines if queue is empty.
bool isFull():Determines if queue is full.
A priority queue is an ADT where every element has a "priority" associated with it. This priority determines the order in which they exit the queue. The elements with highest priority are removed before elements with low priority. If two elements have the same priority, they are removed according to their order in the queue.
Consider the scenario of jobs sent to a printer. These jobs are usually placed in a queue, so job that is submitted first will be printed first. But every time this is not feasible as some of the jobs are more important though they are submitted later. So these important jobs should have precedence over other jobs which are submitted earlier. Such kind of application requires priority queue.
The common operations on priority queue are
insert: Inserts element in priority queue. It is similar to enqueue operation of Queue.
delete :finds and removes the element from priority queue. It is similar to dequeue operation of Queue. The element removed is of highest priority.
Array implementation of Priority Queue:
All the functions are same as that of normal queue except dequeue as here element is deleted according to priority. We will look at dequeue function.
Let us assume array Q[] of size n.
TYPE dequeue ()
{
int max = 0;
// finding the index of the element with the highest priority
for (int i=0; i<n-1; i++)
{
if (Q[i] > Q[max])
{
max = i;
}
}
TYPE maxnum = Q[max];
size--;
Q[max] = Queue[n];
return maxnum;
delete maxnum;
}
*******program for priority queue**********8
#include<iostream>
#include<conio.h>
#include<process.h>
using namespace std;
template <class TYPE>
struct Node //Node declaration
{
TYPE value; //data in a node
};
class Queue
{
private:
Node<TYPE> * P; //
int count;// number of elements present in queue
int max; // maximum queue size
int front; //index of element at front
int rear // index of element at rear
public:
Queue(int size=50)
{ max = x;
front=-1;
rear=-1;
count=0
P = new TYPE[max];
}
~Queue();
bool enqueue(TYPE in);
TYPE dequeue();
bool isEmpty();
bool isFull();
};
template <class TYPE>
bool Queue<TYPE>:: isEmpty()
{
return (count==0);
}
template <class TYPE>
bool Queue<TYPE>::isFull()
{
return (rear==(max-1));
}
template <class TYPE>
bool Queue<TYPE>:: enqueue(TYPE in)
{
if(isFull())
return false;
rear++;
P[rear].value=in;
return true;
if(count==0)
front=0;
count++;
return true;
}
template <class TYPE>
TYPE Queue<TYPE>::deQueue()
{
if(isEmpty())
cout<<”Queue is empty”;
int m = 0; { { return maxnum; delete maxnum;
|
|
|
|
|
} |
template <class TYPE>
void Queue<TYPE>:: display()
{
for(int i=front;i<=rear;i++)
{
cout<<P[i]<<" <-- ";
}
cout<<endl;
}
}
void main(){
Queue<int> Q; //create queue of integers
int ch;
int x,flag;
do{
cout<<"\nEnter your choice:\n1.enqueue\n2.dequeue\n3.isfull\n4.isempty\5.display\n6.exit"<<endl;
cin>>ch;
switch(ch){
case 1:
cout<<”Enter element to be inserted”;
cin>>x;
flag=Q.enqueue(x)
if(flag==0)
cout<<"The queue is full"<<endl;
else
cout<<”element is inserted ";
break;
case 2:
TYPE T;
T=Q.dequeue();
cout<<”Deleted element is”<<T;
break;
case 3:
flag=Q.isFull();
if(flag==1)
cout<<Queue is full<<endl;
else
cout<<"queue is not full"<<endl;
break;
case 4:
flag=Q.isEmpty();
if(flag==1)
cout<<Queue is empty<<endl;
else
cout<<"queue is not empty"<<endl;
case 5:
Q.display();
break;
case 6:exit(1);
}
}while(ch);
getch();
}
Queues can be used in any situation where we want to efficiently maintain a First-in-First out order. They are mostly used in simulations and operating systems. In a multitasking operating system, the CPU cannot run all jobs at once, so jobs must be batched up and then scheduled according to some policy. So Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.
Here we discuss two important applications of queues
A] Simulation
B] Categorizing data
A] Simulation
Queuing Simulation is a modeling activity which generates statistics for the performance of queues. It is used for analysis of distribution of various limited resources by a system to the entities being served. This kind of analysis is widely used in telecommunications, computer networks, call centers and predicting performance of real life systems.
B] Categorizing data
Categorizing data is rearranging data in various categories or groups without destroying their basic sequence. We can use queues to categorize data while maintaining their original order in each category. Thus queues are used to perform radix sort.
Consider the following series of numbers .
4 15 14 6 21 3 25 18 9 27
Let us categorize data in 3 groups.
G1: [1-10]
G2: [11-20]
G3: [21-30]
Here we are not performing sorting but rearranging data in groups according to above categories. Thus we have above series rearranged as follows
G1: [4 6 3 9]
G2: [15 14 18]
G3: [21 25 27]
Thus we have categorized data in 3 groups while maintaining their basic sequence in original list.
We will implement above scenario using Queue.
Consider linear queue Q with following elements in it.
4
| 15 | 14 | 6 | 21 | 3 | 25 | 18 | 9 | 27 |
We will design multiqueue Q which will store 3 queues Q1,Q2 and Q3 in it.
Q1: [4 6 3 9]
Q2: [15 14 18]
Q3: [21 25 27]
Now multiqueue Q becomes
4
| 6 | 3 | 9 | 15 | 14 | 18 | 21 | 25 | 27 |
Q1 Q2 Q3
In this way we can use Queues efficiently for categorizing data.
Reference Books:
1. E Balgurusamy, “Programming in ANSI C”, Tata McGraw-Hill, 3rd Edition.
2. Yedidyah Langsam, Moshe J Augenstein and Aaron M Tenenbaum “Data structures using C and C++” PHI Publications, 2nd Edition.
3. Reema Thareja, “Data Structures using C”, Oxford University Press, 2
nd Edition.
