Before introducing new material, here are the recursive versions of the algorithms from the linked list notes (Day 15).StacksQueuesA queue is a list from which items may be deleted at one end (the front or head) of the list and into which items may be inserted at the other end (the rear or tail).Before introducing new material, here are the recursive versions of thealgorithms from the linked list notes (Day 15). Stacks A stack is a collection of items into which new items are inserted and fromwhich items are deleted from only one end, called the top of the stack. Different implementations are possible; although the concept of a stack isunique. Example: Trays in the cafeteria.Stacks and Queues - 1 Data Structures: Stacks and Queues (Day 17)Practice: Create a recursive version of this function to create a linked listfrom an array of values. Answer will appear in the next set of notes.Practice: Create a recursive version of this function to count the nodes ina linked list. Answer will appear in the next set of notes.//Copies the contents of an array into a dynamically//growing list.struct node *array_to_list (int a[ ], int j, int n){ struct node *head; if ( j >= n) //base casereturn NULL; else { head = malloc(sizeof(struct node));head -> data = a[j];head ->next = array_to_list(a, j+1, n);return head; }//Count the number of nodes in a list int count(struct node *head){ if (head == NULL) //base casereturn 0; else return (1 + count(head->next));}ABCDEFGtop There are two primary operations defined on a stack:o push: add a new item to the top of the stack.o pop: removes the item from the top of the stack. A stack is also known as a push-down list. The “access policy” of a stack is LIFO (Last In First Out). A stack is a dynamic structure. It changes as elements are added to andremoved from it. pop push A stack can be implemented as a constrained version of a linked list. A stackis referenced via a pointer to the top element of the stack. The link member inthe last node of the stack is set to NULL to indicate the bottom of the stack. Example:stackptrwhere stackptr points to the top of the stack.Stacks and Queues - 2ABCDEFGtopABCDEFHH82 5 3 Note that stacks and linked lists are represented identically. The difference isthat insertions and deletions occur anywhere in a linked list but areconstrained to only the top of a stack. Function push creates a new node and places it on the top of the stack. Function pop removes a node from the top of the stack and frees the memorythat was allocated to the popped node, and returns the popped node.Implementation of a simple stack of integersStacks and Queues - 3struct stackNode{ int data;struct stackNode *nextptr;};//inserts a node at the top of the stackvoid push(struct stackNode **topptr, int info){struct stackNode *newptr;newptr = (struct stackNode *) malloc (sizeof (struct stackNode));if (newptr != NULL){ newptr->data = info;newptr->nextptr = *topptr;*topptr = newptr;}else printf(“%d not inserted. No memory available.\n”, info);}//remove a node from the top of the stackint pop(struct stackNode **topptr){ struct stackNode *tempptr;topptr = (topptr)->nextptr;free(tempptr);return popvalue;}//check for an empty stackint isEmpty(struct stackNode *topptr){return topptr ==NULL;}Applications of StacksReading a line of text and writing it out backwards (palindrome checking)Evaluation of arithmetic expressions Notation can be infix, postfix, or prefix. Infix: operators appear between operands. A + B Postfix: operators appear after operands. AB+ Prefix: operators appear before operands. +AB Operators in a postfix expression are in correct evaluation order and operandsappear in the same order as in an infix expression. Compilers convert infix expressions into postfix expression since they areeasy to evaluate with a stack.Postfix Expressions Precedence of * is higher than +Infix: a + b * cPostfix: abc*+ Precedence of * and / are the same and they are left associative.Infix: a + b * c / dPostfix: abc*d/+Stacks and Queues - 4//reverses a line of text.int main(){structu stackNode *top = NULL;int c;while ((c = getchar() )!= ‘\n’);push(&top, c);while(!isEmpty(top))printf(“%c”, pop(&top));printf(“\n”; Parentheses override the precedence rules.Infix: (a + b) * cPostfix: ab+c* More examplesInfix: (a + b) * (c – d)Postfix: ab+cd-*Infix: a – b/ (c + d * e)Postfix: abcde*+/-Infix: ((a + b) * c – (d – e))/(f + g)Postfix: ab+c*de- -fg+/ Association is assume to be left to right except for exponentiation where theassociation is right to left.Infix: a + b + c = (a + b) + c Postfix: ab+c+Infix: a ^ b ^ c = a ^ (b ^ c)Postfix: abc^^Algorithm for Converting an Infix Expression to PostfixStacks and Queues - 5while there are more characters in the input string{read the next symbol ch in the infix expressionif ch is an operand, put it into the output string.If ch is an operator{check the item op on the top of the stackwhile (more items in the stack && precedence (ch) <= precedence(op){pop op and append it to the output string.op becomes the next top element.}push ch onto the stack}}Evaluating a Postfix ExpressionSince each operator in a postfix expression refers to the previous twooperands, every time we read an operand, push it onto the stack. When weread an operator, its operands are the top two elements in the stack. Popthese two elements, perform the indicated operation and push the result backonto the stack so that it will be available for use as an operand for the nextoperation.Queues A queue is a list from which items may be deleted at one end (the front orhead) of the list and into which items may be inserted at the other end (therear or tail). A queue is similar to a checkout line at the grocery store – first come firstserved. Unlike a stack which is LIFO a queue is FIFO. Queues have many applications in computer systems ranging fromprocess/job scheduling to printer spooling to packet processing in networks. Primitive operations defined for a queue are:o enqueue(q, x) which inserts item x at the rear/tail of queue q.o dequeue(q, x) which removes item x from the front/head of queue q.o isEmpty(q) which returns true if queue q is empty and false otherwise.