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

VLAN on Packet Tracer

In this tutorial, we are going to apply VLAN on packet tracer. Let us create a topology with one switch and multiple hosts like in the figure below.

if we go to the switch and enter the command “show vlan ”. It shows the following. 
 
As we can see in the figure above all the interfaces are being displayed and they are all the part of the default vlan 1. Now let us apply vlans on the switch. We are going to create three vlans as follows.
 
Now, that we have created the vlans. Lets see if they are visible to us.

In the above figure, vlans are visible. Now, we are going to assign interfaces to vlans. They are two ways to do this.
i. We can select an interface and assign that interface to a specific vlan
ii. We can select multiple interfaces (range of interfaces) at once and assign those interfaces to vlan.
In the figure below, we have done both of these.


Now, when we write “show vlan “ command and observe it. We will realize that interfaces have been assigned to desired vlans respectively.
 
Let us assign IP addresses to PCs. Open the PC.
 
Assign IP address.
 
After assigning IP addresses, when we try to communicate between two PCs belonging to two different vlans, it will fail. Thus, we have achieved our purpose.
 
The message sending failure status can be seen in the bottom right corner.
 

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

VLAN

VLAN or  Virtual Local Area Network is a phenomenon which is used to logically separate or combine a network. It is used to configured one or more devices, so that they can communicate, as if they were attached to the same wire, when in fact they are located on a number of different LAN segments. Because VLANs are based on logical instead of physical connections, they are extremely flexible. 

What is VLAN

VLAN is a concept of partitioning of a physical network, so that distinct broadcast domains are created. This is usually achieved on switch or router devices. Simpler devices only support partitioning on a port level, so sharing VLANs across devices requires running dedicated cabling for each VLAN.

Grouping hosts with a common set of requirements regardless of their physical location by VLAN can greatly simplify network design. A VLAN has the same attributes as a physical local area network (LAN), but it allows for end stations to be grouped together more easily even if they are not on the same network switch. Without VLANs, a switch considers all interfaces on the switch to be in the same broadcast domain.To physically replicate the functions of a VLAN would require a separate, parallel collection of network cables and equipment separate from the primary network.

 How VLAN's work

When a LAN bridge receives data from a workstation, it tags the data with a VLAN identifier indicating the VLAN from which the data came. This is called explicit tagging. It is also possible to determine to which VLAN the data received belongs using implicit tagging. In implicit tagging the data is not tagged, but the VLAN from which the data came is determined based on other information like the port on which the data arrived. Tagging can be based on the port from which it came, the source Media Access Control (MAC) field, the source network address, or some other field or combination of fields. VLAN's are classified based on the method used. To be able to do the tagging of data using any of the methods, the bridge would have to keep an updated database containing a mapping between VLAN's and whichever field is used for tagging. For example, if tagging is by port, the database should indicate which ports belong to which VLAN. This database is called a filtering database. Bridges would have to be able to maintain this database and also to make sure that all the bridges on the LAN have the same information in each of their databases. The bridge determines where the data is to go next based on normal LAN operations. Once the bridge determines where the data is to go, it now needs to determine whether the VLAN identifier should be added to the data and sent. If the data is to go to a device that knows about VLAN implementation (VLAN-aware), the VLAN identifier is added to the data. If it is to go to a device that has no knowledge of VLAN implementation (VLAN-unaware), the bridge sends the data without the VLAN identifier.

 

Why use VLAN's?

VLAN offer a number of advantages over traditional LAN.

Physical topology independence


VLANs provide independence from the physical topology of the network by allowing physically diverse workgroups to be logically connected within a single broadcast domain. If the physical infrastructure is already in place, it now becomes a simple matter to add ports in new locations to existing VLANs if a department expands or relocates. These assignments can take place in advance of the move, and it is then a simple matter to move devices with their existing configurations from one location to another. The old ports can then be "decommissioned" for future use, or reused by the department for new users on the VLAN.

