Priority Queue

 The queue is a FIFO (First in first out) structure. In daily life, you have also seen that it is not true that a person, who comes first, leaves first from the queue. Let’s take the example of traffic. Traffic is stopped at the signal. The vehicles are in a queue. When the signal turns green, vehicles starts moving. The vehicles which are at the front of the queue will cross the crossing first. Suppose an ambulance comes from behind. Here ambulance should be given priority. It will bypass the queue and cross the intersection. Sometimes, we have queues that are not FIFO i.e. the person who comes first may not leave first. We can develop such queues in which the condition for leaving the queue is not to enter first. There may be some priority. Here we will also see the events of future like the customer is coming at what time and leaving at what time. We will arrange all these events and insert them in a priority queue. We will develop the queue in such a way that we will get the event which is going to happen first of all in the future. This data structure is known as priority queue. In a sense, FIFO is a special case of priority queue in which priority is given to the time of arrival. That means the person who comes first has the higher priority while the one who comes later, has the low priority. You will see the priority queue being used at many places especially in the operating systems. In operating systems, we have queue of different processes. If some process comes with higher priority, it will be processed first. Here we have seen a variation of queue. We will use the priority queue in the simulation. The events will be inserted in the queue and the event going to occur first in future, will be popped.

What are the requirements to develop this simulation? We need the C++ code for the simulation. There will be a need of the queue data structure and obviously, the priority queue. Information about the arrival of the customers will be placed in an input file. Each line of the file contains the items (arrival time, transaction duration).

Here are a few lines from the input file.

00 30 10 <- customer 1 00 35 05 <- customer 2 00 40 08 00 45 02 00 50 05 00 55 12 01 00 13 01 01 09

The first line shows the customer 1. “00 30 10” means Customer 1 arrives 30 minutes after the opening of the bank. He will need 10 minutes for his transaction. The last entry “01 01 09” means customer arrives one hour and one minute after the bank opened and his transaction will take 9 minutes and so on. The file contains similar information about the other customers. We will collect the events now. The first event to occur is the arrival of the first customer. This event is placed in the priority queue. Initially, the four teller queues are empty. The simulation proceeds as follows: when an arrival event is removed from the priority queue, a node representing the customer is placed on the shortest teller queue. Here we are trying to develop an algorithm while maintaining the events queue.

After the opening of the bank, the arrival of the first customer is the first event. When he enters the bank all the four tellers are free. Suppose he goes to the first teller and starts his transaction. After the conclusion of his transaction, he leaves the bank. With respect to events, we have only two events, one is at what time he enters the bank and other is at what time he leaves the bank. When other customers arrive, we have to maintain their events.

If the customer is the only one on a teller queue, an event for his departure is placed on the priority queue. At the same time, the next input line is read and an arrival event is placed in the priority queue. When a departure event is removed from the event priority queue, the customer node is removed from the teller queue. Here we are dealing with the events, not with the clock. When we come to know that a person is coming at say 9:20am, we make an event object and place it in the priority queue. Similarly if we know the time of leaving of the customer from the bank, we will make an event and insert it into the priority queue. When the next customer in the queue is served by the teller, a departure event is placed on the event priority queue. When the other customer arrives, we make an event object and insert it into the priority queue. Now the events are generated and inserted when the customer arrives. But the de-queue is not in the same fashion. When we de-queue, we will get the event which is going to occur first.

When a customer leaves the bank, the total time is computed. The total time spent by the customer is the time spent in the queue waiting and the time taken for the transaction. This time is added to the total time spent by all customers. At the end of the simulation, this total time divided by the total customers served will be average time consumed by customers. Suppose that 300 customers were served, then we will divide the total time by 300 to get the average time. So with the help of simulation technique, we will get the result that x customers came today and spent y time in the bank and the average time spent by a customer is z.

 Code of the Bank Simulation

Let’s have a look on the C+ code of this simulation.

#include <iostream> #include <string> #include <strstream.h> #include "Customer.cpp" #include "Queue.h" #include "PriorityQueue.cpp" #include "Event.cpp" Queue q[4]; // teller queues PriorityQueue pq; //eventList; int totalTime; int count = 0; int customerNo = 0; main (int argc, char *argv[]) { Customer* c; Event* nextEvent; // open customer arrival file ifstream data("customer.dat", ios::in); // initialize with the first arriving customer. ReadNewCustomer(data); While( pq.length() > 0 ) { nextEvent = pq.remove(); c = nextEvent->getCustomer(); if( c->getStatus() == -1 ){ // arrival event int arrTime = nextEvent->getEventTime(); int duration = c->getTransactionDuration(); int customerNo = c->getCustomerNumber(); processArrival(data, customerNo, arrTime, duration , nextEvent); } else { // departure event int qindex = c->getStatus(); int departTime = nextEvent->getEventTime(); processDeparture(qindex, departTime, nextEvent); } }

We have included lot of files in the program. Other than the standard libraries, we have Customer.cpp, Queue.h, PriorityQueue.cpp and Event.cpp. With the help of these four files, we will create Customer object, Queue object, PriorityQueue object and Event object. You may think that these are four factories, creating objects for us.

As there are four tellers, so we will create equal number of queues (Queue q[4]). Then we create a priority queue object pq from the PriorityQueue factory. We declare totalTime, count and customerNo as int. These are global variables.

In the main method, we declare some local variables of customer and event. Afterwards, the customer.dat file for the input data is opened as:

ifstream data("customer.dat", ios::in);

We read the first customers data from this file as:

readNewCustomer(data);

Here data is the input file stream associated to customer.dat. We will read the arrival time and time of transaction from the file of the first customer. After reading it, we will process this information.

Now there is the while loop i.e. the main driver loop. It will run the simulation. First thing to note is that it is not clock-based which is that the loop will execute for 24 hours. Here we have the condition of priority queue’s length. The variable pq represents the event queue. If there are some events to be processed, the queue pq will not be empty. Its length will not be zero. We get the next event from the priority queue, not from the queue. The method pq.remove() (de-queue method) will give us the event which is going to happen first in future. The priority of events is according the time. In the event object we have the customerNo. In the if statement, we check the status of the customer. If the status is –1, it will reflect that this is the new customer arrival event.

We know that when a new customer enters the bank, he will look at the four tellers and go to the teller where the queue is smallest. Therefore in the program, we will check which is the smallest queue and insert the customer in that queue. If the event is about the new customer, the if statement returns true. We will get its arrival time, duration and customer number and assign it to the variables arrTime, duration and customerNo respectively. We will call the method processArrival() and pass it the above information.

