stack

Unit 3 Stack and Queue : 

Unit 3 Stack and Queue Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

3.1 Why Stacks ? : 

Expression evaluation stacks were the first kind of stacks to be widely supported by special hardware. As a compiler interprets an arithmetic expression, it must keep track of intermediate stages and precedence of operations using an evaluation stack. In a compiled language, the compiler keeps track of the pending operations during its instruction generation, and the hardware uses a single expression evaluation stack to hold intermediate results. To see why stacks are well suited to expression evaluation, consider how the following arithmetic expression would be computed: X = (A + B) * (C + D) 3.1 Why Stacks ? Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 3: 

The solution to the recursion problem is to use a stack for storing the subroutine return address. The local variable stack The parameter stack Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

What is Stack? : 

It is Linear Data Structure Concept is Last in First out : LIFO Insertions and Deletions are Done from the Same end, which is called as the top of the stack. Inserting an element to the stack is called Push operation Deleting an element from the stack is called as pop operation What is Stack? Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Push and Pop : 

Push and Pop top empty stack push an element push another pop Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Stack Terminiologies : 

Need to declare an array size ahead of time Associated with each stack is Top of Stack we call it as Top for an empty stack, set Top to -1 Push (1)   Increment Top by 1. (2)   Set Stack[Top] = X Pop (1)   Set return value to Stack[TopOfStack] (2)   Decrement TopOfStack by 1 Stack Terminiologies Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Implementation of Stacks : 

Any list implementation could be used to implement a stack Arrays (static: the size of stack is given initially) Linked lists (dynamic: never become full) We will explore implementations based on array and linked list Let’s see how to use an array to implement a stack first Implementation of Stacks Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

objects: a finite ordered list with zero or more elements. methods: for all stack  Stack, item  element, max_stack_size  positive integer Stack createS(max_stack_size) ::= create an empty stack whose maximum size is max_stack_size Boolean isFull(stack, max_stack_size) ::= if (number of elements in stack == max_stack_size) return TRUE else return FALSE Stack push(stack, item) ::= if (IsFull(stack)) stack_full else insert item into top of stack and return : 

objects: a finite ordered list with zero or more elements. methods: for all stack  Stack, item  element, max_stack_size  positive integer Stack createS(max_stack_size) ::= create an empty stack whose maximum size is max_stack_size Boolean isFull(stack, max_stack_size) ::= if (number of elements in stack == max_stack_size) return TRUE else return FALSE Stack push(stack, item) ::= if (IsFull(stack)) stack_full else insert item into top of stack and return Stack ADT Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Boolean isEmpty(stack) ::= if(stack == CreateS(max_stack_size)) return TRUE else return FALSEElement pop(stack) ::= if(IsEmpty(stack)) return else remove and return the item on the top of the stack. : 

Boolean isEmpty(stack) ::= if(stack == CreateS(max_stack_size)) return TRUE else return FALSEElement pop(stack) ::= if(IsEmpty(stack)) return else remove and return the item on the top of the stack. Stack ADT (cont’d) Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Array-based Stack Implementation : 

Array-based Stack Implementation Allocate an array of some size (pre-defined) Maximum N elements in stack Bottom stack element stored at element 0 last index in the array is the top Increment top when one element is pushed, decrement after pop Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Stack createS(max_stack_size) ::= #define MAX_STACK_SIZE 100 /* maximum stack size */ typedef struct { int key; /* other fields */ } element; element stack[MAX_STACK_SIZE]; int top = -1; Boolean isEmpty(Stack) ::= top< 0; Boolean isFull(Stack) ::= top >= MAX_STACK_SIZE-1; : 

Stack createS(max_stack_size) ::= #define MAX_STACK_SIZE 100 /* maximum stack size */ typedef struct { int key; /* other fields */ } element; element stack[MAX_STACK_SIZE]; int top = -1; Boolean isEmpty(Stack) ::= top< 0; Boolean isFull(Stack) ::= top >= MAX_STACK_SIZE-1; Stack Implementation: CreateS, isEmpty, isFull Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

void push(element item){ /* add an item to the global stack */ if (top >= MAX_STACK_SIZE-1) { stack_full( ); return; } stack[++top] = item;} : 

void push(element item){ /* add an item to the global stack */ if (top >= MAX_STACK_SIZE-1) { stack_full( ); return; } stack[++top] = item;} Push Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

element pop(){ /* return the top element from the stack */ if (top == -1) return stack_empty( ); /* returns and error key */ return stack[(top)--]; } : 

element pop(){ /* return the top element from the stack */ if (top == -1) return stack_empty( ); /* returns and error key */ return stack[(top)--]; } Pop Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 14: 

Void stackFull() { printf” (“ Stack Full , push not possible \n”); exit(Exit_Failure); } Stack Full Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

3.2 Stack Using Dynamic arrays : 