Performance
In networks where traffic consists of a high percentage of broadcasts and multicasts, VLAN's can reduce the need to send such traffic to unnecessary destinations. For example, in a broadcast domain consisting of 10 users, if the broadcast traffic is intended only for 5 of the users, then placing those 5 users on a separate VLAN can reduce traffic.
Compared to switches, routers require more processing of incoming traffic. As the volume of traffic passing through the routers increases, so does the latency in the routers, which results in reduced performance. The use of VLAN's reduces the number of routers needed, since VLAN's create broadcast domains using switches instead of routers. Switched networks by nature will increase performance over shared media devices in use today, primarily by reducing the size of collision domains. Grouping users into logical networks will also increase performance by limiting broadcast traffic to users performing similar functions or within individual workgroups. Additionally, less traffic will need to be routed, and the latency added by routers will be reduced

Formation of Virtual Workgroups
Nowadays, it is common to find cross-functional product development teams with members from different departments such as marketing, sales, accounting, and research. These workgroups are usually formed for a short period of time. During this period, communication between members of the workgroup will be high. To contain broadcasts and multicasts within the workgroup, a VLAN can be set up for them. With VLAN's it is easier to place members of a workgroup together. Without VLAN's, the only way this would be possible is to physically move all the members of the workgroup closer together.
Despite this saving, VLAN's add a layer of administrative complexity, since it now becomes necessary to manage virtual workgroups.

Reduced Cost
VLAN's can be used to create broadcast domains which eliminate the need for expensive routers.

Security
Periodically, sensitive data may be broadcast on a network. In such cases, placing only those users who can have access to that data on a VLAN can reduce the chances of an outsider gaining access to the data. VLAN's can also be used to control broadcast domains, set up firewalls, restrict access, and inform the network manager of an intrusion.

Improved manageability
VLANs provide an easy, flexible, less costly way to modify logical groups in changing environments. VLANs make large networks more manageable by allowing centralized configuration of devices located in physically diverse locations.

Technorati Tags: computer communication and networks,networking tutorial,networks tutorial,networking stuff,networks,vlan,vlan tutorial,vlan implementation,vlan applied,vlan applied on packet tracer,virtual local area network,virtual lan,vlocal area network

Abstract Data Type

A data type is a collection of values and a set of operations on those values. That collection and these operations form a mathematical construct that may be implemented with the use of a particular hardware or software data structure. The term abstract data type (ADT) refers to the basic mathematical concept that defines the data type. We have discussed four different implementations of the list data structure. In case of implementation of the list with the use of an array, the size of the array gives difficulty if increased. To avoid this, we allocate memory dynamically for nodes before connecting these nodes with the help of pointers. For this purpose, we made a singly linked list and connected it with the next pointer to make a chain. Moving forward is easy but going back is a difficult task. To overcome this problem, we made a doubly linked list using prev and next pointers. With the help of these pointers, we can move forward and backward very easily. Now we face another problem that the prev pointer of first node and the next pointer of the last node are NULL. Therefore, we have to be careful in case of NULL pointers. To remove the NULL pointers, we made the circular link list by connecting the first and last node.

The program employing the list data structure is not concerned with its implementation. We do not care how the list is being implemented whether through an array, singly linked list, doubly linked list or circular linked list. It has been witnessed that in these four implementations of the list, the interface remained the same i.e. it implements the same methods like add, get, next, start and remove etc. This proves that with this encapsulation attained by making a class, we are not concerned with its internal implementation. The implementation of these abstract data types can be changed anytime. These abstract data types are implemented using classes in C++. If the list is implemented using arrays while not fulfilling the requirements, we can change the list implementation. It can be implemented with the use of singly-link list or doubly link list. As long as the interface is same, a programmer can change the internal implementation of the list and the program using this list will not be affected at all. This is the abstract data type (ADT). What we care about is the methods that are available for use, with the List ADT i.e. add, get, and remove etc methods. We have not studied enough examples to understand all the benefits of abstract data types. We will follow this theme while developing other ADT. We will publish the interface and keep the freedom to change the implementation of ADT without effecting users of the ADT. The C++ classes provide a programmer an ability to create such ADTs. What benefits can we get with the help of these ADTs and classes? When we develop an ADT or a class or factory then the users of this factory are independent of how this factory works internally. Suppose that we have ordered the car factory (car class) to produce a new car and it replies after a long time. If we ordered the remove method to remove one node and we are waiting and it keeps on working and working. Then we might think that its implementation is not correct. Although, we are not concerned with the internal implementation of this ADT yet it is necessary to see whether this ADT is useful for solving our problem or not. It should not become a bottleneck for us. If the method we are using is too much time consuming or it has some problem in terms of algorithm used. On one side, we only use the interfaces provided by these ADTs, classes, or factories as long as they do what they promise. We are not concerned with the internal details. On the other hand, we have to be careful that these factories or methods should not take too much time so that these will not be useful for the problem.