If the status of the customer is not equal to –1, it means that the customer is in one of the four queues. The control will go to else part. We will get the status of the customer which can be 0, 1, 2 and 3. Assign this value to qindex. Later on, we will see how these values are assigned to the status. We will get the departure time of the customer and call the processDeparture() method.

In the main driver loop, we will get the next event from the event queue. In this case, events can be of two types i.e. arrival event and the departure event. When the person enters the bank, it is the arrival event. If any queue is empty, he will go to the teller. Otherwise, he will wait in the queue. After the completion of the transaction, the customer will leave the bank. It is the departure event.

Let’s discuss the function readNewCustomer(). This function is used to read the data from the file.

void readNewCustomer(ifstream& data) { int hour,min,duration; if (data >> hour >> min >> duration) { customerNo++; Customer* c = new Customer(customerNo, hour*60+min, duration); c->setStatus( -1 ); // new arrival Event* e = new Event(c, hour*60+min ); pq.insert( e ); // insert the arrival event } else { data.close(); // close customer file } }

Here, we have used the >> to read the hour, minute and duration from the file. Then we create a customer object c from the customer factory with the new keyword. We pass the customerNo, arrival time and transaction duration to the constructor of the customer object. After the object creation, it is time to set its status to –1. This means that it is an arriving customer. Then we create an event object e passing it the customer c and the arrival time. We insert this event into the priority queue pq. If there is no more data to read, we go into the else part and close the data file.

Let’s see the function processArrival(). We have decided that when the customer arrives and no teller is available, he will go to the shortest queue.

int processArrival(ifstream &data, int customerNo, int arrTime, int duration, Event* event) { int i, small, j = 0; // find smallest teller queue small = q[0].length(); for(i=1; i < 4; i++ ) if( q[i].length() < small ){ small = q[i].length(); j = i; } // put arriving customer in smallest queue Customer* c = new Customer(customerNo, arrTime, duration ); c->setStatus(j); // remember which queue the customer goes in q[j].enqueue(c); // check if this is the only customer in the. // queue. If so, the customer must be marked for // departure by placing him on the event queue. if( q[j].length() == 1 ) { c->setDepartureTime( arrTime+duration); Event* e = new Event(c, arrTime+duration ); pq.insert(e); } // get another customer from the input readNewCustomer(data); }

First of all, we will search for the smallest queue. For this purpose, there is a for loop in the method. We will check the length of all the four queues and get the smallest one. We store the index of the smallest queue in the variable j. Then we create a customer object. We set its status to j, which is the queue no. Then we insert the customer in the smallest queue of the four. The customer may be alone in the queue. In this case, he does not need to wait and goes directly to the teller. This is the real life scenario. When we go to bank, we also do the same. In the banks, there are queues and everyone has to enter in the queue. If the queue is empty, the customers go straight to the teller. Here we are trying to simulate the real life scenario. Therefore if the length of the queue is one, it will mean that the customer is alone in the queue and he can go to the teller. We calculate his departure time by adding the arrival time and transaction time. At this time, the person can leave the bank. We create a departure event and insert it into the priority queue. In the end, we read a new customer. This is the way; a programmer handles the new customers. Whenever a new person enters the bank, we create an event and insert it into the smallest queue. If he is alone in the queue, we create a departure event and insert it into the priority queue. In the main while loop, when we remove the event, in case of first future event, it will be processed. After the completion of the transaction, the person leaves the bank.

We may encounter another case. There may be a case that before leaving the bank, more persons arrive and they have to wait in the queue for their turn. We handle this scenario in the departure routine. The code is:

int processDeparture( int qindex, int departTime, Event* event) { Customer* cinq = q[qindex].dequeue(); int waitTime = departTime - cinq->getArrivalTime(); totalTime = totalTime + waitTime; count = count + 1; // if there are any more customers on the queue, mark the // next customer at the head of the queue for departure // and place him on the eventList. if( q[qindex].length() > 0 ) { cinq = q[qindex].front(); int etime = departTime + cinq->getTransactionDuration(); Event* e = new Event( cinq, etime); pq.insert( e ); } }

In this method, we get the information about the qindex, departTime and event from the main method. We get the customer by using the qindex. Then we calculate the wait time of the customer. The wait time is the difference of departure time and the arrival time. The total time holds the time of all the customers. We added the wait time to the total time. We incremented the variable count by one. After the departure of this customer, next customer is ready for his transaction. The if statement is doing this. We check the length of the queue, in case of presence of any customer in the queue, we will check the customer with the front() method. We set its departure time (etime) by adding the depart time of the previous customer and his transaction time. Then we create an event and insert it in the priority queue.

In the end, we calculate the average time in the main loop and print it on the screen. Average time is calculated by dividing the total time to total customer.

// print the final average wait time. double avgWait = (totalTime*1.0) / count; cout << "Total time: " << totalTime << endl; cout << “Customer: " << count << endl; cout << "Average wait: " << avgWait << endl;

You may be thinking that the complete picture of simulation is not visible. How will we run this simulation? Another important tool in the simulation is animation. You have seen the animation of traffic. Cars are moving and stopping on the signals. Signals are turning into red, green and yellow. You can easily understand from the animation. If the animation is combined with the simulation, it is easily understood.

We have an animated tool here that shows the animation of the events. A programmer can see the animation of the bank simulation. With the help of this animation, you can better understand the simulation.

In this animation, you can see the Entrance of the customers, four tellers, priority queue and the Exit. The customers enter the queue and as the tellers are free. They go to the teller straight. Customer C1<30, 10> enters the bank. The customer C1 enters after 30 mins and he needs 10 mins for the transaction. He goes to the teller 1. Then customer C2 enters the bank and goes to teller 2. When the transaction ends, the customer leaves the bank. When tellers are not free, customer will wait in the queue. In the event priority queue, we have different events. The entries in the priority queue are like arr, 76 (arrival event at 76 min) or q1, 80 (event in q1 at 80 min) etc. Let’s see the statistics when a customer leaves the bank. At exit, you see the customer leaving the bank as C15<68, 3><77, 3>, it means that the customer C15 enters the bank at 68 mins and requires 3 mins for his transaction. He goes to the teller 4 but the teller is not free, so the customer has to wait in the queue. He leaves the bank at 77 mins.

 

Implementation of Priority Queue

In the priority queue, we put the elements in the queue to get them from the queue with a priority of the elements. Following is the C++ code of the priority queue.

#include "Event.cpp" #define PQMAX 30 class PriorityQueue { public: PriorityQueue() { size = 0; rear = -1; }; ~PriorityQueue() {}; int full(void) { return ( size == PQMAX ) ? 1 : 0; }; Event* remove() { if( size > 0 ) { Event* e = nodes[0]; for(int j=0; j < size-2; j++ ) nodes[j] = nodes[j+1]; size = size-1; rear=rear-1; if( size == 0 ) rear = -1; return e; } return (Event*)NULL; cout << "remove - queue is empty." << endl; }; int insert(Event* e) { if( !full() ) { rear = rear+1; nodes[rear] = e; size = size + 1; sortElements(); // in ascending order return 1; } cout << "insert queue is full." << endl; return 0; }; int length() { return size; }; };

In this code, the file Events.cpp has been included. Here we use events to store in the queue. To cater to the need of storing other data types too, we can write the PriorityQueue class as a template class.

In the above code, we declare the class PriorityQueue. Then there is the public part of the class. In the public part, at first a programmer encounters the constructor of the class. In the constructor, we assign the value 0 to size and –1 to rear variables. A destructor, whose body is empty, follows this. Later, we employ the method full() which checks the size equal to the PQMAX to see whether the queue is full. If the size is equal to PQMAX, the function returns 1 i.e. TRUE. Otherwise, it returns 0 i.e. FALSE. We are going to implement the priority queue with an array. We can also use linked list to implement the priority queue. However, in the example of simulation studied in the previous lecture, we implemented the queue by using an array. We have seen in the simulation example that there may be a maximum of five events. These events include one arrival event and four departure events. That means four queues from where the customers go to the teller and one to go out of the bank after the completion of the transaction. As we know that there is a need of only five queues, so it was decided to use the array instead of dynamic memory allocation and manipulating the pointers.

In the remove() method, there are some things which are the property of the priority queue. We don’t have these in the queue. In this method, first of all we check the size of the priority queue to see whether there is something in the queue or not. If size is greater than 0 i.e. there are items in the queue then we get the event pointer (pointer to the object Event) e from the first position (i.e. at index 0) of the array, which we are using internally to implement the queue. At the end of the method, we return this event object e. This means that we are removing the first object from the internal array. We already know that the removal of an item from the start of an array is very time consuming as we have to shift all the remaining items one position to the left. Thus the remove() method of the queue will execute slowly. We solved this problem by removing the item from the position where the front pointer is pointing. As the front and rear went ahead and we got empty spaces in the beginning, the circular array was used. Here, the remove() method is not removing the element from the front. Rather, it is removing element from the first position (i.e. index 0). Then we execute a for loop. This for loop starts from 0 and executes to size-2. We can notice that in this for loop, we are shifting the elements of the array one position left to fill the space that has been created by removing the element from the first position. Thus the element of index 1 becomes at index 0 and element of index 2 becomes at index 1 and so on. Afterwards, we decrease size and rear by 1. By decreasing the size 1 if it becomes zero, we will set rear to –1. Now by the statement

return e ;

We return the element (object e), got from the array. The outer part of the if block

return (Event*)NULL;

cout << "remove - queue is empty." << endl;

is executed if there is nothing in the queue i.e. size is less than 0. Here we return NULL pointer and display a message on the screen to show that the queue is empty.

Now let’s look at the insert() method. In this method, first of all we check whether the array (we are using internally) is full or not. In case, it is not full, we increase the value of rear by 1. Then we insert the object e in the nodes array at the position rear. Then the size is increased by 1 as we have inserted (added) one element to the queue. Now we call a method sortElements() that sorts the elements of the array in an order. We will read different algorithms of sorting later in this course.

We have said that when we remove an element from a priority queue, it is not according to the FIFO rule. We will remove elements by some other rule. In the simulation, we had decided to remove the element from the priority queue with respect to the time of occurrence of an event (arrival or departure). We will remove the element (event) whose time of occurrence is before other events. This can be understood from the example of the traffic over a bridge or crossing. We will give higher priority to an ambulance as compared to a bus. The cars will have the lower priority. Thus when a vehicle has gone across then after it we will see if there is any ambulance in the queue. If it is there, we will remove it from the queue and let go across the bridge. Afterwards, we will allow a bus to go and then the cars. In our simulation example, we put a number i.e. time of occurrence, with the object when we add it to the queue. Then after each insertion, we sort the queue with these numbers in ascending order. Thus the objects in the nodes array get into an order with respect to the time of their occurrence. After sorting, the first element in the array is the event, going to be occurring earliest in the future. Now after sorting the queue we return 1 that shows the insert operation has been successful. If the queue is full, we display a message to show that the queue is full and return 0, indicating that the insert operation had failed.

Then there comes the length() method, having a single statement i.e.

return size ;

This method returns the size of the queue, reflecting the number of elements in the queue. It is not the size of the array used internally to store the elements of the queue.

We have seen the implementation of the priority queue by using an array. We will use the priority queue in some other algorithms later. Now, we will see another implementation of the priority queue using some thing other than array, which is much better than using an array. This will be more efficient. Its remove and insert methods will be faster than the ones in array technique. Here in the simulation, we were making only five queues for the events. Suppose, if these go to hundreds or thousands, a lot of time will be spent to remove an element from the queue. Similarly, when an element is added, after adding the element, to sort the whole array will be a time consuming process. Thus the application, with the use of the priority queue, will not be more efficient with respect to the time.

Technorati Tags: data structure tutorial,ds tutorial,queues,priority queues,priority queues implementation,priority queue data structure,priority queue simulation,priority queue example,priority queue,priority queue tutorial

Queues

A queue is a linear data structure into which items can only be inserted at one end and removed from the other. In contrast to the stack, which is a LIFO (Last In First Out) structure, a queue is a FIFO (First In First Out) structure.

The usage of queue in daily life is pretty common. For example, we queue up while depositing a utility bill or purchasing a ticket. The objective of that queue is to serve persons in their arrival order; the first coming person is served first. The person, who comes first, stands at the start followed by the person coming after him and so on. At the serving side, the person who has joined the queue first is served first. If the requirement is to serve the people in some sort of priority order, there is a separate data structure that supports priorities. The normal queue data structure, presently under discussion, only supports FIFO behavior.

Now, let’s see what are the operations supported by the queue.

Queue Operations

The queue data structure supports the following operations:

Operation	Description
enqueue(X)	Place X at the rear of the queue.
dequeue()	Remove the front element and return it.
front()	Return front element without removing it.
isEmpty()	Return TRUE if queue is empty, FALSE otherwise

 Implementing Queue

There are certain points related to the implementation of the queue. Suppose we are implementing queue with the help of the linked -list structure. Following are the key points associated with the linked list implementations:

- Insert works in constant time for either end of a linked list.

- Remove works in constant time only.

- Seems best that head of the linked list be the front of the queue so that all removes will be from the front.

- Inserts will be at the end of the list.

The above figure shows queue elements on the left with two pointers front and rear. This is an abstract view of the queue, independent of its implementation method of array or linked list. On the right side is the same queue ,using linked list and pointers of front and rear. When dequeue() function is called once, the front element 1 is removed. The picture of the queue showing one element removal is also depicted below. Note that front pointer has been moved to the next element 7 in the list afer removing the front element 1.

Now at this stage of the queue, we will call enqueue (9) to insert an element 9 in it. . The following figure shows that the new element is inserted at the rear end and rear pointer starts pointing this new node with element 9.

At this point of time, the code of these functions of dequeue() and enqueue() should not be an issue.

Note that in this queue data structure, the new elements are inserted at rear end and removed from the front. This is in contrast to stack structure where the elements are inserted and removed from the same end.

Let’s see the code for queue operations:

/* Remove element from the front */ 1. int dequeue() 2. { 3. int x = front->get(); 4. Node* p = front; 5. front = front->getNext(); 6. delete p; 7. return x; 8. } /* Insert an element in the rear */ 9. void enqueue(int x) 10. { 11. Node* newNode = new Node(); 12. newNode->set(x); 13. newNode->setNext(NULL); 14. rear->setNext(newNode); 15. rear = newNode; 16. }

In dequeue() operation, at line 3, the front element is retrieved from the queue and assigned to the int variable x.

In line 4, the front pointer is saved in Node pointer variable p.

In line 5, the front pointer is moved forward by retrieving the address of the next node by using front->getNext() and assigning it to the front pointer.

In line 6, the node pointed to by the front pointer is deleted by using delete front statement.

At the end of dequeue() implementation, the value of deleted node that was saved in the int variable x, is returned back.

The enqueue(int ) is used to add an element in the queue. It inserts the element in the rear of the queue. At line 11, a new Node object is created using the new Node() statement and the returned starting address of the created object is assigned to the newNode pointer variable.

In line 12, the value of the passed in parameter x, is set in the newly created node object using the set() method.

In line 13, the next pointer in the newly created node is set to NULL.

In line 14, the newly created node is set as the next node of the node currently pointed by the rear pointer.

Ine line 15, the rear pointer is set to point to the newly created node.

The code of two smaller functions is as under:

/* To retrieve the front element */ int front() { return front->get(); } /* To check if the queue is empty */ int isEmpty() { return ( front == NULL ); }

The front() method is used to retrieve the front element. This is the oldest element inserted in the queue. It uses the get() method of the Node class.

The isEmpty() method is used to check whether the queue is empty or not. It checks the address inside the front pointer, if it is NULL. It will return true indicating that the queue is empty or vice versa.

While studying stack data structure, we implemented it by using both array and linked list. For queue, until now we have been discussing about implementing queue using linked list. Now, let’s discuss implementing queue with the help of an array.

Queue using Array

A programmer keeps few important considerations into view account before implementing a queue with the help of an array:

If we use an array to hold the queue elements, both insertions and removal at the front (start) of the array are expensive. This is due to the fact that we may have to shift up to “n” elements.

For the stack, we needed only one end but for a queue, both are required. To get around this, we will not shift upon removal of an element.

In the above figure, queue implementation using array is shown. As the array size is 8, therefore, the index of the array will be from 0 to 7. The number of elements inside array are 1, 7, 5 and 2, placed at start of the array. The front and rear in this implementation are not pointers but just indexes of arrays. front contains the starting index i.e. 0 while rear comprises 3.

Let’s see, how the enqueue() works:

As shown in the above diagram, an element i.e. 6 has been inserted in the queue. Now, the rear index is containing 4 while the front has the same 0 index. Let’s see the figure of the array when another element 8 is inserted in the queue.

When an element is removed from the queue. It is removed from the front index.

After another call of dequeue() function:

With the removal of element from the queue, we are not shifting the array elements. The shifting of elements might be an expensive exercise to perform and the cost is increased with the increase in number of elements in the array. Therefore, we will leave them as it is.

After insertion of two elements in the queue, the array that was used to implement it, has reached its limit as the last location of the array is in use now. We know that there is some problem with the array after it attained the size limit. We observed the similar problem while implementing a stack with the help of an array.

We can also see that two locations at the start of the array are vacant. Therefore, we should can consider how to use those locations appropriately in to insert more elements in the array.

Although, we have insert and removal operations running in constantly, yet we created a new problem that we cannot insert new elements even though there are two places available at the start of the array. The solution to this problem lies in allowing the queue to wrap around.

How can we wrap around? We can use circular array to implement the queue. We know how to make a linked list circular using pointers. Now we will see how can we make a circular array.

The number of locations in the above circular array are also eight, starting from index 0 to index 7. The index numbers are written outside the circle incremented in the clock-wise direction. To insert an element 21 in the array , we insert this element in the location, which is next to index 7.

Now, we will have to maintain four variables. front has the same index 2 while the, size is 8. ‘ rear’ has moved to index 0 and noElements is 7. Now, we can see that rear index has decreased instread of increasing. It has moved from index 7 to 0. front is containing index 2 i.e. higher than the index in rear. Let’ see, how do we implement the enqueue() method.

void enqueue( int x) { 1. rear = (rear + 1) % size; 2. array[rear] = x; 3. noElements = noElements + 1; }

In line 1 of the code, 1 is added in rear and the mod operator (that results in remainder of the two operands) is applied with size variable. This expression on the right of assignment in line 1 can result from 0 to 7 as size is containing value 8. This operator ensures that value of this expression will always be from 0 to 7 and increase or decrease from this. This resultant is assigned to the rear variable.

In line 2, the x (the value passed to enqueue() method to insert in the queue) is inserted in the array at the rear index position. Therefore, in the above case, the new element 21 is inserted at index 0 in the array.

In line 3, noElements is added to accumulate another element in the queue.

Let’s add another element in the queue.

Now, the queue, rather the array has become full. It is important to understand, that queue does not have such characteristic to become full. Only its implementation array has become full. To resolve this problem, we can use linked list to implement a queue. For the moment, while working with array, we will write the method isFull(), to determine the fullness of the array.

int isFull() { return noElements == size; } int isEmpty() { return noElements == 0; }

isFull() returns true if the number of elements (noElements) in the array is equal to the size of the array. Otherwise, it returns false. It is the responsibility of the caller of the queue structure to call isFull() function to confirm that there is some space left in the queue to enqueue() more elements.

Similarly isEmpty() looks at the number of elements (noElements) in the queue. If there is no element, it returns true or vice versa..

Let’s see the dequeue() method.

int dequeue() { int x = array[front]; front = (front + 1) % size; noElements = noElements - 1; return x; }

In the first line, we take out an element from the array at front index position and store it in a variable x. In the second line, front is incremented by 1 but as the array is circular, the index is looped from 0 to 7. That is why the mod (%) is being used. In the third line, number of elements (noElements) is reduced by 1 and finally the saved array element is returned.

Technorati Tags: Queue implementation,queue,queue implementation using array,queue data structure,queues,queue using arrays,circular arrays,queue implementation using array using arrays

Inter VLAN Routing (Router on a Stick)

In this tutorial we are going apply inter vlan routing. In order to communicate between different vlans, we use this phenomenon. Let us apply vlan on the following topology, then we will apply vtp (vlan trunking protocol).  

Now, in order to communicate between different vlans we will have to create sub interfaces of fast ethernet interface of router. Let us do that. Note that, we will create as many sub interfaces as many vlans we are using in our topology. In this case we are using 2 vlans, so we will create two sub interfaces for both vlans.

 

We will also apply encapsulation of sub interface.

 

Let us create vlans and assign those vlans to switch interfaces i.e. PCs

And,

 

In order to apply VTP we will have write the following commands. Apply the domain name, and trunk the ports of switch. Note, trunk only those ports that are connected to router and switches.

Thus, vlans are visible in other switches too after trunking.

Trunk the port of the switch 1 as well.

 

Now, we see ,in the bottom right corner,  we are able to communicate in between vlans and that s what we wanted , isnt it ?

 

Technorati Tags: inter vlan routing,router on a stick,vlan,vtp,communication between vlans,communication between different vlans,networking tutorial,inter vlan routing tutorial,router on a stick tutorial,apply inter vlan routing on packet tracer,inter vlan routing on packet tracer,inter vlan routing on packet tracer packet tracer,packet tracer tutorial,pt tutorial

ACL on packet tracer

Let us apply ACL (Access Control List) on the topology. First, let us assign IP addresses and change the state of the interfaces.

Here, the status is change as shown in the following diagram.

Then, we will have to assign IP addresses to the PCs.
 
And the PC attach to the other interface. Please note the difference between default gateways. We assign fast Ethernet interface address to default gateway.

Thus, after applying IP addresses. We see that Packet transfer is successful.

Let us apply ACL and permit and deny Hosts IP’s as we want. We are going to deny and permit certain hosts as follows.

Let us apply ACL and permit and deny Hosts IP’s as we want.
 
Then, we will have to tell the interface that which ACL to follow. ACL is uniquely identified with the number, in this case 1.

Now, you see that the denied will not be able to send the data while those who we permit can send packet.
 
Similarly, in the bottom right corner you can see status.

Technorati Tags: acl on packet tracer,packet tracer tutorial,pt tutorial,access control list,access control list on packet tracer,access control list on pt,access control list tutorial,networking access control list,acl on packet tracer tutorial

Infix to Postfix Conversion

In order to convert infix to postfix expression, we need to understand the precedence of operators first.

Precedence of Operators

There are five binary operators, called addition, subtraction, multiplication, division and exponentiation. We are aware of some other binary operators. For example, all relational operators are binary ones. There are some unary operators as well. These require only one operand e.g. – and +. There are rules or order of execution of operators in Mathematics called precedence. Firstly, the exponentiation operation is executed, followed by multiplication/division and at the end addition/subtraction is done. The order of precedence is 

(highest to lowest):

Exponentiation ­

Multiplication/division *, /

Addition/subtraction +, -

For operators of same precedence, the left-to-right rule applies:
A+B+C means (A+B)+C.

For exponentiation, the right-to-left rule applies:
A ­ B ­ C means A ­ (B ­ C)

We want to understand these precedence of operators and infix and postfix forms of expressions. A programmer can solve a problem where the program will be aware of the precedence rules and convert the expression from infix to postfix based on the precedence rules.

 

Examples of Infix to Postfix

Let’s consider few examples to elaborate the infix and postfix forms of expressions based on their precedence order:

Infix	Postfix
A + B 12 + 60 – 23 (A + B)*(C – D ) A ­ B * C – D + E/F	A B + 12 60 + 23 – A B + C D – * A B ­ C*D – E F/+

A programmer can write the operators either after the operands i.e. postfix notation or before the operands i.e. prefix notation. Some of the examples are as under:

Infix	Postfix
A + B	A B +
12 + 60 – 23	12 60 + 23 –
(A + B)*(C – D )	A B + C D – *
A ­ B * C – D + E/F	A B ­ C*D – E F/+

The last expression seems a bit confusing but may prove simple by following the rules in letter and spirit. In the postfix form, parentheses are not used. Consider the infix expressions as ‘4+3*5’ and ‘(4+3)*5’. The parentheses are not needed in the first but are necessary in the second expression. The postfix forms are:

4+3*5 435*+
(4+3)*5 43+5*

In case of not using the parenthesis in the infix form, you have to see the precedence rule before evaluating the expression. In the above example, if we want to add first then we have to use the parenthesis. In the postfix form, we do not need to use parenthesis. The position of operators and operands in the expression makes it clear in which order we have to do the multiplication and addition.

Now we will see how the infix expression can be evaluated. Suppose we have a postfix expression. How can we evaluate it? Each operator in a postfix expression refers to the previous two operands. As the operators are binary (we are not talking about unary operators here), so two operands are needed for each operator. The nature of these operators is not affected in the postfix form i.e. the plus operator (+) will apply on two operands. Each time we read an operand, we will push it on the stack. We are going to evaluate the postfix expression with the help of stack. After reaching an operator, we pop the two operands from the top of the stack, apply the operator and push the result back on the stack. Now we will see an example to comprehend the working of stack for the evaluation of the postfix form. Here is the algorithm in pseudo code form. After reading this code, you will understand the algorithm.

Stack s; // declare a stack while( not end of input ) { // not end of postfix expression e = get next element of input if( e is an operand ) s.push( e ); else { op2 = s.pop(); op1 = s.pop(); value = result of applying operator ‘e’ to op1 and op2; s.push( value ); } } finalresult = s.pop();

We have declared a Stack‘s’. There is a ‘while loop’ along with ‘not end of input’ condition. Here the input is our postfix expression. You can get the expression from the keyboard and use the enter key to finish the expression. In the next statement, we get the next element and store it in ‘e’. This element can be operator or operand. The operand needs not to be single digit. It may be of two digits or even more like 60 or 234 etc. The complete number is stored in the ‘e’. Then we have an ‘if statement’ to check whether ‘e’ is an operand or not. If ‘e’ is an operand than we wrote s.push(e) i.e. we pushed the ‘e’ onto the stack. If ‘e’ is not the operand, it may be an operator. Therefore we will pop the two elements and apply that operator. We pop the stack and store the operand in ‘op2’. We pop the stack again and store the element in ‘op1’. Then the operator in ‘e’ is applied to ‘op1’ and ‘op2’ before storing the result in value. In the end, we push the ‘value’ on the stack. After exiting the loop, a programmer may have only one element in the stack. We pop this element which is the final result.

Consider the example of 4+3*2 having a postfix form of 432*+. Here 4, 3, and 2 are operands whereas + and * are operators. We will push the numbers 4, 3 and 2 on the stack before getting the operator *. Two operands will be popped from the stack and * is being applied on these. As stack is a LIFO structure, so we get 2 first and then 3 as a result of pop. So 2 is store in ‘op1’ and 3 in ‘op2’. Let’s have a look on the program again. On applying * on these, we will push the result (i.e. 6) on the stack. The ‘while loop’ will be executed again. In case of getting the next input as operand, we will push it on the stack otherwise we will pop the two operands and apply the operator on these. Here the next element is the operator +. So two operands will be popped from the stack i.e. 6 and 4. We will apply the operator plus on these and push the result (i.e. 10) on the stack. The input is finished. Now we will pop the stack to get the final result i.e. 10.

 Postfix Expression solved by Example

In the earlier example, we have used the stack to solve the postfix expression. Let’s see another comprehensive example. The postfix expression is:

6 2 3 + - 3 8 2 / + * 2 ­ 3 +

We want to evaluate this long expression using stack. Let’s try to solve it on paper. We have five columns here i.e. input, op1, op2, value and stack. We will run our pseudo code program. In the start, we read the input as a result we get number 6. As 6 is operand, so it will be pushed on the stack. Then we have number 2 which will also be pushed on the stack. Now 2 is the most recent element. The next element is the number 3 that will also be pushed on the stack. Now, there are three elements on the stack i.e. 3, 2 and 6. The number 3 is the most recent. On popping, we will get the number 3 first of all. The next element is ‘+’, an operator. Now the else part of our pseudo code is executed. We will pop two operands from the stack and apply the operator (+) on these. The number 3 will be stored in variable op2 and number 2 in op1. The operator (+) will be applied on these i.e. 2+3 and the result is stored in value. Now we will push the value (i.e. 5) on the stack. Now we have two numbers on the stack i.e. 5 and 6. The number 5 is the most recent element. The next element is ‘-‘. As it is also an operator, so we will pop the two elements from the stack i.e. 5 and 6. Now we have 5 in op2 and 6 in op1. On applying the operator (-), we will get the result as 1 (6-5). We can’t say op2 - op1. The result (1) will be pushed on stack. Now on the stack, we have only one element i.e. 1. Next three elements are operands so we pushed 3, 8 and 2 on the stack. The most recent element is 2. The next input is an operator in the expression i.e. ‘/’, we will pop two elements from the stack. The number 2 will be stored in op2 while number 8 in op1. We apply the operator (/) on the op1 and op2 i.e. (op1/op2), the result is 4 (i.e. 8/2). We push the result on the stack. We have, now, three elements i.e. 4, 3, and 1 on the stack. The next element is operator plus (+). We will pop the two elements i.e. 4 and 3 and will apply the operator (+). The result (7) will be pushed on the stack. The next input element is operator multiply (*). We will pop the two elements i.e. 7 and 1 and the result (7*1 = 7) is pushed on the stack. You have noted that whenever we have an operator in the input expression, we have two or more elements on the stack. As the operators we are using are binary and we need two operands for them. It will never be the case that you want to pop two elements from the stack and there is only one or no element on the stack. If this happens than it means there is an error in the program and you have popped more values than required. The next input element is 2 that is pushed on the stack. We have, now, the operator ( ­ ) in the input. So we will pop the two elements, op2 will hold 2 and op1 will have the number 7. The operator ( ­ ) will be applied on the operands i.e. (7 ­ 2) and the result (49) is pushed on the stack. We have, now, the number 3 in the element being pushed on the stack. The last element is the operator plus (+). So we pop the two elements i.e. 49 and 2 and apply the operator on these. The result (49+3 = 52) is pushed on the stack. The input expression is finished, resulting in the final result i.e. 52.

This the tabular form of the evaluation of the postfix expression.

Input	op1	op2	value	stack
6				6
2				2 6
3				3 2 6
+	2	3	5	5 6
-	6	5	1	1
3	6	5	1	3 1
8	6	5	1	8 3 1
2	6	5	1	2 8 3 1
/	8	2	4	4 3 1
+	3	4	7	7 1
*	1	7	7	7
2	1	7	7	2 7
­	7	2	49	49
3	7	2	49	3 49
+	49	3	52	52

With the help of stack we can easily solve a very big postfix expression. Suppose you want to make a calculator that is a part of some application e.g. some spreadsheet program. This calculator will be used to evaluate expressions. You may want to calculate the value of a cell after evaluating different cells. Evaluation of the infix form programmatically is difficult but it can be done. We will see another data structure which being used to solve the expressions in infix form. Currently, we have to evaluate the values in different cells and put this value in another cell. How can we do that? We will make the postfix form of the expression associated with that cell. Then we can apply the above algorithm to solve the postfix expression and the final result will be placed at that cell. This is one of the usages of the stack.

Infix to postfix Conversion

We have seen how to evaluate the postfix expressions while using the stack. How can we convert the infix expression into postfix form? Consider the example of a spreadsheet. We have to evaluate expressions. The users of this spreadsheet will employ the infix form of expressions. Consider the infix expressions ‘A+B*C’ and ‘(A+B)*C’. The postfix versions are ‘ABC*+’ and ‘AB+C*’ respectively. The order of operands in postfix is the same as that in the infix. In both the infix expressions, we have the order of operands as A, B and then C. In the postfix expressions too, the order is the same i.e. A, B, followed by C. The order of operands is not changed in postfix form. However, the order of operators may be changed. In the first expression ‘A+B*C’, the postfix expression is ‘ABC*+’. In the postfix form multiplication comes before the plus operator. In scanning from left to right, the operand ‘A’ can be inserted into postfix expression. First rule of algorithm is that if we find the operand in the infix form, put it in the postfix form. The rules for operators are different. The ‘+’ cannot be inserted in the postfix expression until its second operand has been scanned and inserted. Keep the expression A+B*C in your mind. What is the second operand of the plus? The first operand is A and the second operand is the result of B*C. The ‘+’ has to wait until the ‘*’ has not been performed. You do the same thing while using the calculator. First you will multiply the B*C and then add A into the result. The ‘+’ has to be stored away until its proper position is found. When ‘B’ is seen, it is immediately inserted into the postfix expression. As ‘B’ is the operand, we will send the operand to the postfix form. Can the ‘+’ be inserted now? In case of ‘A+B*C’, we cannot insert ‘+’ because ‘*’ has precedence. To perform multiplication, we need the second operand. The first operand of multiplication is ‘B’ while the second one is ‘C’. So at first, we will perform the multiplication before adding result to ‘A’.

In case of ‘(A+B)*C’, the closing parenthesis indicates that ‘+’ must be performed first. After sending the A and B to postfix perform, we can perform the addition due to the presence of the parenthesis. Then C will be sent to the postfix expression. It will be followed by the multiplication of the C and the result of A + B. The postfix form of this expression is AB+C*. Sometimes, we have two operators and need to decide which to apply first like in this case ‘+’ and ‘*’. In this case, we have to see which operator has higher precedence. Assume that we have a function ‘prcd(op1,op2)’ where op1 and op2 are two operators. The function ‘prcd(op1,op2)’ will return TRUE if op1 has precedence over op2, FASLE otherwise. Suppose we call this function with the arguments ‘*’ and ‘+’ i.e. prcd(*, +), it will return true. It will also return true in case both op1 and op2 are ‘+’ e.g. if we have A+B+C, then it does not matter which + we perform first. The call prcd(+ , *) will return false as the precedence of * is higher than the + operator. The ‘+’ has to wait until * is performed.

Now we will try to form an algorithm to convert infix form into postfix form. For this purpose, a pseudo code will be written. We will also write the loops and if conditions. The pseudo code is independent of languages. We will be using a stack in this algorithm. Here, the infix expression is in the form of a string. The algorithm is as follows:

Stack s;

while( not end of input ) {

c = next input character;

if( c is an operand )

add c to postfix string;

else {

while( !s.empty() && prcd(s.top(),c) ){

op = s.pop();

add op to the postfix string;

}

s.push( c );

}

while( !s.empty() ) {

op = s.pop();

add op to postfix string;

}

First we will declare a stack ‘s’. The ‘while loop’ will continue till the end of input. We read the input character and store it in the ‘c’. Here the input character does not mean one character, but an operand or an operator. Then we have a conditional if statement. If ‘c’ is an operand, then we will have to add it to postfix string. Whenever we get an operand in the infix form, it will be added to the postfix form. The order of operands does not change in the conversion. However, in this case, the order of operators may change. If ‘c’ is the operator, then we will, at first, check that stack is not empty besides identifying the precedence of the operators between the input operator and the operator that is at the top of the stack. In case of the precedence of the operator that is on the stack is higher, we will pop it from the stack and send to the postfix string. For example if we have * on the stack and the new input operator is +. As the precedence of the + operator is less than the * operator, the operands of the multiplication has already been sent to the postfix expression. Now, we should send the * operator to the postfix form. The plus operator (+) will wait. When the while loop sends all such operators to the postfix string, it will push the new operator to the stack that is in ‘c’. It has to wait till we get the second operand. Then we will again get the input. On the completion of the input, the while loop will be finished. There may be a case that input may be completed even at the time when there are still some elements on the stack. These are operators. To check this, we have another while loop. This loop checks if the stack is not empty, pops the operator and put it in the postfix string. Let’s take a look at a comprehensive example to understand it. In case of the infix expression, A + B * C, we have three columns, one each for input symbol, the postfix expression and the stack respectively. Now let’s execute the pseudo code. First of all, we get the ‘A’ as input. It is an operand so we put it on the postfix string. The next input is the plus operator (+) which will be pushed on the stack. As it is an operator and we need two operands for it. On having a look at the expression, you might have figure out that the second operand for the plus operator is B*C. The next input is the operand B being sent to the postfix expression form. The next thing we get is the input element as ‘*’. We know that the precedence of * is higher than that of the +. Let’s see how we can do that according to our pseudo code. The prcd(s.top(), op) takes two operands. We will get the top element of the stack i.e. + will be used as first argument. The second argument is the input operator i.e. *. So the function call will be as prcd(+, *) while the function returns false because the precedence of the plus operator is not higher than the multiplication operator. So far, we have only one operand for multiplication i.e. B. As multiplication is also a binary operator, it will also have to wait for the second operand. It has to wait and the waiting room is stack. So we will push it on the stack. Now the top element of the stack is *. The next symbol is ‘C’. Being an operand, C will be added to the postfix expression. At this point, our input expression has been completed. Our first ‘while loop’ executes till the end of input. After the end of the input, the loop will be terminated. Now the control goes to the second while loop which says if there is something on the stack, pop it and add it the postfix expression. In this case, we have * and + on the stack. The * is at the top of the stack. So when we pop, we get * which is at the top of the stack and it will be added to the postfix expression. In the result of second pop, we get the plus operator (+) which is also added to the postfix expression. The stack is empty now. The while loop will be terminated and postfix expression is formed i.e. ABC*+.

Symbol	postfix	stack
A	A
+	A	+
B	AB	+
*	AB	* +
C	ABC	* +
	ABC*	+
	ABC*+

If we have to convert the infix expression into the postfix form, the job is easily done with the help of stack. The above algorithm can easily be written in C++ or C language, specially, if you already have the stack class. Now you can convert very big infix expressions into postfix expressions. Why we have done this? This can be understood with the help of the example of spreadsheet programming where the value of cell is the evaluation of some expression. The user of the spreadsheets will use the infix expressions as they are used to it.

Sometimes we do need the parenthesis in the infix form. We have to evaluate the lower precedence operator before the higher precedence operator. If we have the expression (A+B) *C, this means that we have to evaluate + before the multiplication. The objective of using parenthesis is to establish precedence. It forces to evaluate the expression first of all. We also have to handle parenthesis while converting the infix expression into postfix one. When an open parenthesis ‘(‘ is read, it must be pushed on the stack. This can be done by setting prcd(op,‘(‘ ) to be FALSE. What is the reason to put the parenthesis on the stack? It is due to the fact that as long as the closing parenthesis is not found, the open parenthesis has to wait. It is not a unary or binary operator. Actually, it is a way to show or write precedence. We can handle the parenthesis by adding some extra functionality in our prcd function. When we call prcd(op, ‘(‘), it will return false for all the operators and be pushed on the stack. Also, prcd( ‘(‘,op ) is FALSE which ensures that an operator after ‘(‘ is pushed on the stack. When a ‘)’ is read. All operators up to the first ‘(‘ must be popped and placed in the postfix string. To achieve this our function prcd( op,’)’ ) should return true for all the operators. Both the ‘(‘ and the’)’ will not go to the postfix expression. In postfix expression, we do not need parenthesis. The precedence of the operators is established in such a way that there is no need of the parenthesis. To include the handling of parenthesis, we have to change our algorithm. We have to change the line s.push(c) to:

if( s.empty() || symb != ‘)’ )
s.push( c );

else
s.pop(); // discard the ‘(‘

If the input symbol is not ‘)’ and the stack is not empty, we will push the operator on the stack. Otherwise, it is advisable to pop the stack and discard the ‘(‘. The following functionality has to be added in the prcd function.

prcd( ‘(‘, op ) = FALSE for any operator

prcd( op, ‘)’ ) = FALSE for any operator other than ‘)’

prcd( op, ‘)’ ) = TRUE for any operator other than ‘(‘

prcd( ‘)’, op ) = error for any operator.

Conversion from infix to postfix

During the process of conversion, there may be need of parenthesis in the infix especially at the times when we want to give a higher precedence to an operator of lower precedence. For example, if there is a + operator and * operator in an expression and a programmer wants the execution of addition before the multiplication. To achieve this object, it is necessary to put parentheses around the operands of + operator. Suppose, there is the expression A + B * C in which we want to give the precedence to the + operator over * operator. This expression will be written as (A + B) * C. Now we are going to discuss the conversion of infix expression that includes parentheses to the postfix expression. We have defined the return values for opening ‘(‘and closing ‘)’ parentheses in the precedence function. Let’s try to understand this process with the help of an example of converting the infix expression (A + B) * C into a postfix expression. We will see how our algorithm, discussed earlier, converts this infix expression into a postfix expression. To carry out the process of conversion we have three columns symbol, postfix and stack. The column symbol has the input symbols from the expression. The postfix column has the postfix string (expression) after each step and the stack is used to put the operators on it. The whole process of converting the infix notation into a postfix is given in the following table. This process of conversion is completed in eight steps. Each of the rows of the table depicts one step.

Step No.	Symbol	Postfix	Stack
1	(		(
2	A	A	(
3	+	A	(+
4	B	AB	(+
5	)	AB+
6	*	AB+	*
7	C	AB+C	*
8		AB+C*

First of all, there is the input symbol ‘(‘(i.e. opening parenthesis). As this is not an operand, it may be put on the stack. The next input symbol is ‘A’. Being an operand it goes to the postfix string and the stack remains unchanged. Then there is + operator of binary type. Moreover, there is one operand in the postfix string. We push this + operator on the stack and it has to wait for its second operand. Now in the input symbol, there is an operand ‘B’. We put his operand in the postfix string. Then after this, there is the closing parenthesis ‘)’ in the input symbol. We know that the presence of a closing parenthesis in the input means that an expression (within the parentheses) has been completed. All of its operands and operators are present with in the parentheses. As studied in the algorithm, we discard a closing parenthesis when it comes in the input. Then the operators from the stack are popped up and put in the postfix string. We also pop the opening parenthesis and discard it as we have no need of opening as well as closing parenthesis in the postfix notation of an expression. This process is carried out in the 5^th row of the table. The + operator is put in the postfix string. We also discard the opening parenthesis, as it is not needed in the postfix.

Now the next input symbol is *. We put this operator on the stack. There is one operand for the * operator i.e. AB+. The * operator being a binary operator, has to wait for the second operand. ‘C’ is the Next input symbol that is an operand. We put it in the postfix string. After this, the input string (expression) ends so we come out of the loop. We check if there is any thing on the stack now? There is * operator in the stack. We pop the operator and put it into the postfix string. This way, we get the postfix form of the given infix expression that becomes AB+C*. In this postfix expression, the + operator is before the * operator. So addition operation is done before the multiplication. This is mainly due to the fact that in the infix expression, we have put parentheses to give + operator the precedence higher than the * operator. Note that there are no parentheses in the postfix form of the given infix expression.

Now we apply the evaluation algorithm on this postfix expression (i.e. AB+C*). The two operands A and B, will go to the stack. Then operator + will pop these operands from the stack, will add them and push the result back on the stack. This result becomes an operand. Next ‘C’ will go to the stack and after this * operator will pop these two operands (result of addition and C). Their multiplication will lead to the final result. The postfix notation is simple to evaluate as compared to the infix one. In postfix, we need not to worry about what operation will be carried first. The operators in this notation are in the order of evaluation. However, in the infix notation, we have to force the precedence according to our requirement by putting parentheses in the expression. With the help of a stack data structure, we can do the conversion and evaluation of expressions easily.

Technorati Tags: Infix to postfix conversion,Infix to postfix conversion through stack,stack implementation of Infix to postfix conversion,solution of Infix to postfix conversion,data structure and algorithm tutorial,data structure tutorial,programming,infix postfix conversion,infix postfix expression