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

Stack implementation through Linked list in C

We can avoid the size limitation of a stack implemented with an array, with the help of a linked list to hold the stack elements. As needed in case of array, we have to decide where to insert elements in the list and where to delete them so that push and pop will run at the fastest. Primarily, there are two operations of a stack; push() and pop(). A stack carries lifo behavior i.e. last in, first out. You know that while implementing stack with an array and to achieve lifo behavior, we used push and pop elements at the end of the array. Instead of pushing and popping elements at the beginning of the array that contains overhead of shifting elements towards right to push an element at the start and shifting elements towards left to pop an element from the start. To avoid this overhead of shifting left and right, we decided to push and pop elements at the end of the array. Now, if we use linked list to implement the stack, where will we push the element inside the list and from where will we pop the element? There are few facts to consider, before we make any decision:
Insertion and removal in stack takes constant time. Singly linked list can serve the purpose. Hence, the decision is to insert the element at the start in the implementation of push operation and remove the element from the start in the pop implementation.


There are two parts of above figure.On the left hand, there is the stack implemented using an array. The elements present inside this stack are 1, 7, 5 and 2. The most recent element of the stack is 1. It may be removed if the pop() is called at this point of time. On the right side, there is the stack implemented using a linked list. This stack has four nodes inside it which are liked in such a fashion that the very first node pointed by the head pointer contains the value 1. This first node with value 1 is pointing to the node with value 7. The node with value 7 is pointing to the node with value 5 while the node with value 5 is pointing to the last node with value 2. To make a stack data strcuture using a linked list, we have inserted new nodes at the start of the linked list.

We are going to implement stack through linked list. Here is the code of stack implementation in C.

#include "stdio.h"
#include "stdlib.h"
#include "conio.h"

void pop();

void push(int value);

void display();

struct node

{

    int data;

    struct node *link;

};

struct node *top=NULL,*temp;

int main()

{

    int choice,data;

  

   

    while(1) //infinite loop is used to insert/delete infinite number of elements in stack

    {

       

        printf("\n1.Push\n2.Pop\n3.Display\n4.Exit\n");

        printf("\nEnter ur choice:");

        scanf("%d",&choice);

        switch(choice)

        {

        case 1:  //To push a new element into stack

           

           

            printf("Enter a new element :");

            scanf("%d",&data);

            push(data);

            break;

           

        case 2: // pop the element from stack

            pop();

            break;

           

        case 3: // Display the stack elements

            display();

            break;

        case 4: // To exit

            exit(0);

        }

       

    }     

getch();

return 0;

}

push(int data)

{

         temp=(struct node *)malloc(sizeof(struct node)); // creating a space for the new element.

         temp->data=data;

            temp->link=top;

            top=temp;

                    

}

pop()

{

            if(top!=NULL)

            {

                printf("The poped element is %d",top->data);

                top=top->link;

            }

            else

            {

                printf("\nStack Underflow");   

            }

           

}

display()

{

         temp=top;

            if(temp==NULL)

            {

                printf("\nStack is empty\n");

            }

           

            while(temp!=NULL)

            {

                printf(" %d ->",temp->data);

                temp=temp->link;

            }

               

}

Technorati Tags: stack,stack implementation using linked list,stack using linked list,stack implementation in linked list,stack using linked list in c,c stack implementation,stack link list in c

Sessional 2 Assignment

Create a network topology of your own choice. Create a rather innovative scenario in which you can apply the following:

• DHCP
• DNS
• VLAN
• STP
• VTP

Note: This assignment must be done individually. Plagiarism will not be tolerated. Any two topologies match will get 0 marks. Your Assignment will be checked next week in your first lab. No assignment will be checked after that. All the helping material is available on this site in case you need it. Bring your assignments in .pkt format, email it to yourself so that you can access it in lab.  Have a nice weekend.

GOOD LUCK

BroadCast and Collision domains

BroadCast Domain

A broadcast domain is a logical division of a computer network, in which all nodes can reach each other by broadcast at the data link layer. A broadcast domain can be within the same LAN segment or it can be bridged to other LAN segments. A broadcast domain encompasses a set of devices for  when one of the devices sends a broadcast, all the other devices receive a copy of the broadcast. For example, switches flood broadcasts and multicasts on all ports. Because broadcast frames are sent out all ports, a switch creates a single broadcast domain.

Any computer connected to the same repeater or switch is a member of the same broadcast domain. Further, any computer connected to the same set of inter-connected switches/repeaters is a member of the same broadcast domain. Routers and other higher-layer devices form boundaries between broadcast domains.

This is as compared to a collision domain, which would be all nodes on the same set of inter-connected repeaters, divided by switches and learning bridges. Collision domains are generally smaller than broadcast domains. Broadcast domains are only divided by layer 3 network devices such as routers or layer 3 switches. However,some layer two network devices are also able to divide the collision domains. A broadcast domain is a set of NICs for which a broadcast frame sent by one NIC is received by all other NICs in the same broadcast domain 

Collision Domain

