DSA-G3-Handouts PDF - Data Structures and Algorithms

Data Structures and Algorithms Group 3 Report: __STACK__ Definition of Stack - Is a linear data structure that holds a linear, ordered sequence of elements. It is an abstract data type. It works on the LIFO (Last in First...

Data Structures and Algorithms Group 3 Report: __STACK__ Definition of Stack - Is a linear data structure that holds a linear, ordered sequence of elements. It is an abstract data type. It works on the LIFO (Last in First Out) process in which insertion and deletion are allowed only at the end, called the top of the stack. - To implement a Stack, it is required to maintain a pointer to the top of the Stack, which is the last element to be inserted because we can access the elements only on the top of the stack. - Its size can be fixed or changed dynamically. Stacks can be represented by means of Array, Linked List, and etc. - Is a storage device for storing information in a manner of LIFO (Last in First Out). Types of Stacks 1. Register Stack - Uses CPU registers as its location for stack operations. It’s typically much faster because registers are part of the CPU. - Offers faster access and manipulation due to the proximity of registers to the CPU. - Its size is limited by the number of registers available in the CPU. Typically holds only a small number of values. 2. Memory Stack - Uses main memory (RAM) as its location for stack operations. Accessing memory is slower than accessing registers. - Slower due to additional time required to access data from memory. - Its size is limited only by the available system memory, allowing for much larger stack size. Basic Terminologies in Stack Data Structure 1. IsEmpty - a function that checks if the stack has no elements. 2. IsFull - a function that checks if the stack has reached its maximum capacity. 3. Top - the index or reference to the most recently added element in the stack. 4. Size - the maximum number of elements that the stack can hold. 5. Underflow - an error condition that occurs when attempting to pop an element from an empty stack. 6. Overflow - an error condition that occurs when attempting to push an element onto a full stack. 7. Null - the Stack is empty. 8. Max-1 - the Stack is full.  Stack Operations 1. PUSH OPERATION - implies the insertion of new element into a Stack. A new element is always inserted from the topmost position of the Stack; thus, we always need to check if the top is empty or not, i.e., TOP=Max-1 if this condition goes true, it means the Stack is full, and no more elements can be inserted, and even if we try to insert the element, a Stack overflow message will be displayed. 2. POP OPERATION - means to delete an element from the Stack. Before deleting an element, make sure to check if the Stack Top is NULL, i.e., TOP=NULL. If this condition goes true, it means the Stack is empty, and no deletion operation can be performed, and even if we try to delete, then the Stack underflow message will be generated. 3. PEEK OPERATION - when we need to return the value of the topmost element of the Stack without deleting it from the Stack, the Peek Operation is used. This operation first checks if the Stack is empty, i.e., TOP = NULL; if it is so, then an appropriate message will display, else the value will return.  Stack Applications Function Call Stack - A call stack is the stack that holds all the function calls, with the bottom elements as the main function. It contains information of the active functions of the program. It is also called the program stack. - Before understanding the working of a function call, we need some prerequisite knowledge about Program Execution in the CPU, Stack, Stack Pointer, and Stack Frame. 1. Stack — is a linear data structure that follows the LIFO (Last In First Out) or FILO (First In Last Out) policy of data insertion and deletion. It can be visualized as a group of elements stacked over one another and only the top element is accessible. 2. Stack Pointer — is the pointer that points to the top of the stack. It will always point to the stack frame of the function currently being executed. 3. Stack Frame — is the buffer memory that is the element of the call stack. It is a collection of all the local variables, function parameters, return address, and all the data related to the called function.  Example: - The system will reserve memory for each of them, but we can have only one running at a time, so one might wonder, how does the computer know which function to run first? - We cannot run main without running greet and can’t run greet if we don’t run print. And this is where the stack data structure comes in handy. When a function is called it becomes active and we push its frame on top of the call stack. Additionally, each time a new function is invoked we immediately push its frame on top of the stack and it becomes the active frame. This way we ensure that there is only one active function at a time, making the process thread safe. - When a function finishes its execution, we pop its frame. And since the stack frame contains a return address pointing to the stack frame of the function that is called it, we can easily go switch back to the parent function. That is the beauty of the stack structure.  Expression Evaluation a. Infix Expression: - Typical human-readable format.  Evaluation Principle: 1. Start from Left to Right. 2. Follow Operator Precedence (PEMDAS) - Parenthesis - Exponents - Multiplication and Division (from left to right) - Addition and Subtraction (from left to right) 3. Evaluate expressions inside parenthesis first. 4. Evaluate from left to right for equal precedence operators. b. Postfix Notation: - Operators follow operands. In evaluating using a stack: read from left to right.  Stack-Based Infix to Postfix Notation Conversion: 1. Initialize an empty stack for operators and an empty list for the output postfix expression. 2. Scan the infix expression from left to right. 3. If the scanned character is an operand, append it to the postfix list. 4. If the scanned character is an operator: - If the precedence of the current scanned operator is higher than the precedence of the operator on top of the stack, or if the stack is empty, or if the stack contains a ‘(‘, then push the current operator onto the stack. - Else, pop all operators from the stack that have precedence higher than or equal to that of the current operator. After that push the current operator onto the stack. 5. If the scanned character is '(', push it onto the stack. 6. If the scanned character is ')', pop the stack and append to the postfix list until '(' is encountered. Discard both parentheses. 7. Repeat steps 2-6 until the entire infix expression is scanned. 8. Pop any remaining operators from the stack and append them to the postfix list.  Example Conversion Infix Expression: 1x2/2-3x4+8 Character Stack Output 1 Null 1 x x 1 2 x 12 / / 12x 2 / 12x2 - - 12x2/ 3 - 12x2/3 X -x 12x2/3 4 -x 12x2/34 + + 12x2/34x- 8 + 12x2/34x-8 12x2/34x-8+   Stack-Based Postfix Notation Evaluation: 1. Scan the Postfix Expression from left to right. 2. If the current character is an operand push it onto the stack. 3. If the current character is an operator, pop two operands from the stack, apply the operation, and push the result onto the stack. 4. Repeat steps 2-3 until the end of the expression is reached. 5. The final result is the only element left on the stack. Postfix Expression: 1 2 x 2 / 3 4 x - 8 + Character Stack Output 1 1 2 12 x 12 1x2 = 2 2 22 / 22 2/2 = 1 3 13 4 134 x 134 3x4 = 12 - 1 12 1-12 = -11 8 -11 + 8 -11 8+-11 -3 c. Prefix Notation: - Operators precede operands. In evaluating using a stack: read from right to left.  Stack-Based Infix to Prefix Notation Conversion: 1. Reverse the Infix Expression: - Start by reversing the infix expression. Swap left and right parentheses. 2. Convert Reversed Infix to Postfix: - Enclosed the highest-precedence operator and its operands. - Use the standard infix-to-postfix conversion algorithm on the reversed expression. 3. Reverse the Postfix Expression: - Finally, reverse the postfix expression to get the prefix notation.  Example Conversion Infix Expression: 1x2/2-3x4+8 Reversed Infix Expression: 8+(4x3)-(2/2x1) Character Stack Output 8 Null 8 + + 8 ( +( 8 4 +( 84 x +(x 84 3 + 843x - +- 843x ( +-( 843x 2 +-( 843x2 / +-(/ 843x2 2 +-(/ 843x22  x +-(/x 843x22 1 +-(/x 843x221 ) 843x221x/-+ +-/x122x348  Stack-Based Prefix Notation Evaluation: 1. Scan the Prefix Expression from right to left. 2. If the current token is an operand push it onto the stack. 3. If the current token is an operator, pop two operands from the stack, apply the operation, and push the result onto the stack. 4. Repeat steps 2-3 until the end of the expression is reached. 5. The final result is the only element left on the stack. Prefix Expression: + - / x 1 2 2 x 3 4 8 Character Stack Output 8 8 4 84 3 843 x 8 4x3 = 12 8 12 2 8 12 2 2 8 12 2 2 1 8 12 2 2 1 x 8 12 2 1x2 = 2 / 8 12 2/2 = 1 - 8 1-12 = -11 + -11+8 = -3 -3  REFERENCES Admin. (2024, February 16). Stacks and its applications for gate: Data Structures. BYJUS. https://byjus.com/gate/stack-and-its-applications/ Simplilearn. (2023, February 20). Stack implementation using array in data structures. Simplilearn.com. https://www.simplilearn.com.cach3.com/tutorials/data-structure-tutorial/stack-implementation-using- array.html#google_vignette Agarwal, T. (2021, August 11). Stack pointer : Types, applications, and operations of Stack. ElProCus. https://www.elprocus.com/what-is-stack-stack-pointer-types-operations-its-application/ YouTube. (n.d.). YouTube. https://www.youtube.com/watch?v=ctMn5ul5mQ4 GeeksforGeeks , & GeeksforGeeks. (2024, October 17). Convert infix expression to postfix expression. GeeksforGeeks. https://www.geeksforgeeks.org/convert-infix- expression-to-postfix-expression/ GeeksforGeeks. (2024, September 11). Function call stack in C. https://www.geeksforgeeks.org/function- call-stack-in-c/ Hristov, W. by: H. (2023, March 20). The call stack. Baeldung on Computer Science. https://www.baeldung.com/cs/call-stack Group 3 Group Leader: Bulos Edrian O. Group Members: Jenifer F. Razon Maureen P. Guadalquiver Jan Carlo B. Rabe Danryl James B. Usa Glowen Tanaman Rench F. Auxtero Axcel Xyron M. Sebrero