This distinction will always be there. Sometimes, the source code of classes is not provided. We will be provided libraries, as standard libraries are available with the compiler. These classes are in compiled form i.e. are in object form or in binary form. On opening these files, you will not see the C++ code, rather binary code. When you read the assembly language code, it will give some idea what this binary code is about. You can view the interface methods in the .h file. As an application programmer, you have to see that the ADTs being used are written in a better way. The point to be remembered here is that you should not worry about the internal implementation of these ADTs. If we want to change the internal implementation of the ADTs, it can be done without affecting the users of these ADTs. While writing a program, you should check its performance. If at some point, you feel that it is slow, check the ADTs used at that point. If some ADT is not working properly, you can ask the writer of the ADT to change the internal implementation of that ADT to ensure that it works properly.

 

Technorati Tags: data structure,data structure and algorithm tutorial,ds tutorial,linked list tutorial,abstract data type

Stack Implementation using array

Lets implement the stack using the arrays. The stack shown in the below diagram may be considered as an array. Here the array is shown vertically. We can implement the stack using array. The interface will remain as push and pop methods. The user of the stack does not need to know that the stack is internally implemented with the help of array. The worst case for insertion and deletion from an array may happen when we insert and delete from the beginning of the array. We have to shift elements to the right for insertion and left for removal of an element. We face the same problem while implementing the list with the use of the array. If we push and pop the elements from the start of the array for stack implementation, this problem will arise. In case of push, we have to shift the stack elements to the right. However, in case of pop, after removing the element, we have to shift the elements of stack that are in the array to the left. If we push the element at the end of the array, there is no need to shift any element. Similarly as the pop method removes the last element of the stack which is at the end of the array, no element is shifted. To insert and remove elements at the end of the array we need not to shift its elements. Best case for insert and delete is at the end of the array where there is no need to shift any element. We should implement push() and pop() by inserting and deleting at the end of an array.

In the above diagram, on the left side we have a stack. There are four elements in the stack i.e. 1, 7, 5 and 2. The element 1 is the extreme-most that means that it is inserted in the end whereas 7, 5, and 2 have been added before. As this is a LIFO structure so the element 1 should be popped first. On the right side we have an array with positions 0, 1, 2, 3 and so on. We have inserted the numbers 2, 5, 7 and 1. We have decided that the elements should be inserted at the end of the array. Therefore the most recent element i.e. 1 is at position 3. The top is the index representing the position of the most recent element. Now we will discuss the stack implementation in detail using array.

We have to choose a maximum size for the array. It is possible that the array may ‘fill-up’ if we push enough elements. Now more elements cannot be pushed. Now what should the user of the stack do? Internally, we have implemented the stack using array which can be full. To avoid this, we write isFull() method that will return a boolean value. If this method returns true, it means that the stack (array) is full and no more elements can be inserted. Therefore before calling the push(x), the user should call isFull() method. If isFull() returns false, it will depict that stack is not full and an element can be inserted. This method has become the part of the stack interface. So we have two more methods in our interface i.e. isEmpty() and isFull().

