UNIT II LINEAR DATA STRUCTURES – STACKS.pptx

PPT related to Linear data structures like stack and queue

1. UNIT II LINEAR DATA STRUCTURES – STACKS, QUEUES Stack ADT – Operations – Applications – Evaluating arithmetic expressions- Conversion of Infix to postfix expression – Queue ADT – Operations – Circular Queue – Priority Queue – deQueue – applications of queues.

2. STACK :DEFINITION Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO ( L ast I n F irst O ut) or FILO ( F irst I n L ast O ut).

3. The following operations are performed on the stack. Push (To insert an element on to the stack) Pop (To delete an element from the stack) Display (To display elements of the stack) Operations on a Stack

4. A stack Overflow is an undesirable condition in which the program tries to use more memory space than the call stack has available. If a Stack is empty and yet a Pop operation is attempted, then it results in Stack Underflow condition. Conditions on a Stack

5. The stack implementation can be done using ( i )Array :Array is a static data structure so the collection of data must be fixed in size. The only problem with this implementation is array size must be specified initially. int stk [MAXSIZE]; int top; Implementation of stack

6. #include<stdio.h> #include<stdlib.h> int stack[100], choice,n,top,x,i ; void push(void); void pop(void); void display(void); int main() { top=-1; printf ("\n Enter the size of STACK[MAX=100]:"); scanf ("% d",&n ); printf ("\n\t STACK OPERATIONS USING ARRAY"); printf ("\n\t--------------------------------"); printf ("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT"); do

7. { printf ("\n Enter the Choice:"); scanf ("% d",&choice ); switch(choice) { case 1: { push(); break; } case 2: { pop(); break; }

8. case 3: { display(); break; } case 4: { printf ("\n\t EXIT POINT "); break; } default: { printf ("\n\t Please Enter a Valid Choice(1/2/3/4)"); }

9. } } while(choice!=4); return 0; } void push() { if(top>=n-1) { printf ("\n\ tSTACK is over flow"); } else { printf (" Enter a value to be pushed:");

10. scanf ("% d",&x ); top++; stack[top]=x; } } void pop() { if(top<=-1) { printf ("\n\t Stack is under flow"); } else { printf ("\n\t The popped elements is % d",stack [top]); top--;

11. } } void display() { if(top>=0) { printf ("\n The elements in STACK \n"); for( i =top; i >=0; i --) printf ("\ n%d ",stack[ i ]); printf ("\n Press Next Choice"); } else { printf ("\n The STACK is empty"); } }

12. ( ii)Linked List :Linked List is a dynamic data structure. So collection of data can be used which are variable in size and structure. The program executes can grow and shrink to accommodate the data being stored. struct Node { int data; struct Node* link; }*top, *head;

13. Push Display Pop

14. void push () { int data; struct node *top =(struct node*)malloc( sizeof (struct node)); if(head==NULL) { printf ("Enter the value"); scanf ("% d",&data ); top->data = data; top -> link = NULL; head=top; } else { top->data = data; top->link = head; head=top; } printf ("Item pushed"); } }

15. void pop() { struct node *top; if (head == NULL) { printf ("Underflow"); } else { top = head; head = head->next; free(top); printf ("Item popped"); } }

16. void display() { int i ; struct node *top; ptr =head; if( ptr == NULL) { printf ("Stack is empty\n"); } else { printf ("Printing Stack elements \n"); while( ptr !=NULL) { printf ("%d\n", ptr -> val ); ptr = ptr ->next; } } }

17. Conversion of infix to Postfix expression Evaluating Arithmetic Expression Applications of Stack

18. Arithmetic Expression

19. • Infix expression : The expression of the form a op b. When an operator is in-between every pair of operands. • Postfix expression : The expression of the form a b op. When an operator is followed for every pair of operands. • Why postfix representation of the expression? The compiler scans the expression either from left to right or from right to left. Conversion of infix to postfix

20. • Consider the below expression: a op1 b op2 c op3 d If op1 = +, op2 = *, op3 = + The compiler first scans the expression to evaluate the expression b * c, then again scan the expression to add a to it. The result is then added to d after another scan. The repeated scanning makes it very in-efficient. •It is better to convert the expression to postfix(or prefix) form before evaluation. •The corresponding expression in postfix form is: abc *+d+. Conversion of infix to postfix

21. • Stack organized computers are better suited for post-fix notation than the traditional infix notation. Thus the infix notation must be converted to the post-fix notation. • Expressions are usually represented in what is known as Infix notation, in which each operator is written between two operands (i.e., A + B). • we must distinguish between ( A + B )*C and A + ( B * C ) by using either parentheses or some operator-precedence convention. • Polish notation (prefix notation) – It refers to the notation in which the operator is placed before its two operands. Here no parentheses are required, i.e., +AB Evaluating Arithmetic Expression

22. • Reverse Polish notation (postfix notation) – It refers to the notation in which the operator is placed after its two operands. Again, no parentheses is required in Reverse Polish notation, i.e., AB+ There are 3 levels of precedence for 5 binary operators Highest: Exponentiation (^) Next highest: Multiplication (*) and division (/) Lowest: Addition (+) and Subtraction (-) Evaluating Arithmetic Expression

