DSA Module 3 [Lesson 2] - Stack - PDF

DATA STRUCTURES and ALGORITHM MODULE 3 [Lesson 2] First Semester College of Computer Studies – Calapan City Campus QUOTE OF THE DAY  STACK Implementation LESSON 2 and Operations At the end of this lesson, the students must have: Applied the use...

DATA STRUCTURES and ALGORITHM MODULE 3 [Lesson 2] First Semester College of Computer Studies – Calapan City Campus QUOTE OF THE DAY  STACK Implementation LESSON 2 and Operations At the end of this lesson, the students must have: Applied the use of stack operations; Learning Evaluated expression using stacks; OUTCOMES And simulated programs on stack Figure 25. Stack of Plates  STACKs A STACK is an Abstract Data Type (ADT) commonly used in programming languages. It is named after Stack since it could be seen in real-life situation. It is also an ordered list of similar data types. The operation only takes place at one end known as TOP. It also has a feature of Last-In First-Out (LIFO) or in reverse First In, Last Out (FILO).  STACKs The last data inserted is the first data to process. Figure 25. Stack of Plates In stack, inserting is called PUSH and removing is POP. In Fig.25, the first method is to PUSH or insert a plate to the stack at the end, then POP a plate at end also. In this situation, we could consider two different states: underflow and overflow. Underflow takes place when the stack is completely empty, while Overflow takes place when the stack is completely full.  BASIC Oper Following are the basic operations of Stack: 1. PUSH() – storing the element to stack. 2. POP() – removing the element to stack. But, in order to do these operations, we need to use some METHODS of stack. 1. PEEK() - looking/getting for the top of the stack without removing the element. 2. isFULL() – checking if the stack is full. 3. isEMPTY() – checking if the stack is empty.  PROPERTIES & METHODS a.Count()-Property b.Push(T)-Method c.Peek()-Method d.Pop()-Method e.Contains(T) -Method f. Clear()-Method  ALGORITHM & PSEUDOCODE PUSH: The process of putting a new data element onto stack is known as a Push Operation. Algorithm for PUSH() operation 1. Check if stack is FULL or not. 2. If FULL, print overflow and exit the program, else 3. INCREMENT the top and add the element.  ALGORITHM & PSEUDOCODE 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 data element Algorithm for POP() operation 1. Check if stack andisdeallocates EMPTY or not. memory space. 2. If EMPTY, print underflow and exit the program, else 3. Print the element on top and DECREMENT.  ALGORITHM & PSEUDOCODE Pseudocode for PEEK() 1. begin procedure peek 2. return stack[top] 3. end procedure Pseudocode for isFULL() Pseudocode for isEMPTY() 1. begin procedure isFULL 1. begin procedure isEMPTY 2. if top equivalent to MAXSIZE, 2. if top less than 1, return TRUE, else return TRUE, else 3. return FALSE 3. return FALSE 4. end procedure 4. end procedure ALGORITHM & PSEUDOCODE  STACKs _ Research Infix, Prefix and Postfix in Data Structure. Write the prefix and postfix of this expression 4 + 7 * 2 / 2 ASSIGNMENT