Now we will discuss the actual C++ code of these operations. These methods are part of stack class or stack factory. We have an array named A while current is its index. The code of pop() method is as:

 

int pop() { return A[current--]; } In this method, the recent element is returned to the caller, reducing the size of the array by 1. The code of push method is: void push(int x) { A[++current] = x; }

 

We know that ++current means that add one to the current and then use it. That also shows that element x should be inserted at current plus one position. Here we are not testing that this current index has increased from the array size or not. As discussed earlier that before using the push method, the user must call isFull() method. Similarly it is the responsibility of the user to call the isEmpty() method before calling the pop method. Therefore there is no if statement in the push and pop method.

The code of the top() method is:

 

int top() { return A[current]; } This method returns the element at the current position. We are not changing the value of current here. We simply want to return the top element. int isEmpty() { return ( current == -1 ); } This method also tests the value of the current whether it is equal to -1 or not. Initially when the stack is created, the value of current will be -1. If the user calls the isEmpty() method before pushing any element, it will return true. int isFull() { return ( current == size-1); }

This method checks that the stack is full or not. The variable size shows the size of the array. If the current is equal to the size minus one, it means that the stack is full and we cannot insert any element in it.

We have determined the cost and benefit of all the data structures. Now we will see how much time these methods take. A quick examination shows that all the five operations take constant time. In case of list, the find method takes too much time as it has to traverse the list. Whereas the add and remove methods are relatively quick. The methods of stack are very simple. There is no complexity involved. We insert element at one side and also remove from that side not in the middle or some other place. Therefore we need not to carry out a lot of work. During the usage of the array, the stack methods push, pop, top, isFull and isEmpty all are constant time operations. There is not much difference of time between them.

The complete code of the program is:

/* Stack implementation using array */ #include <iostream.h> /* The Stack class */ class Stack { public: Stack() { size = 10; current = -1;} //constructor int pop(){ return A[current--];} // The pop function void push(int x){A[++current] = x;} // The push function int top(){ return A[current];} // The top function int isEmpty(){return ( current == -1 );} // Will return true when stack is empty int isFull(){ return ( current == size-1);} // Will return true when stack is full private: int object; // The data element int current; // Index of the array int size; // max size of the array int A[10]; // Array of 10 elements }; // The main method int main() { Stack stack; // creating a stack object // pushing the 10 elements to the stack for(int i = 0; i < 12; i++) { if(!stack.isFull()) // checking stack is full or not stack.push(i); // push the element at the top else cout <<"\n Stack is full, can't insert new element"; } // pop the elements at the stack for (int i = 0; i < 12; i++) { if(!stack.isEmpty()) // checking stack is empty or not cout << "\n The popped element = " << stack.pop(); else cout <<"\n Stack is empty, can't pop"; } }

The output of the program is:

Stack is full, can't insert new element Stack is full, can't insert new element The popped element = 9 The popped element = 8 The popped element = 7 The popped element = 6 The popped element = 5 The popped element = 4 The popped element = 3 The popped element = 2 The popped element = 1 The popped element = 0 Stack is empty, can't pop Stack is empty, can't pop

However, a programmer finds the size-related problems in case of an array. What should we do when the array is full? We can avoid the size limitation of a stack implemented with an array by using a linked list to hold the stack elements.

Technorati Tags: stack implementation using array,data structure,data structure and algorithm tutorial,ds tutorial,Stack tutorial,stack implementation,stack programming,stack in c++,stack operations.

Stacks

Let us discuss another important data structure i.e stack.  Some examples of stacks in real life are stack of books, stack of plates etc. We can add new items at the top of the stack or remove them from the top. We can only access the elements of the stack at the top. Following is the definition of stacks.

“Stack is a collection of elements arranged in a linear order”.

Let’s see an example to understand this. Suppose we have some video cassettes. We took one cassette and put it on the table. We get another cassette and put it on the top of first cassette. Now there are two cassettes on the table- one at the top of other. Now we take the third cassette and stack it on the two. Take the fourth cassette and stack it on the three cassettes.