A collision domain is the set of LAN interfaces whose frames could collide with each other, but not with frames sent by any other devices in the network. The collision is happened when to computer in same time want to use bandwidth. The CSMA/CD algorithm that deals with the issue of collisions, and some of the differences between how hubs and switches operate to create either a single collision domain (hubs) or many collision domains (switches). Generally speaking in easy terms, A collision domain is a set of network interface cards (NIC) for which a frame sent by one NIC could result in a collision with a frame sent by any other NIC in the same collision domain.

Only one device in the collision domain may transmit at any one time, and the other devices in the domain listen to the network in order to avoid data collisions. Because only one device may be transmitting at any one time, total network bandwidth is shared among all devices. Collisions also decrease network efficiency on a collision domain; if two devices transmit simultaneously, a collision occurs, and both devices must retransmit at a later time.

Modern wired networks use a network switch to eliminate collisions. By connecting each device directly to a port on the switch, either each port on a switch becomes its own collision domain (in the case of half duplex links) or the possibility of collisions is eliminated entirely in the case of full duplex links.

When creating any Ethernet LAN, you use some form of networking devices—typically switches today—a few routers, and possibly a few hubs. The different parts of an Ethernet LAN may behave differently, in terms of function and performance, depending on which types of devices are used. These differences then affect a network engineer’s decision when choosing how to design a LAN. The terms collision domain and broadcast domain define two important effects of the process of segmenting LANs using various devices. 

The Importance  of Collision and Broadcast Domains on LAN Design

When designing a LAN,  when choosing the number of devices in each collision domain and broadcast domain. First, consider the devices in a single collision domain for a moment. For a single collision domain: 

1. The devices share the available bandwidth in network.
2. The devices may inefficiently use that bandwidth due to the effects of collisions

For example, you might have ten PCs with 10/100 Ethernet NICs. If you connect all ten PCs to ten different ports on a single 100-Mbps hub, you have one collision domain, and the PCs in that collision domain share the 100 Mbps of bandwidth.
That may work well and meet the needs of those users. However, with higher traffic loads, the hub’s performance would be worse and you need a switch . Using a switch instead of a hub, with the same topology, would create ten different collision domains, each with 100 Mbps of bandwidth. Also, with only one device on each switch interface, no collisions would occur. This means that you could enable full duplex on each interface, effectively giving each interface 200 Mbps.

Using the switches instead of hubs seems like an obvious choice given the overwhelming performance benefits. Frankly, most new installations today use switches exclusively.

Technorati Tags: networking,broad cast domain,collision domain,broad cast domain vs collision domain,broad cast domain and collision domain

VTP on Packet Tracer

VLAN Trunk Protocol (VTP) reduces administration in a switched network. When you configure a new VLAN on one VTP server, the VLAN is distributed through all switches in the domain. This reduces the need to configure the same VLAN everywhere. Let us apply VTP on packet tracer.
 
Let us see vtp status by applying the command “show vtp status”.
 
Let us set domain name. In VTP there should be only one domain name through out to synchronize between all the switches.
 
Domain name is set.

In order for changes made in one switch to take place in other switches as well. we will have to trunk the interfaces. Only those interfaces that are connected.

Or we can select a range of interfaces and trunk them.
 
Now, when we check the status on other switches we can see that the domain name has been set on all the other switches as well.
 
Let us create VLAN.
 
This vlan is shown in other switch due to the trunking .
 
Now, there are three modes in a vtp.

i. Server
ii. Client
iii. Transparent

We are going to apply all three modes on different switches. We can create vlan in server mode, only use them in client mode. But the changes made in transparent mode are independent and does not have affect on other modes.


Let us turn the switch 7 to transparent mode and create a vlan in it.
 
The vlan created in transparent mode is not visible in the other modes.
 
If we change the mode of vtp from server to client , we are unable to create vlan now in the client mode as shown in the message below.
 

Technorati Tags: computer communication and networks,networking tutorial,networks tutorial,networking stuff,networks,vlan,vlan tutorial,vlan implementation,spanning tree protocol,virtual local area network,virtual lan,vlocal area network,vtp on packet tracer,vlan trunking protocol,vlan trunk protocol on packet tracer,vtp on pt

Spanning Tree Protocol on Packet Tracer

Let us apply STP on packet tracer. Let us develop a basic topology like the one in the following diagram.

As we can see in the above diagram that some light are green while others are orange. Y is it so ? We will see that in a moment. Let us try to communicate between two Hosts. Assign IP addresses to all hosts

As we can see in the figure below, the communication is successful. It is due to the spanning tree protocol applied on the switch by default. It provides us with the loop free environment. It calculates the cost of each path and provides us with the one that has the minimum cost. That is the reason that some links are up while others are down with the orange light.

So let us see what happens if we remove the spanning tree protocol from this topology.

We will remove STP from all the switches one by one.

After removing STP, we have observed by the following diagram, a couple of changes. i.e. all the lights are green. In fact, some are dark green. Some lights are blinking, while some are not. This is due to fact that as there is no protocol to decide that which path to choose as we have removed STP.

Now that if we try to communicate between any hosts it will fail and communication is disabled.

Technorati Tags: computer communication and networks,networking tutorial,networks tutorial,networking stuff,networks,vlan,vlan tutorial,vlan implementation,spanning tree protocol,virtual local area network,virtual lan,vlocal area network,spanning tree protocol on packet tracer,stp packet tracer,stp on pt,stp pt,stp on packet tracer