Data Structures and Algorithms: Stacks - CC4 Finals Reviewer PDF

Data Structures and Algorithms STACKS  ▪ Understand the basic concepts and architecture of stacks data structure ▪ Comprehend the algorithms for push(x), pop( ), top ( ), isEmpty( ) and other relative operations. ▪ Implement Stack...

Data Structures and Algorithms STACKS  ▪ Understand the basic concepts and architecture of stacks data structure ▪ Comprehend the algorithms for push(x), pop( ), top ( ), isEmpty( ) and other relative operations. ▪ Implement Stack data structure on different data structures such as Objectives arrays, linked-list, reverse strings, balance parentheses, and infix and postfix structure. ▪ Describe relative advantages and disadvantages of stack data structures.  ▪ A stack is also known as a Last-In-First-Out (LIFO) list. ▪ A stack is a linear structure in which items are added or removed only at one end the top. ▪ The depth of stack is the number of elements it contains. ▪ ▪AnComprehend empty stack the has algorithms depthfor push(x), pop( ), top ( ), isEmpty( ) and other zero. relative operations. ▪ Homogenous Introduction to ▪ Elements are ordered Stacks ▪ Stack user cannot have direct access to data items inside the stack ▪ Only topmost item can be retrieved ▪ Can hold any number of data items (in principle), however, there is an upper limit to stack size depending on the memory space  STACK ADT. (Abstract Data Type) A ▪ list with the Comprehend therestriction algorithms forthat insertion push(x), pop( ), topand deletion ( ), isEmpty( can ) and be other relative operations. performed only from one end, called the top. Introduction to Stacks  Operations Push (x) – Insert or push some item “x” onto the stack. Before thistheoperation, ▪ Comprehend thepush(x), algorithms for stackpop( if ),often top ( ),checked if itother isEmpty( ) and has enoughoperations. relative capacity to accommodate the new item If stack is full, an overflow would occur Operations Pop( ) – Removing the most recent item or element from the stack. Must ensure that the stack is not empty before this operation If stack contains no item, popping would cause an underflow error  Top( ) – Returns the copy of the item or element at the top of the stack. The item itself is not removed from the stack This operation is also called peek Comprehend ▪IsEmpty( thereturn ) – It will algorithms true ifforthe push(x), stack pop( ), topfalse is empty, ( ), isEmpty( ) and other otherwise. relative operations. Normally applied before the pop operation to avoid stack undeflow Operations IsFull()- – It will return true if the stack is full, false otherwise. Normally applied before the push operation to avoid stack overflow Not used when dynamic memory allocation is used  Create - generates an empty stack object and reserves necessary storage space ▪ Comprehend the algorithms for push(x), pop( ), top ( ), isEmpty( ) and other relative operations. Destroy – removes all elements from the stack and releases memory allocated to stack Operations  A stack is a linear data structure in which Definition of insertions and deletions are allowed only Stack at the end, called the top of the stack.   When we defined a stack as an ADT (or Abstract Data Type), then we are only interested knowing the stack operations from the user point of view. Stack as an ADT  Therefore, we are not interested in knowing the implementation details at this moment. We are only interested in knowing what type of operations we can perform on stack.   push (data) : Inserts data onto stack Primary  pop (data): Deletes the last inserted element Operations from the stack   top(): returns the last inserted element without removing it. Secondary  size(): returns the size or the number of elements in the stack. Operations  isEmpty(): returns TRUE if the stack is empty, else returns FALSE.  isFull(): returns TRUE if the stack is full, else returns FALSE.  push(1) push(2) First push(3) Command pop() isFull()  Operations (Example) ▪ Comprehend the algorithms for push(x), pop( ), top ( ), isEmpty( ) and other relative operations. Operations isEmpty( ) = True isEmpty( ) = False  Algorithm of peek( ) Return Value Algorithm of peek() 5 ▪ Comprehend the algorithms for push(x), pop( ), top ( ), isEmpty( ) and other relative operations. 6 Operations Implementation of peek() function. 7 8 9  Algorithm of isFull( ) FALSE Algorithm of isFull() Implementation of isFull() ▪ Comprehend the algorithms for push(x), pop( ), top ( ), isEmpty( ) and other function. relative operations. Operations 7 8 9  Algorithm of isEmpty( ) TRUE FALSE Algorithm of isEmpty() ▪ Comprehend Implementation the algorithms of isEmpty() for push(x), pop( ), top ( ), isEmpty( ) and other relative operations. function. Operations 8 9  The process of putting a new data element onto stack is known as a Push Operation. Push operation involves a series of steps − Step 1 − Checks if the stack is full. Step 2 − If the stack is full, produces an error and exit. Algorithm of Step 3 − If the stack is not full, increments top to point next empty space. Step 4 − Adds data element to the stack location, where top is pointing. push( ) Step 5 − Returns success.  1.) PUSH(20) Algorithm of push( ) cont. 2.) PUSH(30) Algorithm of push() Implementation of push() 20 function. 7 Operations 8 10 11  Algorithm of pop( ) Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of pop() operation, the data element is not actually removed, instead top is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually removes Algorithm of data element and deallocates memory space. pop( ) 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.  1.) POP() Algorithm of pop( ) cont. 2.) POP() Algorithm of pop() Implementation of pop() Algorithm of function. pop( ) 10 Data Structures and Algorithms STACKS  ▪ Understand the basic concepts and architecture of stacks data structure ▪ Comprehend the algorithms for push(x), pop( ), top ( ), isEmpty( ) and other relative operations. ▪ Implement Stack data structure on different data structures such as Objectives arrays, linked-list, reverse strings, balance parentheses, and infix and postfix structure. ▪ Describe relative advantages and disadvantages of stack data structures. Implementation Schemes Array-based implementation Linked list-based implementation Array Implementation: STACK  simplified version of the array based list. The only important design decision to be made is which end of the array should represent the top of the stack. One choice is to make the top be at position 0 in the array. Array Inefficient implementation because now every push or pop operation will require that all elements currently in the stack be Implementation shifted one position in the array, for a cost of Θ(n) if there are n elements. as elements are pushed onto the stack, they are appended to the tail of the list. Method pop removes the tail element. In this case, the cost for each push or pop operation is only Θ(1).  Array Implementation of Stacks An array of appropriate data type is used to store stack data Size of array determines the maximum number of data Array elements in the stack Implementation A variable top is used to identify the topmost element The elements of stack are placed in a sequential order in of Stacks the array When an element is pushed onto stack, top is incremented by 1 When an element is popped off, top is decremented by 1 Array Implementation of Stacks  Array Implementation int A 22 10 75 top  -1 //empty stack 0 1 2 3 4 5 6 7 8 9 Array Push(x) { Implementation top  top + 1 Operation: A[top]  x Push(2) of Stacks } Push(10) Pop( ) Push(5) { Pop ( ) top  top -1 Push(7) } Example #2  C++ example Example #2  Size of stack needs to be specified at compile time If an application requires less space than the array size, storage space will be wasted The program will crash if application requires more storage space at runtime Disadvantages of Array Implementation of Stacks Linked-List Implementation: STACK Stacks  Linked-List Implementation Elements are inserted and removed only from the head of the list. A header node is not used because no special-case code is required for lists of zero or one elements. The only data member is top, a pointer to the first (top) link node of the stack. Linked-List Method push first modifies the next field of the newly created link node to Implementation point to the top of the stack and then sets top to point to the new link node. Method pop is also quite simple. Variable temp stores the top nodes’ value, while ltemp links to the top node as it is removed from the stack. The stack is updated by setting top to point to the next link in the stack. The old top node is then returned to free store (or the freelist), and the element value is returned  Linked list Implementation of Stacks The data elements are stored as nodes and pointers Linked-List Implementation  Linked-List Implementation next Linked-List Implementation head elem node tail A B C D  Push 1. Create a new node 2. Copy element to the new node 3. Link pointer of new node is set to point to pre-existing front node 4. Head pointer is re-set to point to the new node Linked-List Implementation  Pop 1. Topmost element is copied for removal 2. A new pointer is created to point to front mode 3. Head pointer is reset to point to the next node 4. Using the new pointer, front node is deleted Linked-List Implementation  Operations ▪ insertFront(x): inserts an element on the front of the list ▪ removeFront(): returns and removes the Linked-List element at the front of the list Implementation ▪ insertBack(x): inserts an element on the back of the list ▪ removeBack(): returns and removes the element at the end of the list  insertFront(x) : inserts an element on the front of the list. 1) Allocate a new node 2) Have new node point to old head 3) Update head to point to new node Linked-List Implementation head tail  X X A B C D  removeFront(): returns and removes the element at the front of the list. 1) Update head to point to next node in the list. 2) Return element of previous head and delete the node. Linked-List head head tail Implementation X A B C D  insertBack(x): inserts an element on the back of the list. 1) Allocate a new node 2) If tail is NULL, update head and tail to point to the new node; otherwise. Have the old tail point to the new node.  Linked-List Update tail to point to new node. Implementation head tail X tail   removeBack(): returns and removes the element at the end of the list. 1) No efficient way of doing. 2) Typically would not use a linked-list if this operation is commonly used Linked-List Implementation head tail  Linked-List Example # 2  Stacks are extensively used in computer science and other disciplines Stacks play a central role in the following situations Translating and computing high-level computer languages Implementing recursive procedures and recursive functions Implementing search and traversal algorithms Stacks are also used by Text editors, Web browsers and Application packages Stack Applications RECURSION STACK Perhaps the most common computer application that uses stacks is not even visible to its users. This is the implementation of subroutine calls in most programming language runtime environments. A subroutine call is normally implemented by placing necessary information about the subroutine (including the return address, parameters, and local variables) onto a stack. This information is called an activation record. Further subroutine calls add to the stack. Each return from a subroutine pops the top activation record off the stack. Recursion Implementation Implementing recursion with a stack. β values indicate the address of the program instruction to return to after completing the current function call. On each recursive function call to fact, both the return address and the current value of n must be saved. Each return from fact pops the top activation record off the stack. Recursion Example Here, we simply push successively smaller values of n onto the stack until the base case is reached, then repeatedly pop off the stored values and multiply them into the result. Reverse String STACK  Array String O O H EL L EL H O \0 L 0 1 2 3 4 5 Reverse String L Left to Right Rule E Implementation H Fill the stack from index to index.Left to Right Rule Stack Fill the array with LIFO (Stack) rule for reversing.  Balance Parentheses STACK  Parentheses are used in arithmetic expressions to specify priority of evaluation in a valid expression, ‘(‘ match with a corresponding ‘)’ The following expression has the same number of ‘)’ and ‘(‘ , but it is illegal. A+)+(C+D)+( Using Stack for We can use a stack to validate an expression using Parentheses the following algorithm Matching 1. Scan the expression from left to right 2. If ‘(‘ is encountered, push it onto the stack 3. If ‘)’ is found, pop the stack 4. If stack is empty, report a mismatched ‘)’ 5. If stack is not empty at the end of the scan, report mismatching error  Expression Balanced? )( NO [()] YES Balance [{]} NO Parentheses [()()] YES Implementation Solution: = Last un-closed, first closed. Scan from left to right. If its an opening symbol, add it to a list. If its a closing symbol, remove the last opening symbol from the list.  exp = “ { ( ) ( ) }“ Balance Parentheses Implementation ( { S  Array scheme is suitable for stacks with fixed number of data items. Its implementation is simple. By contrast, the linked list implementation is complex but flexible It involves creation and deletion of front node It is preferable when size is unpredictable In both implementations, amount of storage space is proportional to number of elements In Big-Oh notation, space efficiency of either implementation is O(N) Performance of Stack Implementation  In array implementation, all stack operations involve manipulating only the first element It is independent of the number of elements in the array Time efficiency is O(1) List-based implementation also involves manipulating a single node at the front It is independent of the number of nodes thus time efficiency is O(1) Delete operation has time efficiency of O(N), because N nodes are deleted to release storage space Performance of Stack Implementation Performance of Stack Implementation ▪ Helps manage the data in particular way (LIFO) which is not possible with Linked list and array. ▪ When function is called the local variables are stored in stack and destroyed once returned. Stack is used when variable is not used outside the function. ▪ It gives control over how memory is allocated and deallocated. ▪ Stack frees you from the burden of remembering to cleanup(read delete) the object ▪ Not easily corrupted (No one can easily inset data in middle) Advantages of Stacks ▪ Stack memory is limited. ▪ Creating too many objects on the stack will increase the chances of stack overflow ▪ Random access not possible Disadvantages of Stacks  An algebraic expression is a legal combination of operands and the operators.  Operand is the quantity (unit of data) on which a mathematical operation is performed.  Operand may be a variable like x, y, z or a constant like 5, 4,0,9,1 etc.  Operator is a symbol which signifies a mathematical or logical operation between the operands. Example of familiar operators include +,-,*, /, ^  An example of expression as x+y*z. Algebraic Expression  INFIX: the expressions in which operands surround theoperator, e.g. x+y, 6*3 etc this way of writing the Expressions is called infix notation.   POSTFIX: Postfix notation are also Known as Reverse Polish Notation (RPN). They are different from the infix and prefix notations in the sense that in the postfix notation, operator comes after the operands, e.g. xy+, xyz+* etc.   PREFIX: Prefix notation also Known as Polish notation. In the prefix notation, operator comes before the operands, e.g. +xy, *+xyz etc. Algebraic Expression How do you figure out the operands of an operator? a + b * c a * b + c / d This is done by assigning operator priorities. priority(*) = priority(/) > priority(+) = priority(-) When an operand lies between two operators, the operand associates with the operator that has higher priority. Operator Priorities When an operand lies between two operators that have the same priority, the operand associates with the operator on the left. a + b – c a * b / c / d Tie Breaker Sub expression within delimiters is treated as a single operand, independent from the remainder of the expression. (a + b) * (c – d) / (e – f) AB+CD-*EF-/ xyz in prefix and xy/z* in postfix. Both prefix and postfix notations make Expression Evaluation a lot easier.  So it is easier to evaluate expressions that are in these forms. Infix Expression is Hard To Parse Examples of infix to prefix and postfix 1. Scan the infix expression from left to right 2. When an operand is encountered, append it to the output string 3. Push each ‘(‘ onto the stack 4. When an operator is encountered, push it onto the stack if stack is already empty 5. Otherwise, pop operator of greater or equal precedence 6. Continue popping until either ‘)’ is encountered or operator of lower precedence is found 7. When ‘)’ is encountered, pop off the stack 8. Continue with this procedure until a matching ‘(‘ is encountered 9. Push the new operator onto stack 10. At the end, pop off all operators and append them to output string Algorithm for converting infix notation to postfix notation Postfix notation is another way of writing arithmetic expression. In postfix notation, the operator is written after the two operands. infix: 2+5 postfix: 2 5 + Expressions are evaluated from left to right. Precedence rules and parentheses are never needed!! Examples of infix to prefix and postfix Suppose that we would like to rewrite A+B*C in postfix Applying the rules of precedence, we obtained. 1. Examine the next element in the input. 2. If it is operand, output it. 3. If it is opening parenthesis, push it on stack. 4. If it is an operator, then a) If stack is empty, push operator on stack. b) If the top of stack is opening parenthesis, push operator on stack c) If it has higher priority than the top of stack, push operator on stack. d) Else pop the operator from the stack and output it, repeat step 4 5. If it is a closing parenthesis, pop operators from stack and output them until an opening parenthesis is encountered. pop and discard the opening parenthesis. 6. If there is more input, go to step 1 7. If there is no more input, pop the remaining operators to output. Algorithm for Infix to Postfix Why? No brackets necessary! Postfix Examples Suppose we want to convert 2*3/(2-1)+5*3 into Postfix form 1. Each operator in a postfix string refers to the previous two operands in the string. 2. Suppose that each time we read an operand we push it into a stack. When we reach an operator, its operands will then be top two elements on the stack 3. We can then pop these two elements, perform the indicated operation on them, and push the result on the stack. 4. So that it will be available for use as an operand of the next operator. Evaluation a postfix expression 1. Use a stack to evaluate an expression in postfix notation. 2. The postfix expression to be evaluated is scanned from left to right. 3. Variables or constants are pushed onto the stack. 4. When an operator is encountered, the indicated action is performed using the top elements of the stack, and the result replaces the operands on the stack. Evaluation a postfix notation 1. Initialise an empty stack 2. While token remain in the input stream a) Read next token b) If token is a number, push it into the stack c) Else, if token is an operator, pop top two tokens off the stack, apply the operator, and push the answer back into the stack 3. Pop the answer off the stack. Evaluating a postfix expression Question: Evaluate the following expression in postfix : 623+-382/+*2^3+) 6, 2+3 = 5, 6-5=1 3, 8/2=4, 3+4=7 7x1=7 7^2=49, 49+3=52 Approach: Use Stacks  Operator stack: This stack will be used to keep operations (+, -, *, /, ^) Order of precedence of operations– 1. ^ (Exponential) 2. public int linearSearch(int[] list, int target) { for(int i = 0; i < list.length; i++) if( list[i] == target ) return i; return -1; } Searching in a Sorted List If items are sorted then we can divide and conquer dividing your work in half with each step generally a good thing Sorting A fundamental application for computers Done to make finding data (searching) faster Sorting Categories 1. Internal Sorting – The data collection to be sorted is kept in the main memory. 2. External Sorting – The sorting of data stored on secondary devices. Data is sorted in the main memory and written back to the secondary device. Bubble Sort Bubble sort is the simplest iterative algorithm operates by comparing each item or element with the item next to it and swapping them if needed. In simple words, it compares the first and second element of the list and swaps it unless they are out of specific order. Similarly, Second and third element are compared and swapped, and this comparing and swapping go on to the end of the list. The number of comparisons in the first iteration are n-1 where n is the number elements in an array. The largest element would be at nth position after the first iteration. And after each iteration, the number of comparisons decreases and at last iteration only one comparison takes place. Bubble Sort Videos\Bubble.mp4 Bubble Sort Advantages and Disadvantages of Bubble Sort Advantages Disadvantage/s It is easy to understand Sorting takes a long time Easy to implement No demand for large amounts of memory Once sorted, data is available for processing Bubble Sort: Performance The best-case scenario is depicted by O(n). In this instance, the algorithm executes in a time directly proportional to the size of the array. The worst-case scenario of its operation occurs when the array needs to be 'reverse sorted' and is depicted by O (n^2) where the time increases exponentially as the number of sorted elements increase. Bubble Sort: Implementation Bubble Sort: Efficiency The Bubble sort is the simplest sorting algorithm. But it is also the slowest of all. Let’s have a look about its efficiency. Let’s have an array of size 10 to be sorted. In the first pass of the loop it makes 9 comparisons, and with the second pass it makes 8 comparisons, and so on, down to one comparison on the last pass. So, for 10 items, it makes: 9+8+7+6+5+4+3+2+1 = 45 Selection Sort Selection sort has achieved slightly better performance and is efficient than bubble sort algorithm. Suppose we want to arrange an array in ascending order then it functions by finding the largest element and exchanging it with the last element and repeat the following process on the sub-arrays till the whole list is sorted. In selection sort, the sorted and unsorted array does not make any difference and consumes an order of n2 (O(n2)) in both best- and worst-case complexity. Videos\Selection.mp4 Selection sort is faster than Bubble sort. Selection Sort 35 65 30 60 20 scan 0-4, smallest 20 swap 35 and 20 20 65 30 60 35 scan 1-4, smallest 30 swap 65 and 30 20 30 65 60 35 scan 2-4, smallest 35 swap 65 and 35 20 30 35 60 65 scan 3-4, smallest 60 swap 60 and 60 20 30 35 60 65 done Advantages and Disadvantages of Selection Sort Advantages Disadvantages The main advantage of the The primary disadvantage of the selection sort is that it performs selection sort is its poor efficiency well on a small list. when dealing with a huge list of items. Because it is an in-place sorting The selection sort requires n- algorithm, no additional squared number of steps for temporary storage is required sorting n elements. beyond what is needed to hold the original list. Its performance is easily Quick Sort is much more efficient influenced by the initial than selection sort ordering of the items before the sorting process. Selection Sort: Performance Selection sort loops over indices in the array; for each index, selection sort calls indexOfMinimum and swap. If the length of the array is nnn, there are nnn indices in the array. Since each execution of the body of the loop runs two lines of code, you might think that 2 n2n2, n lines of code are executed by selection sort. But it is not true! Remember that indexOfMinimum and swap are functions: when either is called, some lines of code are executed. Selection Sort: Implementation Key Differences Between Bubble Sort and Selection Sort 1. In the bubble sort, each element and its adjacent element is compared and swapped if required. On the other hand, selection sort works by selecting the element and swapping that element with the last element. The selected element could be largest or smallest depending on the order i.e., ascending or descending. 2. The worst-case complexity is same in both the algorithms, i.e., O(n2), but best complexity is different. Bubble sort takes an order of n time whereas selection sort consumes an order of n2 time. 3. Bubble sort is a stable algorithm, in contrast, selection sort is unstable. 4. Selection sort algorithm is fast and efficient as compared to bubble sort which is very slow and inefficient. Bubble Sort Vs Selection Sort Comparison Chart Insertion Sort Insertion sort is a simple sorting algorithm that allows for efficient, in-place sorting of the array, one element at a time. By in-place sorting, we mean that the original array is modified, and no temporary structures are needed. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part. Algorithm To sort an array of size n in ascending order: 1. Iterate from arr to arr[n] over the array. 2. Compare the current element (key) to its predecessor. 3. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element. Insertion Sort Advantages and Disadvantages of Insertion Sort Advantages Disadvantages The main advantage of the insertion sort is The disadvantage of the insertion sort is that it its simplicity. does not perform as well as other, better sorting algorithms It also exhibits a good performance when With n-squared steps required for every n dealing with a small list. element to be sorted, the insertion sort does not deal well with a huge list. The insertion sort is an in-place sorting The insertion sort is particularly useful only algorithm, so the space requirement is when sorting a list of few items minimal. Implementation of Insertion Sort 1. The first step is to create a method that takes in input the array to be sorted, sort arr as seen in line 3 in the code above. 2. The second step is to create an outer for loop which will iterate over each element of the array as shown in line 5. 3. The third step is to create a separate iterator, j which will check for the ascending order of elements in the list, as shown in line 7. 4. The fourth step is the inner while loop: As shown in line 9 the while loop must satisfy two conditions: the value of j must be greater than 0, and the value at index j-1, must be greater than the value at index j. If this condition holds true then, as shown from lines 11 to 14, the key is set to the value at index j. Then the values at j and j-1 are swapped. The value of j is reduced by 1 and the loop continues till one of the conditions breaks. 5. This continues for every iteration of the outer for loop till that also breaks. Merge Sort A merge sort is a type of a divide and conquer algorithm used to sort a given array; this means that the array is divided into halves and then further sub-divided till division can no longer take place. This happens when you reach a single element array as that has no middle to further divide the array on. Each divided sub-array is then sorted and subsequently merged with other sub-divisions. The sorted merge continues till all divisions of the array have been merged, giving us a sorted array. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. See following C implementation for details. Videos\Merge.mp4 Merge Sort Advantages and Disadvantages of Merge Sort Advantages Disadvantages It can be applied to files of Requires extra space »N any size. Reading of the input during Merge Sort requires more the run-creation step is space than other sort. sequential ==> Not much seeking. If heap sort is used for the Merge sort is less efficient in-memory part of the than another sort merge, its operation can be overlapped with I/O Implementation of Insertion Sort Language libraries often have sorting algorithms in them Java Arrays and Collections classes C++ Standard Template Library Python sort and sorted functions Hybrid sorts when size of unsorted list or portion of array is small use insertion sort, otherwise use O(N log N) sort like Quicksort of Mergesort Many other sorting algorithms exist. CLOSURE ACTIVITY& EVALUATION