In the array representation, we need to know, at compile time, a good bound (MAX_STACK_SIZE) on how large the stack will become We can use a dynamically allocated array for elements and then increasing the size of this array as needed 3.2 Stack Using Dynamic arrays Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 16: 

Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 17: 

We must alter the code for the push function to use the new test for a full stack; the code for the pop function is unchanged. The code for stackFull is also changed Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 18: 

Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Applications of Stack : 

Evaluation of expression Types of Expressions: Infix, Prefix & Postfix Infix: a+b Prefix: +ab Pstfix: ab+ Four things in an expression : 1 Operand 2 Operator 3 Precedence 4 Associativity Applications of Stack Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Arithmetic Expressions: Operators : 

Arithmetic Expressions: Operators A unary operator has one operand A binary operator has two operands A ternary operator has three operands Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 21: 

What is the order in which the operations are performed? The precedence determines the order in which we evaluate operators The associativety indicates how we evaluate operators with the same precedence Parentheses override precedence, and expressions are evaluated from the innermost parenthesized expression first Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Arithmetic Expressions: Operator Precedence Rules : 

Arithmetic Expressions: Operator Precedence Rules The operator precedence rules for expression evaluation define the order in which “adjacent” operators of different precedence levels are evaluated Typical precedence levels parentheses unary operators, +, - Chart *, / +, - Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 23: 

The operator associativity rules for expression evaluation define the order in which adjacent operators with the same precedence level are evaluated Left to right & right to left Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Infix to Postfix Conversion : : 

Scan the Infix string from left to right. Initialize an empty stack. If the scanned character[symb] is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character to stack. If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack(topStack). If topStack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character. Infix to Postfix Conversion : Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 25: 

Repeat this step till all the characters are scanned. If stack is not empty add top Stack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty. If the scanned character is left parentheses, push it onto the stack. If the scanned character is right parenthesis, the symbol at the top of the stack is popped off the stack and copied to the Postfix Expression. Repeat until the symbol at the top of the stack is a left parenthesis Return the Postfix string. Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Pseudocode : 