Now if we want to take the cassette, we can get the fourth cassette which is at the top and remove it from the stack. Now we can remove the third cassette from the stack and so on. Suppose that we have fifty cassettes stacked on each other and want to access the first cassette that is at the bottom of the stack. What will happen? All the cassettes will fell down. It will not happen exactly the same in the computer. There may be some problem. It does not mean that our data structure is incorrect. As we see in the above example that the top most cassette will be removed first and the new cassette will be stacked at the top. The same example can be repeated with the books. In the daily life, we deal with the stacked goods very carefully.

Now we will discuss how to create a stack data structure or a factory, going to create stack object for us. What will be the attributes of this object? During the discussion on the list, we came to know that a programmer adds values in the list, removes values from the list and moves forward and backward. In case of a stack too, we want to add things and remove things. We will not move forward or backward in the stack. New items can be added or removed at the top only. We can not suggest the removal of the middle element of the stack.

Let’s talk about the interface methods of the stacks. Some important methods are:

Method Name	Description
push(x)	Insert x as the top element of the stack
pop()	Remove the top element of the stack and return it.
top()	Return the top element without removing it from the stack.

The push(x) method will take an element and insert it at the top of the stack. This element will become top element. The pop() method will remove the top element of the stock and return it to the calling program. The top() method returns the top-most stack element but does not remove it from the stack. The interface method names that we choose has special objective. In case of list, we have used add, remove, get, set as the suitable names. However, for stack, we are using push, pop and top. We can depict the activity from the method name like push means that we are placing an element on the top of the stack and pushing the other elements down.

The example of a hotel’s kitchen may help understand the concept of stacks in a comprehensive manner. In the kitchen, the plates are stacked in a cylinder having a spring on the bottom. When a waiter picks a plate, the spring moves up the other plates. This is a stack of plates. You will feel that you are pushing the plates in the cylinder and when you take a plate from the cylinder it pops the other plates. The top method is used to get the top- most element without removing it.

When you create classes, interfaces and methods, choose such names which depicts what these method are doing. These names should be suitable for that class or factory.

Let’s discuss the working of stack with the help of a diagram.

 

At the start, the stack is empty. First of all, we push the value 2 in the stack. As a result, the number 2 is placed in the stack. We have a top pointer that points at the top element. Then we said push(5). Now see how 2 and 5 are stacked. The number 5 is placed at the top of number 2 and the pointer top moves one step upward. Then we pushed the number 7 which is placed on the top and the number 2 and 5 are below. Similarly, we push number 1. The last figure in the first row shows the stacked values of the numbers- 1, 7, 5 and 2.

Let’s pop the elements from the stack. The first figure of second row shows the pop operation. As a result, the number 1 is popped. Than again we push the number 21 on the stack. The number 7, 5, and 2 are already in the stack and number 21 is pushed at the top. If we pop now, the number 21 is popped. Now number 7 is at the top. If we pop again, the number 7 is popped. Pop again and the number 5 is popped and number 2 remains in the stack. Here with the help of this diagram, we are proving that the values are added at the top and removed at the top in a stack.

The last element to go into the stack is the first to come out. That is why, a stack is known as LIFO (Last In First Out) structure. We know that the last element pushed in the stack is at the top which is removed when we call pop. Let’s see some other scenarios. What happens if we call pop() while there is no element? One possible way-out is that we have isEmpty() function that returns true if stack is empty and false otherwise. This is a boolean function that returns false if there is no element in the stack. Otherwise, it will return true. The second option is this that when we call pop on an empty stack, it throws an exception. This is a concept of advanced C++. Exception is also a way to convey that some unusual condition has arisen or something has gone wrong. Suppose, if we have a division method and try to divide some number with zero. This method will throw ‘division by zero’ exception. Currently we will not throw an exception but use the isEmpty() method. The user who is employing the stack is responsible to call the isEmpty() method before calling the pop. Call the pop method if isEmpty() returns false . Otherwise, there will be a problem.

