combinepdf-min.pdf

Stacks CHAPTER 3 Objectives Students are expected to: Define stack data structure Identify the different ways to represent stack Examine the stack operation algorithms Apply stack operation algorithms in converting mathematical expressions Compare the difference of queue and stack data stru...

Stacks CHAPTER 3 Objectives Students are expected to: Define stack data structure Identify the different ways to represent stack Examine the stack operation algorithms Apply stack operation algorithms in converting mathematical expressions Compare the difference of queue and stack data structure Stacks A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is named stack as it behaves like a real-world stack, for example in the picture shown below. Stacks An ordered list where all operations are restricted at one end of the list known as the TOP. The last element inserted into the stack will always be the first one processed. This type of behavior in list processing is called LIFO or Last-in-First-Out. Stacks Representation There are several ways to represent a stack: (1) as a one-dimensional array, (2) structure, (3) pointer, (4) linked list. Algorithm for PUSH operation Algorithm for POP operation STACK APPLICATIONS Evaluation of Expressions Infix Notation is characterized by the sequence: operand operator operand Example: C + D Postfix Notation is characterized by the sequence: operand operand operator Example: C D + Operator Precedence 1. Parentheses ( ) – highest precedence 2. Multiplication * and Division / → Equal but higher precedence than addition & subtraction 3. Addition + and Subtraction – → Equal but lower precedence if compared to multiplication and division **We will consider only {+, −,∗,/, } operators, other operators are neglected. Convert the infix notation to its equivalent postfix notation: Infix notation: A+B*C/D Stack Postfix Array Rules in Converting Infix to Postfix Notation: Step 1: Assign one-dimensional array for the postfix notation to be derived. Step 2: Read each symbols of the given infix notation, from left to right manner. 2.1 If the symbol is operand, move to postfix array. 2.2 If the symbol is operator or parenthesis, proceed to step 3. Infix notation: A+B*C/D Postfix Array Stack Rules in Converting Infix to Postfix Notation: Step 1: Assign one-dimensional array for the postfix notation to be derived. Step 2: Read each symbols of the given infix notation, from left to right manner. 2.1 If the symbol is operand, move to postfix array. 2.2 If the symbol is operator or parenthesis, proceed to step 3. Infix notation: A+B*C/D Postfix Array A Stack Infix notation: A+B*C/D Postfix Array A Stack Rules in Converting Infix to Postfix Notation: Step 1: Assign one-dimensional array for the postfix notation to be derived. Step 2: Read each symbols of the given infix notation, from left to right manner. 2.1 If the symbol is operand, move to postfix array. 2.2 If the symbol is operator or parenthesis, proceed to step 3. Step 3a: If stack is empty/parenthesis 3a.1 If stack is empty, PUSH (for any operator). 3a.2 If the topmost element of the stack is an open parenthesis, PUSH (for any operator). 3a.3 For close parenthesis ), POP until it reaches the nearest open parenthesis. Infix notation: A+B*C/D Postfix Array A Stack + + Infix notation: A+B*C/D Postfix Array A B Stack + Infix notation: A+B*C/D Postfix Array A B Stack * + Step 3b: If stack is not empty: 3b.1 If the element to be inserted is HIGHER compared to the topmost element of the stack, PUSH. 3b.2 If the element to be inserted is LOWER compared to the topmost element of the stack, POP then return to step 3. 3b.3 If the element to be inserted is EQUAL compared to the topmost element of the stack, POP then return to step 3. Infix notation: A+B*C/D Postfix Array A B Stack * * + Infix notation: A+B*C/D Postfix Array A B C Stack * + Infix notation: A+B*C/D Postfix Array A B C Stack / * + Step 3b: If stack is not empty: 3b.1 If the element to be inserted is HIGHER compared to the topmost element of the stack, PUSH. 3b.2 If the element to be inserted is LOWER compared to the topmost element of the stack, POP then return to step 3. 3b.3 If the element to be inserted is EQUAL compared to the topmost element of the stack, POP then return to step 3. Infix notation: A+B*C/D Postfix Array A B C * Stack / * / + Step 3b: If stack is not empty: 3b.1 If the element to be inserted is HIGHER compared to the topmost element of the stack, PUSH. 3b.2 If the element to be inserted is LOWER compared to the topmost element of the stack, POP then return to step 3. 3b.3 If the element to be inserted is EQUAL compared to the topmost element of the stack, POP then return to step 3. Infix notation: A+B*C/D Postfix Array A B C * Stack / / + Infix notation: A+B*C/D Postfix Array A B C * D Stack / +  After reading all the symbols in the given infix notation and if stack is not empty: POP all the remaining elements of the stack to the postfix array. Infix notation: A+B*C/D Postfix Array A B C * D / + Stack / + Infix notation: A+B*C/D Postfix Notation: A B C * D / + Example #2 A+B*C/D*E–F+G A B C *D / E * + F – G +  Example #3 (with parentheses) Ex#3: Infix notation: A - B * (C + D / E) * F Postfix Array Stack Ex#3: Infix notation: A - B * (C + D / E) * F Postfix Array A Stack Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A Stack Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A Stack - - Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A B Stack - Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A B Stack * * - Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A B Stack ( * - Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A B C Stack ( * - Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A B C + Stack ( * - Step 3a: If stack is empty/parenthesis 3a.1 If stack is empty, PUSH (for any operator). 3a.2 If the topmost element of the stack is an open parenthesis, PUSH (for any operator). 3a.3 For close parenthesis ), POP until it reaches the nearest open parenthesis. Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A B C D + Stack ( * - Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A B C D / + Stack ( * - Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A B C D E / + Stack ( * - Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A B C D E / + / ) + Stack ( * - Step 3a: If stack is empty/parenthesis 3a.1 If stack is empty, PUSH (for any operator). 3a.2 If the topmost element of the stack is an open parenthesis, PUSH (for any operator). 3a.3 For close parenthesis ), POP until it reaches the nearest open parenthesis. Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A B C D E / + * Stack * ** - Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A B C D E / + * F Stack * - Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A B C D E / + * F * - Stack * - Ex#3: Infix notation: A – B * (C + D / E) * F Postfix Array A B C D E / + * F * - SEATWORK: A – B * ( ( C + D / E) + F ) * (G – H) ABCDE/+F+*GH–*– Queues CHAPTER 4 Objectives Students are expected to: Define queue and circular queue Identify the different ways to represent queue Examine the queue operation algorithms Apply queue operation algorithms in Java programming Compare the difference of queue and stack data structure Circular Queue The elements of the array are “arranged” in a circular fashion, with Arr following Arr[n]. Arr Arr Arr Arr REAR = -1 FRONT = -1 Arr Arr Arr Arr Stack vs Queue Linked List CHAPTER 5 Objectives Students are expected to: Understand the types of linked lists and its operations. Write a class which implements a simple list-like abstract data type. Appreciate that arrays and linked lists are two different data structures which may be used to implement list-like abstract data types. Write code which manipulates linked list in Java, and use cells and pointers diagrams to illustrate the effect. Linked-List A linked-list is a sequence of data structures which are connected via links. Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list the second most used data structure after array. Types of Linked-List: 1. Singly-Linked List 2. Doubly Linked List 3. Circular Linked List Singly Linked List Singly-linked list Read_List (Head) { If (Head = NULL) then { Print (“The list is empty”) Exit } Set NumNodes to 1 Set NextNode to Head → Node.Pointer Print Head → Node.Data While (NextNode is not NULL) { Increment NumNodes Print NextNode → Node.Data Set NextNode to NextNode → Node.Pointer } Print (“The number of nodes in the list is ” NumNodes) } Adding a new node at the end of the singly-linked list: Insert_Node (Head, i, New_value) { Create New Node Set Address of NewNode→Node.Data to NewValue If ( i = 1) then { Set Address of NewNode→Node.Pointer to Head Set Head to Address of New Node Exit } Decrement i Set Ctr to 1 Set Next_Node to Head While ( (Ctr < i) AND (Next_Node is not NULL) ) { Increment Ctr Set Last_Node to Next_Node Set Next_Node to Next_Node→Node.Pointer } If (Next_Node is NULL) then { Set Last_Node→Node.Pointer to Address of New Node Set Address of New Node→Node.Pointer to NULL } Else { Set Address of New Node→Node.Pointer to Next_Node→Node.Pointer Set Next_Node→Node.Pointer to Address of New Node } } Delete_Node (Head, i, N) { If (i > N) then { Print (“Error: Position to be deleted exceeds length of list” Exit } If (i = 1) { Set NodeAddress to Head Set Head to Head → Node.Pointer } Else { Decrement i Set Ctr to 1 Set NextNode to Head While (Ctr < i) { Increment Ctr Set NextNode to NextNode → Node.Pointer } Set NodeAddress to NextNode → Node.Pointer Set NextNode → Node.Pointer to NodeAddress → Node. Pointer } } Doubly Linked List Doubly-linked list The basic format of a node: Left Pointer Data Right Pointer Node Each node is divided into three parts: the left pointer field, data field, and the right pointer field. Doubly-linked list The data field is used to contain the value of the element. The right pointer field contains the address of the successor node. The left pointer field is used to contain the address of the preceding node in the list. Singly-linked list vs. Doubly-linked list Read_Dbl_List_LR (Head) { If (Head = NULL) then { Print (“The list is empty”) Exit } Set NumNodes to 1 Set NextNode to Head→Node.RightPointer Print Head→Node.Data While (NextNode is not NULL) { Increment NumNodes Print NextNode→Node.Data Set NextNode to NextNode→Node.RightPointer } Print (“The number of nodes in the list is ”) NumNodes } Adding a new node at the beginning of the doubly- linked list: Adding a new node at the end of the doubly-linked list: Adding a new node in between the nodes of the doubly- linked list: Deleting at the beginning of the doubly-linked list: Deleting at the end of the doubly-linked list: