4 DSA - Stacks and Queues PDF

Data Structures and Algorithms (CS-2001) KALINGA INSTITUTE OF INDUSTRIAL TECHNOLOGY School of Computer Engineering Strictly for internal circulation (within KIIT) and reference only. Not for outside circulation without permission 4 Credit...

Data Structures and Algorithms (CS-2001) KALINGA INSTITUTE OF INDUSTRIAL TECHNOLOGY School of Computer Engineering Strictly for internal circulation (within KIIT) and reference only. Not for outside circulation without permission 4 Credit Lecture Note  Chapter Contents 2 Sr Major and Detailed Coverage Area Hrs # 3 Stacks and Queues 8 Stacks, Stacks using Dynamic Arrays and Linked Lists, Queues, Queue using Linked List, Circular Queues using Dynamic Arrays, Evaluation of Expressions, Priority Queue, Dequeue School of Computer Engineering Introduction 3 The linear lists and linear arrays allowed one to insert and delete elements at any place in the list – at the beginning, at the end or in the middle. There are certain frequent situations when one wants to restrict insertions and deletions so that they can take place only at the beginning or the end of the list, not in the middle. Two of the data structures that are useful in such situations are stacks and queues. School of Computer Engineering Stack 4 ❑ A stack is a data structure that works on the principle of Last In First Out (LIFO). ❑ Last item put on the stack is the first item that can be taken off. ❑ New elements are added to and removed from the top called the top of the stack. Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from these basic stuffs, a stack is used for the following three primary operations − ❑ push − pushing (storing) an element on the stack. ❑ pop − removing (deleting) an element from the stack. ❑ peek − return the topmost element from the stack. School of Computer Engineering Stack Application 5 ❑ Parsing ❑ Recursive Function ❑ Function Call ❑ Expression Evaluation Expression Representation ❑ Expression Conversion Sr# Expressio Meaning ❑ Infix to Postfix n ❑ Infix to Prefix 1 Infix Characterized by the placement of operators between operands. E.g. plus ❑ Postfix to Infix sign in "2 + 2" ❑ Prefix to Infix 2 Prefix Characterized by the placement of ❑ Towers of Hanoi operators before operands. E.g. plus sign in “+ 2 2" 3 Postfix Characterized by the placement of operators after operands. E.g. plus sign in “ 2 2 +" School of Computer Engineering Stack Representation 6 Stack can be represented using − ❑ Arrays − Storing the items contiguously ❑ Fixed size (called as static stack) ❑ Dynamic size (called as dynamic stack) ❑ Linked List − Storing items non-contiguously ❑ Dynamic size (called as dynamic stack) School of Computer Engineering Stack - Static Array Representation 7 Static Array Declaration & Definition: DEFINE N NUM [NUM represents whole number e.g. In C, equivalent statement is #define N 100] INTEGER STACK[N] INTEGER TOP = 0 Pictorial Representation 1 5 4 Positio n 1 2 3 4 5 6 7 8 TOP 3 TOP = 0 indicates that the stack is empty and TOP = N indicates that the stack is full School of Computer Engineering Stack Operation using Static Array 8 PUSH(STACK, TOP, N, ITEM) ITEM POP(STACK, TOP) 1. Start 1. Start 2. IF TOP = N THEN 2. IF TOP = 0 THEN DISPLAY Overflow DISPLAY Underflow EXIT EXIT END IF END IF 3. TOP = TOP + 1 3. SET ITEM = STACK[TOP] 4. STACK[TOP] = ITEM [Insert Item into new TOP Position] 4. TOP = TOP -1 5. Stop 5. RETURN ITEM 6. Stop PEEK(STACK, TOP, ITEM) ISEMPTY(STACK, TOP) 1. Start 1. Start 2. IF TOP = 0 THEN 2. IF TOP = 0 THEN DISPLAY Underflow DISPLAY Empty EXIT EXIT END IF END IF 3. SET ITEM = STACK[TOP] [Call by reference] 3. DISPLAY Non-Empty 4. Stop 4. Stop School of Computer Engineering Class Work 9 1. Design Push algorithm using dynamic array. 2. Design Pop algorithm using dynamic array. 3. Design an algorithm to realise two stacks in single static array. School of Computer Engineering Stack - Linked List Representation 10 Since all the action happens at the top of the stack, a single linked list is a fine way to represent the stack wherein the header/start always points to the top of the stack. A CC BB X A Represents Top ❑ Pushing is inserting an element at the front of the list ❑ Popping is removing an element from the front of the list Push Before Push A CC BB X A After Push D A CC BB X D A School of Computer Engineering Stack - Linked List Representation 11 Pop Before Pop D A CC BB X D A After Pop A CC BB X A Stack Node Representation struct node { int info; struct node *next; N represents NULL }*top; School of Computer Engineering Push Function 12 void push() { struct node * temp =(struct node *)malloc(sizeof(struct node)); top scanf(“%d”, & temp->info ); top if (top == NULL) { C temp->next = NULL; B } C B else A X PUSH { temp->next = top; X represents NULL A X } top = temp; } School of Computer Engineering Pop Function 13 void pop() { struct node *tempTop = top; top if (tempTop == NULL) top { printf("\n Underflow"); C return; B } B POP tempTop = tempTop ->next; A X printf("\n Popped value : %d", top->info); A X X represents NULL free(top); top = tempTop; } School of Computer Engineering Arithmetic Expression : Polish Notation 14 The way to write arithmetic expression is known as a notation. Polish Notation is a way of expressing arithmetic expressions that avoids the use of brackets to define priorities for evaluation of operators. Polish Notation was devised by the Polish philosopher and mathematician Jan Łukasiewicz (1878-1956) for use in symbolic logic. ❑ Evaluate the following parenthesis-free arithmetic expression 2 î 3 + 5 * 2 î 2 – 12 / 6 = 8 + 5 * 4 – 12 / 6 = 8 + 20 – 2 = 26 An arithmetic expression can be written in three different but equivalent notations, i.e., without changing the essence or output of an expression. These notations are − ❑ Infix Notation ❑ Postfix Notation ❑ Prefix Notation School of Computer Engineering Expression Representation 15 ❑ Infix Notation - We write expression in infix notation, e.g. a - b + c, where operators are used in-between operands. It is easy for us humans to read, write, and speak in infix notation but the same does not go well with computing devices. An algorithm to process infix notation could be difficult and costly in terms of time and space consumption. ❑ Prefix Notation - In this notation, operator is prefixed to operands, i.e. operator is written ahead of operands. For example, +ab. This is equivalent to its infix notation a + b. Prefix notation is also known as Polish Notation. ❑ Postfix Notation - This notation style is known as Reversed Polish Notation. In this notation style, the operator is postfixed to the operands i.e., the operator is written after the operands. For example, ab+. This is equivalent to its infix notation a + b. School of Computer Engineering Difference in 3 Notation 16 Example Sr# Infix Prefix Postfix 1 a+b +ab ab+ 2 (a + b) ∗ c ∗+abc ab+c∗ 3 a ∗ (b + c) ∗a+bc abc+∗ 4 a/b+c/d +/ab/cd ab/cd/+ 5 (a + b) ∗ (c + ∗+ab+cd ab+cd+∗ d) 6 ((a + b) ∗ c) - d - ∗ + a b c d ab+c∗d- School of Computer Engineering Parsing Expression 17 Parsing is the process of analyzing a collection of symbols, either in natural language or in computer languages, conforming to the rules of a formal grammar. It is not a very efficient way to design an algorithm or program to parse infix notations. Instead, these infix notations are first converted into either postfix or prefix notations and then computed. To parse any arithmetic expression, we need to take care of operator precedence and associativity also. Precedence :- When an operand is in between two different operators, which operator will take the operand first, is decided by the precedence of an operator over others. For example − a + b *c a + (b * c) Associativity :- It describes the rule where operators with the same precedence appear in an expression. For example, in expression a + b − c, both + and – have the same precedence, then which part of the expression will be evaluated first, is determined by associativity of those operators. Here, both + and − are left associative, so the expression will be evaluated as (a + b) − c. School of Computer Engineering Parsing Expression cont… 18 Precedence and associativity determines the order of evaluation of an expression. Following is an operator precedence and associativity table (highest to lowest) − Sr# Operator Precedence Associativity 1 Exponentiation (^ or î) Highest Right Associative 2 Multiplication ( ∗ ), Division ( / ) Second Highest Left Associative and Modular Division ( % ) 3 Addition ( + ) & Subtraction ( − ) Lowest Left Associative The above table shows the default behavior of operators. At any point of time in expression evaluation, the order can be altered by using parenthesis. For example − In a + b*c, the expression part b*c will be evaluated first, with multiplication as precedence over addition. We here use parenthesis for a + b to be evaluated first, like (a + b)*c. School of Computer Engineering Arithmetic Expression Conversion 19 Infix expression to Prefix notation (A+B)*C = [+AB]*C = *+ABC where [ ] indicates a partial translation A+(B*C) = A+[*BC] = +A*BC (A+B)/(C-D) = [+AB]/[-CD] = /+AB-CD Infix expression to Postfix notation (A+B)*C = [AB+]*C = AB+C* where [ ] indicates a partial translation A+(B*C) = A+[BC*] = ABC*+ (A+B)/(C-D) = [AB+]/[CD-] = AB+CD-/ Note Order in which the operations are to be performed is completely determined by the positions of the operators and operand in the expression. Accordingly, one never needs parenthesis when writing expression in Polish notations School of Computer Engineering Why Postfix and Prefix? 20 Postfix: Computer usually evaluates an arithmetic expression written in infix notation in two steps: ❑ 1st Step - Converts the infix notation to Postfix notation ❑ 2nd Step - Evaluates the Postfix expression. In each step, stack is the main tool used to accomplish the given task. Prefix: ❑ Has seen wide application in Lisp (programming language) s-expressions ❑ Data Compression with Prefix Encoding ❑ Standard scientific prefixes are used to denote powers of 10 e.g. kilo = 1e3 ❑ mega = 1e6 ❑ tera = 1e12 ❑ exa = 1e18 ❑ giga = 1e 9 ❑ peta = 1e15 School of Computer Engineering Evaluation of a Postfix Expression 21 1. Start 2. Validate the Postfix expression P for correctness a) Operator is after the operands [Binary operators are considered only] 3. Add a right parenthesis ‘)” at the end of P. [This act as delimiter] 4. Scan P from left to right and repeat steps 5 and 6 for each element of P until the delimiter “)” is encountered 5. If an operand is encountered, push it on STACK 6. If an operator is encountered, then (a) Remove the two top elements of STACK, where A is the top element and B is the next-to-top element (b) Evaluate B A (c ) Place the result of step (b) on STACK 7. Set value of the postfix expression equal to the top element of STACK 8. Stop School of Computer Engineering Example 22 ❑ P = 5, 6, 2, + , *, 12, 4, /, - [Postfix] Note – Commas are used to separate the elements of P so that 5,6,2 is not interpreted as 562. P: (after adding a sentinel right parenthesis at the end of P) 5 6 2 + * 12 4 / - ) (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) Symbol Scanned STACK Symbol Scanned STACK (1) 5 5 (7) 4 40 12 4 (2) 6 5 6 (8) / 40 3 (3) 2 5 6 2 (9) - 37 (4) + 5 8 (10) ) (5) * 40 (6) 12 40 12 School of Computer Engineering Class Work 23 Consider the following arithmetic expression P, written in postfix notation: P =12, 7 , 3, - , / , 2, 1, 5, +, *, + 1. Evaluate the above postfix expression 2. By inspection, translate P into its equivalent infix expression 3. Evaluate the converted infix expression School of Computer Engineering Evaluation of a Prefix Expression 24 1. Start 2. Validate the Prefix Expression P for correctness a) Operator is before the operands [Binary operators are considered only] 3. Scan P from right to left and repeat steps 4 and 5 for each element of P until it ends. 4. If an operand is encountered, put it on STACK 5. If an operator is encountered, then (a) Remove the two top elements of STACK, where A is the top element and B is the next-to-top element (b) Evaluate A B (c ) Place the result of step (b) on STACK 6. Set value of the prefix expression equal to the top element of STACK 7. Stop School of Computer Engineering Example 25 P = -, *, +, 4, 3, 2, 5 [Prefix] Note – Commas are used to separate the elements of P - * + 4 3 2 5 (7) (6) (5) (4) (3) (2) (1) Symbol scanned STACK (1) 5 5 (2) 2 5 2 (3) 3 5 2 3 (4) 4 5 2 3 4 (5) + 5 2 7 (6) * 5 14 (7) - 9 School of Computer Engineering Class Work 26 Consider the following arithmetic expression P, written in prefix notation: P = +, 10, *, - , *, 30, 20, *, /, 5, ^, 6, 4, 3, 8, 1. Evaluate the above prefix expression 2. By inspection, translate P into its equivalent infix expression 3. Evaluate the converted infix expression School of Computer Engineering Infix to Postfix Conversion 27 Q is an arithmetic expression written in infix notation. This algorithm InfixToPostfix (Q, P) finds the equivalent postfix notation where P is the equivalent postfix notation – 1. Start 2. Validate the Infix expression for correctness (a) Operator is between the operands [Binary operators are considered only] (b) Brackets ‘(‘ and ‘)’ are properly matched. 3. Push “(“ onto STACK and Insert “)” to the end of Q 4. Scan Q from Left to Right and Repeat Steps 5 to 8 for each element of Q until the STACK is empty 5. If an operand is encountered, add it to P 6. If a left parenthesis is encountered, push it onto STACK 7. If an operator ∅ is encountered, then: (a) Repeatedly pop from STACK and add to P each operator which has same precedence or higher precedence than ∅. (b) Add ∅ to STACK. 8. If a right parenthesis is encountered, then (a) Repeatedly pop from the STACK and add to P each operator until a left parenthesis is encountered. (b) Remove the left parenthesis. [Do not add it to P] 9. Stop School of Computer Engineering Example 28 Q:A+(B*C–(D/E îF)*G)*H So first, we push “(“ onto stack, and then add “)” to the end of the Q to obtain: A + ( B * C - ( D / E î F ) * G) * H ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Symbol Scanned STACK Expression P 1 A ( A 2 + (+ A 3 ( (+( A 4 B (+( AB 5 * (+(* AB 6 C (+(* ABC 7 - (+(- ABC* School of Computer Engineering Example cont… 29 A + ( B * C - ( D / E î F ) * G) * H ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Symbol Scanned STACK Expression P 8 ( (+(-( ABC* 9 D (+(-( ABC*D 10 / (+(-(/ ABC*D 11 E (+(-(/ ABC*DE 12 î (+(-(/î ABC*DE 13 F (+(-(/î ABC*DEF 14 ) (+(- ABC*DEFî/ 15 * (+(-* ABC*DEFî/ 16 G (+(-* A B C * D E F î /G 17 ) (+ ABC*DEFî/G*- 18 * (+* ABC*DEFî/G*- 19 H (+* ABC*DEFî/G*-H 20 ) ABC*DEFî/G*-H*+ Hence, P : A B C * D E F î / G * - H * + School of Computer Engineering Class Work 30 Consider the infix expression Q: ((A + B) * D) î (E-F). Translate Q into its equivalent postfix expression P Symbol Scanned STACK Expression P 1 ( (( 2 ( ((( 3 A ((( A 4 + (((+ A 5 B (((+ AB 6 ) (( AB + 7 * ((* AB + 8 D ((* AB +D 9 ) ( AB +D* 10 î (î AB +D* 11 ( (î( AB+D* 12 E (î( AB+D*E 13 - (î(- AB+D*E F 14 F (î(- AB+D*E F 15 ) (î AB+D*E F– 16 AB+D*E F–î P: A B + D * E F – î School of Computer Engineering Infix to Prefix Conversion 31 Q is an arithmetic expression written in infix notation. This algorithm InfixToPrefix(Q, P) finds the equivalent postfix notation where P is the equivalent prefix notation – 1. Start 2. Validate the Infix expression for correctness (a) Operator is between the operands [Binary operators are considered only] (b) Brackets ‘(‘ and ‘)’ are properly matched. 3. Reverse the infix expression Q 4. CALL InfixToPostfix (Q, P) 5. Reverse the expression P 6. Stop Example: Infix notation: A+B*C Step 1 – Infix expression is correct Step 2 – Reversing the expression resulting to C*B+A Step 3 – Postfix expression produced in step 2 is CB*A+ Step 4 – Reversing the postfix expression produced in step 3 is + A * B C Prefix or P: + A * B C School of Computer Engineering Example cont… 32 Q : (A+B î C)*D+E î F Step 1 – Infix expression is correct Step 2 – a) Reversing the infix expression produce F î E + D * ) C î B + A ( b) Reverse the bracket, so making every '(' as ')' and every ')' as '(‘ revised expression is F î E + D * ( C î B + A ) Step 3 – Postfix expression of step 2 produce F E î D C B î A + * + Step 4 – Reversing the postfix expression produced in step 3 becomes +*+Aî BCDî EF Prefix or P: + * + A î B C D î E F School of Computer Engineering Home Work 33 Read the following at your own pace: ❑ Postfix to Infix conversion – http://scanftree.com/Data_Structure/postfix-to-infix ❑ Prefix to Infix conversion – http://scanftree.com/Data_Structure/prefix-to-infix ❑ Postfix to Prefix conversion – http://see-programming.blogspot.in/2013/05/postfix-to-prefix-conversion.html ❑ Prefix to Postfix conversion – http://www.manojagarwal.co.in/conversion-from-prefix-to-postfix/ School of Computer Engineering Queue 34 ❑ A queue is a data structure that models/enforces the first-come first-serve order, or equivalently the first-in first-out (FIFO) order. ❑ The element that is inserted first into the queue will be the element that will deleted first, and the element that is inserted last is deleted last. ❑ Items are inserted one end (rear end) and deleted from the other end(front end). Queue basic operations are − ❑ enqueue− Insert element at rear ❑ dequeue− Remove element from front ❑ peek − Examine the element at front without removing it from queue School of Computer Engineering Queue Application 35 Operating System ❑ queue of print jobs to send to the printer ❑ queue of programs / processes to be run ❑ queue of network data packets to send Programming ❑ modeling a line of customers or clients ❑ storing a queue of computations to be performed in order Real World ❑ people on an escalator or waiting in a line ❑ cars at a gas station (or on an assembly line) School of Computer Engineering Queue Representation 36 Queue can be represented using − ❑ Static Arrays − Storing the items contiguously ❑ Static Queue due to fixed size ❑ Space is wasted if we use less elements ❑ cannot insert more elements than the array can hold ❑ Dynamic Arrays − Storing the items contiguously ❑ Dynamic queue ❑ Linked List− Storing items non-contiguously ❑ Dynamic queue School of Computer Engineering Queue - Static Array Representation 37 Static Array Declaration & Definition: DEFINE N NUM [NUM represents whole number e.g. In C, equivalent statement is #define N 100] INTEGER QUEUE[N] INTEGER REAR = 0 INTEGER FRONT = 0 Pictorial Representation 1 FRONT 3 REA R 4 8 6 Positio 1 2 3 4 5 6 7 8 n Keeps track of the number of items in the queue and the position of the front element (at the front of the queue), the rear element (at the rear). The position of the front element is stored in the front member variable. The next item is after the first one and so on until the rear of the queue that occurs at the index stored in a member variable called rear. FRONT = 0 and REAR = 0 indicates that the queue is empty and REAR = N indicates that the queue is full School of Computer Engineering Enqueue Operation 38 1 2 3 4 5 6.. FRONT 0. 0 REAR Let’s an element enters the queue… 1 2 3 4 5 6... 1 FRONT 7 1 REAR After a series of insertion, the state of the queue is 1 2 3 4 5 6... 1 FRONT 7 2 1 1 4 REAR 0 2 School of Computer Engineering Enqueue Algorithm 39 LQINSERT(QUEUE, N, FRONT, REAR, ITEM) 1. Start 2. IF (REAR = N) THEN DISPLAY “OVERFLOW” EXIT END IF 3. IF (FRONT = 0 AND REAR = 0) THEN [Queue initially empty] FRONT = 1 REAR = 1 ELSE REAR = REAR + 1 END IF 4. QUEUE[REAR] = ITEM [This inserts new element] 5. Stop School of Computer Engineering Dequeue Operation 40 1 2 3 4 5 6... 1 FRONT 4 8 6 3 REAR Let’s an element leaves the queue 1 2 3 4 5 6... 2 FRONT 4 8 6 3 REAR After a series of deletion , the state of the queue is 1 2 3 4 5 6 FRONT 3 6 3 REAR School of Computer Engineering Dequeue Algorithm 41 ITEM LQDELETE(QUEUE, FRONT, REAR) 1. Start 2. IF FRONT = 0 THEN DISPLAY “UNDERFLOW“ EXIT END IF 3. ITEM = QUEUE[FRONT] 4. IF (FRONT == REAR) THEN [Check if only one element is left] FRONT = 0 REAR = 0 ELSE FRONT = FRONT + 1 [Increment FRONT by 1] END IF 5. RETURN ITEM 6. Stop School of Computer Engineering Queue Linked Representation 42 Nodes connected in a chain by links Node Representation struct node { char *info; struct node *next; }*front, *rear; School of Computer Engineering Enqueue Operation 43 Post Insertion School of Computer Engineering Enqueue Algorithm 44 LLQINSERT(struct node * FRONT, struct node * REAR, ITEM) BEGIN struct list* node= (struct node*)malloc(sizeof(struct node)); node->info = ITEM; node -> next = NULL; IF (FRONT ==NULL) THEN FRONT = node REAR = node ELSE REAR ->next = node REAR = node END IF END School of Computer Engineering Dequeue Operation 45 Post Deletion School of Computer Engineering Dequeue Algorithm 46 ITEM LLQDELETE(struct node * FRONT) BEGIN IF (FRONT = NULL) THEN DISPLAY “Queue Underflow" EXIT END IF struct * node temp = FRONT ITEM = temp->info FRONT = FRONT->next FREE(temp) RETURN ITEM END School of Computer Engineering Class Work 47 1. Design Deque algorithm using dynamic array. 2. Design Enqueue algorithm using dynamic array. School of Computer Engineering Linear Queue Drawback 48 Once the linear queue is full, even though few elements from the front are deleted & some occupied space is relieved, it is not possible to add anymore new elements, as the rear has already reached the queue’s rear most position. Delete 3 elements This situation also says that queue is full and we can not insert the new element because, 'rear' is still at last position. In above situation, even though we have empty positions in the queue we can not make use of them to insert new element. This is the major problem in normal queue data structure. To overcome this problem we use circular queue data structure. School of Computer Engineering Circular Queue 49 Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle and the graphical representation of a circular queue is as follows... In circular queue, once the Queue is full the "First" element of the Queue becomes the "Rear" most element, if and only if the "Front" has moved forward. otherwise it will again be a "Queue overflow" state. Circular Queue can be represented using − Static Array − Storing the items contiguously (fixed size) and avoids the wastage of space in a regular queue implementation using arrays. School of Computer Engineering Circular Queue Enqueue Algorithm 50 CQINSERT(QUEUE, N, FRONT, REAR, ITEM) 1. Start 2. IF (FRONT = 0 AND REAR = 0) THEN FRONT = 1 GOTO STEP 5 END IF 3. IF (FRONT =1 AND REAR = N) OR (FRONT = REAR + 1) THEN DISPLAY “Circular Queue Overflow” EXIT END IF 4. IF (REAR = N) THEN REAR = 1 GOTO STEP 6 END IF 5. REAR = REAR + 1 6. QUEUE[REAR] = ITEM 7. Stop School of Computer Engineering Circular Queue Dequeue Algorithm 51 ITEM CQDELETE(QUEUE, N, FRONT, REAR) 1. Start 2. IF (FRONT == 0) THEN [Continuation of algorithm] DISPLAY “Circular Queue Underflow” 5. IF (FRONT = REAR) THEN EXIT FRONT = 0 END IF REAR = 0 3. ITEM = QUEUE[FRONT] RETURN ITEM 4. IF FRONT = N THEN END IF FRONT = 1 6. FRONT = FRONT + 1 RETRUN ITEM 7. RETURN ITEM END IF 8. Stop School of Computer Engineering Circular Queue Example 52 1. Initially, Rear = 0, Front = 0. 3. Insert 50, Rear = 2, Front = 1. Front Rear 2. Insert 10, Rear = 1, Front = 1. 4. Insert 20, Rear = 3, Front = 1. Rear Front Front Rear School of Computer Engineering Circular Queue Example cont… 53 5. Insert 70, Rear = 4, Front = 1. 7. Insert 100, Rear = 5, Front = 2. Front Front Rear Rear 6. Delete front, Rear = 4, Front = 2. 8. Insert 40, Rear = 1, Front = 2. Front Rear Front Rear School of Computer Engineering Deque 54 ❑ A deque, also known as a double-ended queue, is an ordered collection of items similar to the queue. ❑ It has two ends, a front and a rear. ❑ Insertions and deletions can occur at either end at constant time, but not in the middle. ❑ It does not require the FIFO orderings that are enforced by queue data structure. ❑ Deques are not heavily used. ❑ The dequeue can be constructed in two ways and are: ❑ circular array ❑ circular doubly linked list ❑ You should know what a deque is, but we won’t explore them much further. Circular array School of Computer Engineering Input Restricted and Output Restricted Deque 55 There are 2 types of deque as explain below - Input-restricted Deque (IRD) Elements can be inserted only at one end and can be removed from both the ends O R Output-restricted Deque (ORD) Elements can be removed only at one end and can be inserted from both the ends. O R School of Computer Engineering Insertion Algorithm in Deque 56 DEFINE N NUM //NUM is any number and defined the capacity of array INT FRONT = 0, REAR = 0 ITEM DEQUE[N] //ITEM is of type int/float/char etc Insertion at front Example VOID INSERT_AT_FRONT(ITEM:X) 1. Deque is empty (Front = 0 and Rear = 0) BEGIN IF (FRONT == 1 AND REAR == N) OR (FRONT = REAR + 1) THEN 2. Let's an element 10 is inserted (Front = 1 and Rear = 1) DISPLAY("Deque is Overflow”) 10 RETURN END IF 3. Let's an element 20 is inserted (Front = 6 and Rear = 1) IF (FRONT == 0) THEN 10 20 FRONT = REAR = 1 4. Let's an element 30 is inserted (Front = 5 and Rear = 1) ELSE IF (FRONT == 1) THEN 10 30 20 FRONT = N 5. Let's element 40, 50 and 60 is inserted (Front = 2 ELSE and Rear = 1) FRONT = FRONT - 1 10 60 50 40 30 20 END IF END IF DEQUE[FRONT] = X END School of Computer Engineering Insertion Algorithm in Deque 57 Insertion at rear Example VOID INSERT_AT_REAR(ITEM:X) 1. Deque is empty (Front = 0 and Rear = 0) BEGIN IF (FRONT == 1 AND REAR == N) OR (FRONT = REAR + 1) THEN 2. Let's an element 10 is inserted (Front = 1 and Rear = 1) DISPLAY("Deque is Overflow”) 10 RETURN END IF 3. Let's an element 20 is inserted (Front = 1 and Rear = 2) IF (REAR == 0) THEN 10 20 REAR = FRONT = 1 ELSE 4. Let's an element 30 is inserted (Front = 1 and Rear = 3) IF (REAR == N) THEN 10 20 30 REAR = 1 5. Let's element 40, 50 and 60 is inserted (Front = 1 ELSE and Rear = 6) REAR = REAR +1 10 20 30 40 50 60 END IF END IF DEQUE[REAR] = X END School of Computer Engineering Deletion Algorithm from Deque 58 Deletion from rear Example ITEM DELETE_FROM_REAR() 1. Deque is empty (Front = 0 and Rear = 0) BEGIN IF (REAR == 0) THEN DISPLAY("Deque is Empty and leading to Underflow”) 2. Deque is full (Front = 1 and Rear = 6) RETURN NULL 10 20 30 40 50 60 END IF SET ITEM = DEQUE[REAR] 3. Deletion from Deque (Front = 1 and Rear = 5) IF (REAR == FRONT) THEN 10 20 30 40 50 60 REAR = FRONT = 0 3. Deletion from Deque (Front = 6 and Rear = 1) ELSE 20 10 IF (REAR == 1) THEN REAR = N Front = 6 and Rear = 6 ELSE 20 10 REAR = REAR - 1 END IF 4. Deletion from Deque (Front = 6 and Rear = 6) END IF 10 RETURN ITEM Front = 0 and Rear = 0 END School of Computer Engineering Deletion Algorithm in Deque 59 Deletion from front Example ITEM DELETE_FROM_FRONT() 1. Deque is empty (Front = 0 and Rear = 0) BEGIN IF (FRONT == 0) THEN DISPLAY("Deque is Empty and leading to Underflow”) 2. Deque (Front = 5 and Rear = 2) RETURN NULL 10 20 50 60 END IF SET ITEM = DEQUE[FRONT] 3. Deletion from Deque (Front = 6 and Rear = 2) IF (FRONT == REAR) THEN 10 20 50 60 FRONT = REAR = 0 4. Deletion from Deque (Front = 1 and Rear = 2) ELSE 10 20 10 IF (FRONT == N) THEN FRONT = 1 5. Deletion from Deque (Front = 2 and Rear = 2) ELSE 10 20 FRONT = FRONT +1 END IF 6. Deletion from Deque (Front = 0 and Rear = 0) END IF 20 RETURN ITEM END School of Computer Engineering Input Restricted Dequeue Illustration 60 Enqueue is restricted from rear (i.e. inserting using front) School of Computer Engineering Input Restricted Dequeue Illustration 61 Enqueue is restricted from front (i.e. inserting using rear) School of Computer Engineering Output Restricted Dequeue Illustration 62 Deque is restricted from rear School of Computer Engineering Output Restricted Dequeue Illustration 63 Deque is restricted from front School of Computer Engineering Dequeue Source Code 64 School of Computer Engineering Application of Deque 65 1. A web browser's history. Recently visited URLs are added to the front of the deque, and the URL at the back of the deque is removed after some specified number of insertions at the front. 2. Undo-Redo operation in software application. 3. Palindrome Checker Step 1: Insert with rear Step 2: Remove from front and rear Check with madam or mam School of Computer Engineering Priority Queues 66 A priority queue is a collection of elements such that each element has been assigned a priority and such that the order in which elements are deleted and processed comes from the following rules – ❑ An element of higher priority is processed before any element of lower priority. ❑ Two elements with the same priority are processed according to the order in which they were added to the queue. Examples: ❑ Patients in an emergency room ❑ CPU Scheduling ❑ All queue applications where priority is involved. School of Computer Engineering Types of Priority Queue 67 ❑ Ascending Priority Queue: In this type of priority queue, elements can be inserted into any order but only the element with the smallest priority to be removed. ❑ Descending Priority Queue: In this type of priority queue, elements can be inserted into any order but only the element with largest priority to be removed. School of Computer Engineering Priority Queues Operation & Representation 68 Operation: ❑ insert(item, priority): Inserts an item with given priority. ❑ Peek(): Returns the highest priority item. ❑ dequeue(): Removes the highest priority item. ❑ isFull() − check if queue is full. ❑ isEmpty() − check if queue is empty. Representation: ❑ One-Way List ❑ Heap (Will cover later) ❑ Array ❑ Fixed Size❑ Variable Size School of Computer Engineering Priority Queue - Array Representation 69 ❑ Use array to hold each level of priority. ❑ Each such level of priority must have its own pair of pointers, FRONT and REAR. Both FRONT and REAR appear in its own circular array. ❑ A two–dimensional array is used to hold info and to track FRONT & REAR for each level of priority. ❑ FRONT[K] and REAR[K] contains the front and rear elements of row K of queue, the row that maintains the queue of elements with priority number K Systematic diagram FRONT & REAR Tracker PRN FRONT REAR 1 2 3 4 5 1 2 2 1 A 2 1 3 Priority 2 B C G 3 0 0 3 4 E D 4 5 1 5 F 5 4 4 School of Computer Engineering Priority Queue – Array Representation cont… 70 Insertion with Priority M and ITEM 1. Start 2. ? 3. Stop Deletion 1. Start 2. ? 3. Stop Peek 1. Start 2. ? 3. Stop School of Computer Engineering Priority Queue - One-Way List Representation 71 ❑ Each node in the list would contain three information namely an information field INFO, a priority number field PRN and the address field NEXT. ❑ A node X precedes a node Y in the list when: ❑ X has lower priority than Y or ❑ When both have the same priority but X was added to the list after Y. Systematic diagram HEAD A1 B2 C2 D3 School of Computer Engineering Priority Queue - One-Way List Representation 72 Node Representation Deletion struct node 1. Start { 2. Visit to the second last node in the chain. int info; 3. Make the second last node next field to NULL. int prn; 4. Point the rear to second last node. struct node *next; 5. Free the last node. }*rear, *front; 6. Stop Insertion with Priority N and ITEM 1. Start 2. Traverse the list until finding a node X whose priority number exceeds the priority N. 3. If node found then Insert ITEM in front of node X 4. If no such node is found, insert ITEM as the last item of the list 5. Stop School of Computer Engineering Priority Queue - One-Way List Insertion Algorithm 73 VOID INSERT (HEAD, DATA, PRIORITY) Step 1: Begin Step 2: Create new node with DATA and PRIORITY Step 3: Check if HEAD has lower priority. If true follow Steps 4-6. Else goto Step 7. Step 4: NEW -> NEXT = HEAD Step 5: HEAD = NEW Step 6: End Step 7: Set TEMP to head of the list Step 8: WHILE (TEMP -> NEXT != NULL AND TEMP -> NEXT -> PRIORITY > PRIORITY) TEMP = TEMP -> NEXT END WHILE Step 9: NEW -> NEXT = TEMP -> NEXT Step 10: TEMP -> NEXT = NEW Step 11: End School of Computer Engineering Priority Queue - One-Way List Algorithm 74 VOID DELETE (HEAD) Step 1: Begin Step 2: If head is NULL then return. Step 3: Set the head of the list to the next node in the list. HEAD = HEAD -> NEXT. Step 4: Free the node at the head of the list Step 5: End ITEM PEEK(HEAD) Step 1: Begin Step 2: If head is NULL then return NULL. Step 2: Return HEAD -> INFO Step 3: End School of Computer Engineering Assignments 75 1. Write an algorithm to convert an infix expression into it equivalent postfix expression. Explain the execution of algorithm using the expression (A+B)*C–(D*E)î(F+G+(H*M)) 2. Write C functions for insertion, deletion, traversal operation for circular queues 3. Write C functions for insertion, deletion, traversal operation for input restricted deques 4. Write C functions for insertion, deletion, traversal operation for output restricted deques 5. Write an algorithm to copy the data elements of one stack to other without changing the order and without using any other data structure 6. Write C functions for insertion, deletion, traversal operation for priority queues 7. Write an algorithm to check for balanced parentheses (, ), {, }, [ and ] in an expression 8. Write recursive pseudo code or recursive function to display the string in reverse order. 9. Write an algorithm to convert postfix expression to infix expression. 10. Write an algorithm to convert prefix expression to infix expression. 11. Given stack data structure, implement queue using only given stack data structure. 12. Given queue data structure, implement stack using only given queue data structure. School of Computer Engineering Assignments cont… 76 13. Write an algorithm or c code segment for insertion, deletion, peek and traversal of priority queue using dynamic arrays. 14. Write an algorithm or c code segment for insertion, deletion, peek and traversal of priority queue using linked list. 15. Write an algorithm or c code segment to reverse the queue 16. Write an algorithm or c code segment to reverse the first k elements in the queue 17. The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: Only one disk can be moved at a time. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack. No disk may be placed on top of a smaller disk. Design an iterative and recursive algorithm or write a C program School of Computer Engineering Assignments cont… 77 18. Write an algorithm or c code segment to implement 2 queues using static array. 19. In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions. 20. Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit. For example, consider the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 1, 6}. The largest possible rectangle possible is 12 (see the below figure, the max area rectangle is highlighted in red) School of Computer Engineering 78 School of Computer Engineering Home Work (HW) 79 1. You are given 2 queues where each queue contains timestamp pair price. You have to print < price 1 price 2 > for all those timestamps where abs(ts1 – ts2)