Module 2 - Data Structures (3).pdf

DATA STRUCTURES AND ALGORITHM CS 213 Module 2: Stack Page 1 TITLE: DATA STRUCTURES AND ALGORITHMS Course Overview This course pack is specifically produced for the course Data Structure intended for the students of SDSSU Cantilan Campus...

DATA STRUCTURES AND ALGORITHM CS 213 Module 2: Stack Page 1 TITLE: DATA STRUCTURES AND ALGORITHMS Course Overview This course pack is specifically produced for the course Data Structure intended for the students of SDSSU Cantilan Campus enrolled in the Bachelor of Science in Computer Science (BSCS) program. This is the second module for the prelim period. Considering the description of the course, this course pack tries to incorporate discussions on Stacks. General Instruction This module begins with an Introduction that encapsulates the topics or lessons that students of this course have to learn, understand and value. The next part is the course direction where students are directed to focus their respective course. Each student taking this course is also required to answer all the assessment to measure whether the student have learned from the lessons. Academic Integrity Academic honesty is required of all students. Plagiarism--to take and pass off as one’s own work, the work or ideas of another--is a form of academic dishonesty. Penalties may be assigned for any form of academic dishonesty” (See Student Handbook/College Manual). Sanctions for breaches in academic integrity may include receiving a grade of a “Failed” on a test or assignment. In addition, the Director of Student Affairs may impose further administrative sanctions. Stack This module covers the following topics: Basic Concept of Stack Designing and Building the Stack Class Stack Operation Module 2: Stack Page 2  Implementation of Stack Operation Run time Stack INTENDED LEARNING OUTCOMES At the end of the lesson, the student should be able to:  Explain the basic concepts and operations on the ADT stack  Implement the ADT stack using sequential and linked representation  Discuss applications of stack: the pattern recognition problem and conversion from infix to postfix  Explain how multiple stacks can be stored using one-dimensional array Introduction Consider the following problems: Problem 1: For a poker game; on any turn, a player may discard a single card from his hand to the top of the pile, or he may retrieve the top card from the discard pile. Is there an appropriate data type to model this discard pile??? Problem 2: Is there an appropriate data type to model this parking lot??? Module 2: Stack Page 3  Stack Stack is a linearly ordered set of elements having the discipline of last-in, first out, hence it is also known as LIFO list. It is similar to a stack of boxes in a warehouse, where only the top box could be retrieved and there is no access to the other boxes. Also, adding a box means putting it at the top of the stack. Adding an item to a stack is referred to as pushing that item onto the stack Removing an item from the stack is referred to as popping the stack The name "stack" for this type of structure comes from the analogy to a set of physical items stacked on top of each other. This structure makes it easy to take an item off the top of the stack, while getting to an item deeper in the stack may require taking off multiple other items first. Considered as a linear data structure, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure, referred to as the top of the stack. This data structure makes it possible to implement a stack as a singly linked list and a pointer to the top element. A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space to accept an entity to be pushed, the stack is then considered to be in an overflow state. The pop operation removes an item from the top of the stack. Module 2: Stack Page 4  The following are the operations on a stack: Getting the size Checking if empty Getting the top element without deleting it from the stack Insertion of new element onto the stack (push) Deletion of the top element from the stack (pop) Designing and Building a Stack class The basic functions are: Constructor: construct an empty stack Empty(): Examines whether the stack is empty or not Push(): Add a value at the top of the stack Top(): Read the value at the top of the stack Pop(): Remove the value at the top of the stack Display(): Displays all the elements in the stack Select position 0 as top of the stack Model with an array Let position 0 be top of stack Problem … consider pushing and popping Requires much shifting Module 2: Stack Page 5 Select position 0 as bottom of the stack A better approach is to let position 0 be the bottom of the stack Thus our design will include An array to hold the stack elements An integer to indicate the top of the stack Implementation of the Operations Constructor: Create an array: (int) array[capacity] Set myTop = -1 Empty(): check if myTop == -1 Push(int x): Module 2: Stack Page 6  if array is not FULL (myTop < capacity-1) myTop++ store the value x in array[myTop] else output “out of space” Top(): If the stack is not empty return the value in array[myTop] else: output “no elements in the stack” Pop(): If the stack is not empty myTop -= 1 else: output “no elements in the stack” Use of Stack in Function calls Whenever a function begins execution, an activation record is created to store the current environment for that function Current environment includes the values of its parameters, contents of registers, the function’s return value, local variables address of the instruction to which execution is to return when the function finishes execution (If execution is interrupted by a call to another function) Functions may call other functions and thus interrupt their own execution, some data structure must be used to store these activation records so they can be recovered and the system can be reset when a function resumes execution It is the fact that the last function interrupted is the first one reactivated Module 2: Stack Page 7  It suggests that a stack can be used to store these activation records A stack is the appropriate structure, and since it is manipulated during execution, it is called the run-time stack. Run-time Stack OS denotes that when execution of main() is completed, it returns to the operating system Use of Run-time Stack When a function is called … Copy of activation record pushed onto run-time stack Module 2: Stack Page 8  Arguments copied into parameter spaces Control transferred to starting address of body of function Summary  A stack is a linearly ordered set of elements obeying the last-in, first-out (LIFO) principle  Two basic stack operations are push and pop  Stacks have two possible implementations – a sequentially allocated one- dimensional array (vector) or a linked linear list  Stacks are used in various applications such as pattern recognition, lists and tree traversals, and evaluation of expressions  Two or more stacks coexisting in a common vector results in better memory utilization  Memory reallocation techniques include the unit-shift method and Garwick's algorithm Module 2: Stack Page 9 ASSESSMENT TASK Lecture Exercises 1. Given the following stack. Perform its operation. Push Push Pop Push Pop Pop 110 15 89 95 71 63 97 115 ? ? ? ? Programming Exercises 1. Write a Java program that checks if parentheses and brackets are balanced in an arithmetic expression. (you can use any java app.) References Books:  Java Education and Development Initiative, (2012). Data Structure.  Shaffer, Clifford A. (2011). Data Structure and Algorithm Analysis in Java. Dover Publications, Inc.  Goodrich, M.T., Tamassia, R. (2008). Data Structures and Algorithms in JAVA, 5th Edition. John Wiley and Sons, Inc.  Drozdek, A., (2005). Data Structures and Algorithms in Java. 3rd Edition. Addison-Wesley. Module 2: Stack Page 10 Internet Sources:  http://www.cs.cornell.edu/courses/cs211/2006fa/lecturenotes.html  http://www.cs.berkeley.edu/~jrs/61b/  http://java.sun.com/docs/book/performance/1st edition/html/JPAlgorithms.fm.html  http://sites.google.com/site/bassamhaddadsite/lecture-notes-Data- Structures-Java Note: Write your answers on short bond paper. It should be handwritten, write it neatly, and avoid erasure. To send your output, you can send it to the drop box located in your barangay, if you have an internet connection, you can take a picture of your answers and send it in google classroom and messenger. Just make sure that the photos that you will send will be in good quality. Don’t forget to write your name and the date. Deadline: A week after the student received the module. INSTRUCTOR INFORMATION Name : FAE MYLENE M. ETCHON E-mail Address : [email protected] Contact Number : 09096347033 Consultation Hours : 1:00 – 5:00 PM MWF Mode of Teaching/Learning Delivery : Blended Learning Tools/Platforms : Schoology LMS/Zoom/Messenger Module 2: Stack Page 11