Unit II - LINEAR DATA STRUCTURES

STACK - QUEUE

1. VELAMMAL ENGINEERING COLLEGE An Autonomous Institution, Affiliated to Anna University Chennai, & Approved by AICTE Delhi Department of Computer Science and Engineering UNIT II - LINEARDATASTRUCTURES–STACKS,QUEUES Dr.M.Usha , AP

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(Last In First Out) or FILO(First In Last Out).               

3. WHY STACK? Stack in PL: The return address (when the function is complete it returns back to the function call) Arguments passed to the function Local variables of the function Hardware Implementation of stack: consists of reserved contiguous region of memory with a stack pointer into that memory. The stack has a fixed location in memory at which it begins. The stack pointer is a hardware register that points to the current extents of the stack. There are stacks that grow downwards and ones that grow upwards. The stack can technically be located anywhere in memory, depending on the system.

4. WHY STACK? Usage in Microprocessors The stack shares the available RAM memory with the heap and the static memory area. The C runtime library takes care of things that need to be defined before the main() function can be executed. One of those things is setting up the stack by loading the stack pointer register with the start address of the stack. The CPU has special instructions for pushing values onto the stack and popping them back.

5. Implementation of stack 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. struct stack { int stk [MAXSIZE]; int top; };

6. Implementation using 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; }; struct Node* top;

7. Drawback of Linked List implementation All the operations take constant time Calls to malloc and free are expensive especially in comparison to the pointer manipulation routines. Limitation of Array Implementation: The stack cannot grow and shrink dynamically as per the requirement.

8. Operations on Stack The basic operations on stack are 1.Push() 2.Pop()

9. Push() operation push() function is used to insert an element at the top of the stack. The element is added to the stack container and the size of the stack is increased by 1. Before Performing Push() operation the stack condition to be checked for overflow. int isfull () { if(top == MAXSIZE) return 1; else return 0; }

10. STEP 1 START STEP 2 Store the element to push into array STEP 3 Check if top== (MAXSIZE-1) then stack is full else goto step 4 STEP 4 Increment top as top = top+1 STEP 5 Add element to the position stk [top]=num STEP 6 STOP

11. Step 1 − Checks if the stack is empty. Step 2 − If the stack is empty, produces an error and exit. Step 3 − If the stack is not empty, accesses the data element at which top is pointing. Step 4 − Decreases the value of top by 1. Step 5 − Returns success. int pop() { int data; if(! isempty ()) { data = stack[top]; top = top - 1; return data;} else { printf ("Could not retrieve data, Stack is empty.\n"); }}

12. Pop() operation Deletion of an element from the top of the stack is called pop operation. The value of the variable top will be incremented by 1 whenever an item is deleted from the stack. The top most element of the stack is stored in an another variable and then the top is decremented by 1. The operation returns the deleted value that was stored in another variable as the result. Before performing pop() operation the stack condition must be checked for underflow. int isempty () { if(top == -1) return 1; else return 0; }

13. Program Execution https://www.tutorialspoint.com/data_structures_algorithms/stack_program_in_c.htm

14. Applications of Stack Evaluating Arithmetic Expression Conversion of infix to Postfix expression Backtracking Procedure During Function call and return Procedure

15. Evaluating Arithmetic Expression 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

16. Reverse Polish notation(postfix notation) – It refers to the analogous 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 (-)

17. 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. The procedure for getting the result is: Convert the expression in Reverse Polish notation( post-fix notation). Push the operands into the stack in the order they are appear. When any operator encounter then pop two topmost operands for executing the operation. After execution push the result obtained into the stack. After the complete execution of expression the final result remains on the top of the stack.

18. Infix notation: (2+4) * (4+6) Post-fix notation: 2 4 + 4 6 + * Result: 60

19. Conversion of infix to postfix 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.

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+.

21. Algorithm 1. Scan the infix expression from left to right. 2. If the scanned character is an operand, output it. 3. Else, …..3.1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it. …..3.2 Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.) 4. If the scanned character is an ‘(‘, push it to the stack. 5. If the scanned character is an ‘)’, pop the stack and and output it until a ‘(‘ is encountered, and discard both the parenthesis. 6. Repeat steps 2-6 until infix expression is scanned. 7. Print the output 8. Pop and output from the stack until it is not empty.

22. Linked List Implementation - Initial Stack

23. Linked List Implementation-Push()

24. void pop() { struct Node* temp; if (top == NULL) { printf ("\ nStack Underflow“); exit(1); } else { temp = top; top = top->link; temp->link = NULL; free(temp); } }

25. Queue ADT Mrs. G. Sumathi Assistant Professor Velammal Engineering College Chennai

26. Agenda Queue ADT Array implementation of queue Linked list implementation of queue Types Circular Queue Double Ended Queue Priority Queue Applications of Queue

27. Queue ADT 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 )

28. Operations in queue: 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 Queue ADT

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

30. Dequeue Operation Void Dequeue () { int val ; if (front == -1 || front > rear) print(“Queue Underflow”); else { val = Q[front]; front++; } } 10 20 30

31. Display Operation void Display () { int i ; if (front == -1 || front > rear) print (“Queue Underflow”); else { for( i =front; i <=rear; i ++) print(Q[ i ]); } }

32. Linked List Implementation of Queue Enqueue operation v oid Enqueue ( int num) { 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; } }

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

34. Circular Queue 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

35. 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

36. Enqueue Operation 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; } } 30 40 50 60 70

37. Dequeue Operation Void Cir_Dequeue () { int val ; if (front ==-1) print (“Queue Underflow”); val = Q[front]; if (front == rear) front = rear = – 1; else if (front == max – 1) front = 0; else front ++; } 20 40 20 30 20 30 40

38. Double Ended Queue (DEQUE) 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

39. Priority Queue 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,.

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

41. 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

42. Queries??

43. Thank You !!!