23. For ex: Infix notation: (A-B)*[C/(D+E)+F] Post-fix notation: AB-CDE +/F +* • We first perform the arithmetic inside the parentheses (A-B) and (D+E). • The division of C/(D+E) must done prior to the addition with F • After that multiply the two terms inside the parentheses and bracket.

24. •Linear data structure •Insertion occurs only at one end called Rear •Deletion occurs only at one end called Front •Element that is inserted first is deleted ( FIFO principle ) Queue ADT

25. • Enqueue : Inserting an element into the queue (at rear) • Dequeue : Deleting an element from the queue (at front) Exceptional Conditions: • Overflow : Attempting to insert an element into queue when it is full • Underflow : Attempting to delete an element from queue when it is empty Operations in queue:

26. Enqueue operation Void Enqueue ( int num ) //Let num = 12 and max=5 { if (rear==max-1) print(“Queue Overflow”); else if (front == -1 && rear == -1) { front = rear = 0; Q[rear] = num ; } else { rear++; Q[rear] = num ; } } Array Implementation of Queue Q 12 25

27. Dequeue Operation Void Dequeue () { int val ; if (front == -1 || front > rear) print(“Queue Underflow”); else { val = Q[ front]; front++; free( val ); } } Array Implementation of Queue 12 25

28. Display Operation void Display () { int i ; if (front == -1 || front > rear) print (“Queue Underflow”); else { for( i =front; i <=rear; i ++) print(Q[ i ]); } } 12 25 For( i =rear; i =>front; i --) to print the order in reverse manner For(I=front+1;I<rear; I+2)

29. Enqueue operation void Enqueue ( int num ) // num = 10 { n=( struct node *) malloc ( sizeof ( struct node)); N  data = num ; n  next =NULL; if(rear == NULL) front = rear= n; else { rear  next = n; rear = n; } } Linked List Implementation of Queue

30. Dequeue Operation Void Dequeue () { Struct node *t; if (front == NULL) print(“Underflow”); else { t = front; front = front  next ; free(t); } }

31. •Type of queue •Last position of the queue is connected to the first position in a circular fashion •Overcome the disadvantage of wastage of front end memory space after performing dequeue operation in linear queue Circular Queue

32. •In linear queue, after performing dequeue , the memory space at the front end remains unused •This situation does not occur in circular queue Need for Circular Queue

33. void Cir_Enqueue ( int num ) { if((front == 0 && rear == max-1) || (rear ==(front-1))) print(“Queue Overflow”); else if (front == -1 && rear == -1) { front = rear = 0; Q[rear] = num ; } else if (rear == max-1 && front != 0) { rear = 0; Q[rear] = num ; } else { rear ++; Q[rear] = num ; } } Enqueue Operation

34. Void Cir_Dequeue () { if (front ==-1) print (“Queue Underflow”); int val ; if (front == rear) val = Q[front]; free( val ); front = rear = –1; else if (front <= max –1) val = Q[front]; Front++; free( val ); rear->next=front; } Dequeue Operation

35. DEQUE is of two types •Input restricted DEQUE –Insertion at only one end –Deletion at both ends •Output restricted DEQUE –Deletion at only one end –Insertion at both ends Double Ended Queue (DEQUE)

36. •Every item has a priority associated with it •Element with higher priority is served first •If two elements have same priority then they served according to the order in the queue •Generally, the value of the element itself is considered as higher priority • Applications : –CPU scheduling –Graph algorithms like Dijkstra’s shortest path, Prim’s minimum spanning tree, etc ,. Priority Queue

37. A node of a linked list for implementing priority queue will contain three parts − Data − It will store the integer value. Priority −It will store the priority which is an integer value. It can range from 0-10 where 0 represents the highest priority and 10 represents the lowest priority. Address − It will store the address of a next node data priority

38. •Data getting transferred between the IO Buffers (Input Output Buffers). •CPU scheduling and Disk scheduling. •Managing shared resources between various processes. •Job scheduling Applications of Queue

39. • Traffic light functioning is the best example for circular queues . The colors in the traffic light follow a circular pattern. • In page replacement algorithms , a circular list of pages is maintained and when a page needs to be replaced, the page in the front of the queue will be chosen. Applications of Circular Queue

40. Balancing the Symbols Towers of Hanoi Functions calls 8 Queen Problems Applications of Stack

41. Balancing the Symbols

42. Algorithm: Declare a character  stack  S. Now traverse the expression string exp. If the current character is a starting bracket ( ‘(‘ or ‘{‘ or ‘[‘ ) then push it to stack. If the current character is a closing bracket ( ‘)’ or ‘}’ or ‘]’ ) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced. After complete traversal by encounters delimiters # , if there is some starting bracket left in stack then “ not balanced ” Balancing the Symbols

43. Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: 1) Only one disk can be moved at a time. 2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack. 3) No disk may be placed on top of a smaller disk. Towers of Hanoi

44. 2^ N – 1 = 8-1 = 7

45. When a call is made to a new function all the variable local to the calling routine need to be saved, otherwise the new function will overwrite the calling routine variable. Ex: int fact( int n) { ---------- ------- s = n * fact(n-1) return s; } Function Calls

46. N Queen Problem

47. N Queen Problem

48. N Queen Problem Basically, we have to ensure 4 things: 1. No two queens share a column. 2. No two queens share a row. 3. No two queens share a top-right to left-bottom diagonal. 4. No two queens share a top-left to bottom-right diagonal.