For stack implementation using array, look at this article. For stack implementation through linked list, click here.

Stack Implementation: Array or Linked List

Since both implementations support stack operations in constant time, we will see what are the possible reasons to prefer one implementation to the other.
- Allocating and de-allocating memory for list nodes does take more time than pre-allocated array. Memory allocation and de-allocation has cost in terms of time, especially, when your system is huge and handling a volume of requests. While comparing the stack implementation, using an array versus a linked list, it becomes important to consider this point carefully.
- List uses as much memory as required by the nodes. In contrast, array requires allocation ahead of time. In the previous bullet, the point was the time required for allocation and de-allocation of nodes at runtime as compared to one time allocation of an array. In this bullet, we are of the view that with this runtime allocation and de-allocation of nodes, we are also getting an advantage that list consumes only as much memory as required by the nodes of list. Instead of allocating a whole chunk of memory at one time as in case of array, we only allocate memory that is actually required so that the memory is available for other programs. For example, in case of implementing stack using array, you allocated array for 1000 elements but the stack, on average, are using 50 locations. So, on the average, 950 locations remain vacant. Therefore, in order to resolve this problem, linked list is handy.
- List pointers (head, next) require extra memory. Consider the manipulation of array elements. We can set and get the individual elements with the use of the array index; we don’t need to have additional elements or pointers to access them. But in case of linked list, within each node of the list, we have one pointer element called next, pointing to the next node of the list. Therefore, for 1000 nodes stack implemented using list, there will be 1000 extra pointer variables. Remember that stack is implemented using ‘singly-linked’ list. Otherwise, for doubly linked list, this overhead is also doubled as two pointer variables are stored within each node in that case.
- Array has an upper limit whereas list is limited by dynamic memory allocation. In other words, the linked list is only limited by the address space of the machine. We have already discussed this point at reasonable length in this lecture.

 Use of Stack

Examples of uses of stack include- traversing and evaluating prefix, infix and postfix expressions.
Consider the expression A+B: we think of applying the operator “+” to the operands A and B. We have been writing this kind of expressions right from our primary classes. There are few important things to consider here:
Firstly, + operator requires two operators or in other words “+” is a binary operator.
Secondly, in the expression A+B, the one operand A is on left of the operator while the other operand B is on the right side. This kind of expressions where the operator is present between two operands called infix expressions. We take the meanings of this expression as to add both operands A and B.
There are two other ways of writing expressions:
- We could write +AB, the operator is written before the operands A and B. These kinds of expressions are called Prefix Expressions.
- We can also write it as AB+, the operator is written after the operands A and B. This expression is called Postfix expression.
The prefixes pre and post refer to the position of the operator with respect to the two operands.
Consider another expression in infix form: A + B * C. It consists of three operands A, B, C and two operator +,* . We know that multiplication () is done before addition (+), therefore, this expression is actually interpreted as: A + (B * C). The interpretation is because of the precedence of multiplication (*) over addition (+). The precedence can be changed in an expression by using the parenthesis. We will discuss it a bit later.
Let’s see, how can we convert the infix expression A + (B * C) into the postfix form. Firstly, we will convert the multiplication to postfix form as: A + (B C *). Secondly, we will convert addition to postfix as: A (B C *) + and finally it will lead to the resultant postfix expression i.e. : A B C * +. Let’s convert the expression (A + B) * C to postfix. You might have noticed that to overcome the precedence of multiplication operator (*) we have used parenthesis around A + B because we want to perform addition operation first before multiplication.
(A + B) * C infix form
(A B +) * C convert addition
(A B +) C * convert multiplication
A B + C * postfix form
These expressions may seem to be difficult to understand and evaluate at first. But this is one way of writing and evaluating expressions. As we are normally used to infix form, this postfix form might be little confusing. If a programmer knows the algorithm, there is nothing complicated and even one can evaluate the expression manually.

Technorati Tags: data structure,data structure and algorithm tutorial,ds tutorial,Stack tutorial,stack implementation,stack programming,stack in c++,stack operations.