CEDA stack is a dynamic structure. It changes as elements are added to and removed from it.Postfix ExpressionsEvaluating a Postfix ExpressionPrimitive operationsA solution: Circular ArrayTo add an element ‘num’ in the queueint DequeueSTACK- A stack is a collection of items into which new itemsare inserted and from which items are deleted at one end(called the top of the stack).- Different implementations are possible; although theconcept of a stack is unique.Example: Trays in the cafeteria.- Two primary operations:1. push: adds a new item on top of a stack.2. pop: removes the item on the top of a stack- Stack is also known as push-down list1top- LIFO (Last In First Out): order of addition and deletionof items from a stack.A stack is a dynamic structure. It changes as elements are added to and removed from it.2Insert:A B C D E FDelete:F E DFEDCBAtopCBAtop- Implementation of a stack as an array#define maxstack 100struct stack{int items[maxstack];int top;};int isEmpty(struct stack s){return (s.top < 0);}int isFull(struct stack s){return (s.top >= maxstack-1);}To put a new item on stack:void push (struct stack *s, int x){if (s->top >= maxstack-1) printf(“The stack is full.\n”);else {s->top = s->top +1;s->items[s->top] = x;}3}To pop an item from the stack:int pop (struct stack *s){int x;if (s->top < 0) printf(“Stack is empty.\n”);else{x = s->items[s->top];s->top = s->top –1;return x;}}To indicate which item is at top of stack (without disturbing the stack)int returntop (struct stack *s){int x;if (s->top < 0) printf(“Stack is empty.\n”);else{x = s->items[s->top];return x;}}4Main programint main(){struct stack S;int c, i;S.top = -1;while ((c=getchar() )!='\n') push(&S, c);while (!isEmpty(S))printf("%c", pop(&S));printf("\n");}5Use of stack Evaluation of arithmetic expressions- Notation can be infix, postfix or prefix.Infix: operator is between operands A + BPostfix : operator follows operands AB+Prefix: operator precedes operands +AB- Operators in a postfix expression are in correctevaluation order. Postfix Expressionsa + b * c Infix form (precedence of * is higher than of +)a + (b * c)a + ( b c * ) convert the multiplication6a (b c * ) + convert the addition a b c * + Postfix formExample 2:( A + B ) * C Infix form( A B + ) * C Convert the addition(A B + ) C * Convert multiplicationA B + C * Postfix form No need of parenthesis anywhere a + (( b * c ) / d ) a + ( ( b c * ) /d )(precedence of * and / are same and they are left associative)a + ( b c * d / ) a b c * d / + 7- More examplesInfix Postfix(a + b) * (c – d) a b + c d - * a – b / (c + d * e) a b c d e * + / -((a + b) * c – (d – e))/(f + g) a b + c * d e - - f g + /Order of precedence for 5 binary operators:power (^)multiplication (*) and division (/)addition (+) and subtraction (-)The association is assumed to be left to right except inthe case of power where the association is assumedfrom right to left. i.e. a + b + c = (a+b)+c = ab+c+a^b^c = a^(b^c) = abc^^8Evaluating a Postfix ExpressionEach operator in a postfix string refers to the previoustwo operands . Each time we read an operand we push it onto a stack. When we reach an operator its operands will be the top two elements on the stack. We can then pop these two elements, perform the indicated operation on them and push the result on the stack so that it will be available for use as an operand of the nextoperator.9Example6 5 2 3 + 8 * + 3 + * 3 2 2 5 5 5 6 6 6 61 2 3 4 8 5 5 40 5 5 5 45 6 6 6 65 6 7 8 3 45 48 6 610Finally with the operator * the result of evaluating the expression is 28811Converting an Infix Expression to Postfixwhile there are more characters in the input {Read next symbol ch in the given infix expression.If ch is an operand put it into the output. If ch is an operator i.e.* , /, +, -, or ( { If stack is empty push ch onto stackElse check the item op at the top of the stack while (more items in the stack && precedence(ch) <= precedence (op) {pop op and append it to the output, provided it is not an open parenthesis the next top element becomes op}push ch onto stack}If ch is right parenthesis ‘)’Pop items from stack until left parenthesis reachedPop left parenthesis and discard both left and right parenthesis}/* now no more characters in the infix expression*/Pop remaining items in the stack to the output. 12QUEUES- A queue is a list from which items may be deletedat one end (front) and into which items may beinserted at the other end (rear)- Similar to checkout line in a grocery store - firstcome first served. - It is referred to as a first-in-first-out (FIFO) datastructure.- Queues have many applications in computersystems:- jobs in a single processor computer- print spooling- information packets in computer networks.13front rear- Primitive operationsenqueue (q, x): inserts item x at the rear of the queue qx = dequeue (q): removes the front element from q and returns itsvalue.isEmpty(q) : true if the queue is empty,otherwise false.Exampleenqueue(q, ‘A’);enqueue(q, ‘B’);enqueue(q, ‘C’);x = dequeue(q);enqueue(q, ‘D’);enqueue(q, ‘E’);14frontrearA B Cx= dequeue (q) -> x= ‘A’Array ImplementationA huge array and two variables (indices) front and rear to point the first and the last elements of the queue.0 1 2 3 4 5 6 7 8 9 10 11 12 13 145 3 8 11 9 4Initially:q.rear = -1;q.front = 0; /* queue is empty when rear < front */15frontrearB C D Efront rear- Addition and deletion are simple.- Good if the queue is often emptied.- Disadvantage: needs a huge array as the number ofslots would go on increasing as long as there areitems to be added to the list (irrespective of howmany items are deleted, as these two areindependent operations.)Ignoring overflow and underflow, insert and remove can be implemented as:/* number of elements in the queue = rear – front + 1 */enqueue(q, x):q.rear = q.rear +1;q.items[q.rear] = x;x = dequeue(q):x = q.items[q.front];q.front = q.front + 1;Problems with this representation:Although there is space we may not be able to add a new item. An attempt will cause an overflow.160 1 2 3 4C D EIt is possible to have an empty queue yet no new itemcan be inserted.( when front