opstk= the empty stack; while(not end of input) { symb=next input character; if (symb is an operand) Add symb to postfix string else while (!empty(opstk)&& prcd(stacktop(opstk),symb) { topsymb=pop(opstk); add topsymb to the postfix string; }/* end while */ Push (opstk,symb); } /* end of else */ } /* output any remaining operators */ While(!empty (opstk(( { topsymb=pop(opstk)) Add topsymb to the postfix string; } /* end while */ Pseudocode Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

How the algorithm works.. Lets see : 

How the algorithm works.. Lets see Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Infix String : a+b*c-d : 

Infix String : a+b*c-d Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Infix String : a+b*c-d : 

Infix String : a+b*c-d Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Infix String : a+b*c-d : 

Infix String : a+b*c-d Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Postfix String : abc*+d- : 

Postfix String : abc*+d- Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 32: 

Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Examples : 

Infix string : A * B + C / D Postfix string: A B * C D / + Infix A * (B + C) / D Postfix:A B C + * D / Infix: A * (B + C / D) Postfix:A B C D / + * Examples Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 34: 

Scan for the given postfix expression from left to right  one element at a time. Check whether it is an operand or an operator. If it is an operand the n push the element in to stack and if it is an operator then pop the two element from the stack. Apply the given operator on them and then push back the returned result in to the stack.    Repeat the step 1 to 3 until the whole postfix expression comes to the end. 5 Pop the element from the stack which should be the only element  in the stack and return it from the function as the result of the expression. Steps to Evaluate the Postfix expression Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 35: 

Opndstk=the empty stack; /*scan the input string */ /* One element at a time in to symb */ While(not of input) { symb=next input char; if(symb is an operand) Push(opndstk,symb) else /* symb is an operator */ opnd2=pop(opndstk); Opnd1=pop(opndstk); Value=result of applying symbol to op1, op2 Push(opndstk,value); } end of else } end of while Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Postfix string is 123*+4- : 

Postfix string is 123*+4- Initially the Stack is empty. Now, the first three characters scanned are 1,2 and 3, which are operands. Thus they will be pushed into the stack in that order. Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Next character scanned is "*", which is an operator. Thus, we pop the top two elements from the stack and perform the "*" operation with the two operands. The second operand will be the first element that is popped. : 

Next character scanned is "*", which is an operator. Thus, we pop the top two elements from the stack and perform the "*" operation with the two operands. The second operand will be the first element that is popped. Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

The value of the expression(2*3) that has been evaluated(6) is pushed into the stack. : 

The value of the expression(2*3) that has been evaluated(6) is pushed into the stack. Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Next character scanned is "+", which is an operator. Thus, we pop the top two elements from the stack and perform the "+" operation with the two operands. The second operand will be the first element that is popped. : 

Next character scanned is "+", which is an operator. Thus, we pop the top two elements from the stack and perform the "+" operation with the two operands. The second operand will be the first element that is popped. Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

The value of the expression(1+6) that has been evaluated(7) is pushed into the stack : 

The value of the expression(1+6) that has been evaluated(7) is pushed into the stack Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Next character scanned is "4", which is added to the stack. : 

Next character scanned is "4", which is added to the stack. Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Next character scanned is "-", which is an operator. Thus, we pop the top two elements from the stack and perform the "-" operation with the two operands. The second operand will be the first element that is popped. : 

Next character scanned is "-", which is an operator. Thus, we pop the top two elements from the stack and perform the "-" operation with the two operands. The second operand will be the first element that is popped. Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

The value of the expression(7-4) that has been evaluated(3) is pushed into the stack. : 

The value of the expression(7-4) that has been evaluated(3) is pushed into the stack. Now, since all the characters are scanned, the remaining element in the stack (there will be only one element in the stack) will be returned.  End result :Postfix String : 123*+4- Result : 3 Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

3.3 Queues : 

A queue is an ordered list in which insertions and deletions take place at different ends The end at which new elements are added is called the rear, and that from which old elements are deleted is called the front A queue is a First-In-First-Out (FIFO)list Q 3.3 Queues Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Add and delete operations : 

Add and delete operations Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Q as an ADT : 

Q as an ADT Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Creating a Queue : 

Creating a Queue Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 48: 

Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

3.5 Adding an element to Linear Queue : 

3.5 Adding an element to Linear Queue Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

3.6 Deleting an element from Linear queue : 

3.6 Deleting an element from Linear queue Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Example 3.2 Job scheduling : 

If OS does not use priorities, the jobs are processed in the order they enter the system As jobs enter and leave the system, the queue gradually shifts to the right If the queue is full, queueFull should move the entire queue to the leftmost (very time-consuming) Example 3.2 Job scheduling Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Example contd… : 

Example contd… Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

3.6 Circular Queues : 

3.6 Circular Queues A more efficient queue representation: permit a queue to wrap around the end of the array front=0,rear=0 Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

3.7 Adding an element to the circular Queue : 

3.7 Adding an element to the circular Queue Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

3.8 Deleting an Element from a Circular Queue : 

3.8 Deleting an Element from a Circular Queue Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Circular Queues Using Dynamically Allocated Arrays : 

To add an element to a full queue, we must first increase the size of the array using a function such as realloc. As with dynamically allocated stacks, we use array doubling. In this case, it is not sufficient to simply double array size using realloc Circular Queues Using Dynamically Allocated Arrays Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 57: 

Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

3.8 A Mazing Problem : 

A maze is a series of wall making dead ends, entrys and exits to get out in and around the maze Mazes present a nice application of stacks The most obvious choice of the maze representation is a two-dimensional array in which zeros represent the open paths and ones the barriers Mazes are often used in psychology experiments to study spatial navigation and learning. Such experiments typically use rats or mice. 3.8 A Mazing Problem Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 59: 

Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 60: 

Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 61: 

Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 62: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 63: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 64: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 65: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 66: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 67: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 68: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 69: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 70: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 71: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 72: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 73: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 74: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 75: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 76: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 77: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 78: 

0 1 2 0 1 2 Allowable Moves Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Not every position has eight neighbors. To avoid checking for these border conditions we can surround the maze by border of ones : 

Not every position has eight neighbors. To avoid checking for these border conditions we can surround the maze by border of ones Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

3.10 Move Representation : 

typedef struct { int vert; int horiz; }offsets; offsets move[8]; /* array of moves for each direction*/ Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore 3.10 Move Representation

To find the position of the Next Move : 

Maze[nextRow][nextCol] we get Nextrow=row+move[dir].vert; Nextcol=col+move[dir].horiz; To find the position of the Next Move Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Representation of Mazes : 

# define maxsize 100 typedef struct { short int row; short int col; short int dir; }element; element stack[maxsize] Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore Representation of Mazes

To find the position of the Next Move : 

Maze[nextRow][nextCol] we get Nextrow=row+move[dir].vert; Nextcol=col+move[dir].horiz; To find the position of the Next Move Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Representation of Mazes : 

# define maxsize 100 typedef struct { short int row; short int col; short int dir; }element; element stack[maxsize] Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore Representation of Mazes

Slide 85: 

Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Multiple Stacks : 

If we have n stacks, we can divide the available memory into n segments The initial division may be done in proportion to the expected sizes of the various stacks, if this is known. Otherwise, we may divide the memory into equal segments Multiple Stacks Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 87: 

Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

Slide 88: 

Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

3.16 Push Operation : 

3.16 Push Operation Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore

3.17 Pop function : 

3.17 Pop function Mr J V Gorabal Assoc Prof CSE SCEM, MAngalore