DSA M3 - M5.pdf

module3 stack data stack abstract type representations likeareal behaves world stack onedimensionalarray pointer structure...

module3 stack data stack abstract type representations likeareal behaves world stack onedimensionalarray pointer structure list linked lastinfirstout lifo lastelementinsertedinthestackwillbethefirsttoprocess iii aaang.ms pop removing deletingitems new new variablesdeclareidarray stack initialize empty size the clear clears ofthestack content Emptywill is ustocheckpriortopoppushusedtocheckkungmaylamanyungstack help Fullwillcheckifitsfullcapacityornot is topitems peek retrieve circularqueue topnumberistreatedasindex notvalue reusecellswithde queueitems loopfrontandrearisindex 1 orbackto0 queues arrangedincircularmotion Arrin firstcomefirstserve firstinfirstout Fifo movesfront vanable both accessibleon andback endsfront i enquene additematrear push stack rear 4 a 7 2 de queue itematfront remove pop stack T.t.io no 411 20 4 50 7 70 2 30 5 60 0 queueisfun enqueneof80willnot takeplace notinserted operations as enquene addinginrear jobfirst soy shortest dequeue removesandreturnsthefront item waitingqueue newL empty frontandrearis 1 walanglaman emptyornew isfull itrearisequalto N I afront 1 de queuestrat i moveremainingitemsforward bigo linearworstcase 2movefrontvanable Stacks CHAPTER 3 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  3.1 Pushdown Stacks linear arrangement of items accessible only at one end, called the top push – add item to top pop – remove item from top Last-in First-out (LIFO) Examples Pringles can Rifle magazines Cafeteria Trays CEFA CEFA  3.1 new creates a new empty stack clear clears the stack of its items isEmpty checks if the stack has no items checks if the stack is filled to its isFull capacity adds an item as the new top item of push the stack removes and returns the top item from pop the stack returns top item without removing it peek from stack. Also called the top() opern CEFA CEFA 3.1 CEFA CEFA  3.2 Array representation of integer stack stack = record { maxStkSize: integer; top = integer; stk = integer[]; } CEFA CEFA  3.3 new operation stack new(stack; n) { 1 create instance of stack record 2 maxStkSize = n 3 top = –1 4 stk = new integer[maxStkSize] 5 return this new stack } stack s = new(stack, 100) clear operation void clear(s : a stack) { 1 s.top = –1 } CEFA CEFA  3.3 isFull operation boolean isFull(s) { 1 if (s.top = s.maxStkSize – 1 ) then return true 2 else return false } push operation integer push(s; el: integer) { 1 if (isFull(s)) then return -999 //push overflow error 2 s.top = s.top + 1 3 s.stk[s.top] = el 4 return 1 } CEFA CEFA  3.3 isEmpty operation boolean isEmpty(s) { 1 if (s.top = –1) then return true 2 else return false } pop operation integer pop(s) { 1 if (isEmpty(s)) then return -999 //pop underflow error 2 integer el = s.stk[s.top] 3 s.top = s.top – 1 4 return el } peek operation integer peek(s) { 1 if (isEmpty(s)) then return -999 //peek empty error 2 else return s.stk[s.top] } CEFA CEFA  3.3.2 Generics – references objects whose classes are not known until instantiated cannot contain an array of generics public class Stack { private int maxStkSize=100; private int top = -1; private Object[] stk; public Stack() { stk = new Object[maxStkSize]; } public Stack(int n) { if (n > 0) maxStkSize = n; stk = new Object[maxStkSize]; } // insert other methods here } CEFA CEFA  3.3.2 Instantiations Stack s1 = new Stack(); Stack s2 = new Stack(300); Some methods public boolean isEmpty() { return (top == -1); } public int push(T el) { if (isFull()) return -999; stk[++top] = el; return 1; } public T pop() { if (isEmpty()) return null; T el = (T) stk[top--]; return el; } CEFA CEFA  3.3.2 Notes: Generics: design once, instantiate in different ways Generics for objects: use wrapper classes for primitives Object array: every class extends Object class cast back to T for pop and peek Errors: error codes/messages or try/catch Java has predefined stack class java.util.Stack CEFA CEFA  3.4 Reversals push all one-by-one, then pop all one-by-one Block Delimiters begin/end, parenthesization, braces HTML push opening delimiters, pop on matching closing delimiters Polish Notation Procedure calls CEFA CEFA  3.4.2 Operators between their operands examples: 5 3+4 2*(3+4) 2+3*4 Sometimes ambiguous Requires parenthesization and precedence rules CEFA CEFA  3.4.2 Parenthesis highest precedence ex. 2 * (3 + 4) = ? Exponent ties are broken right to left: ex. 2 ^ 3 ^ 2 = ? Multiplication and Division ties are broken left to right: ex. 9 / 3 * 2 = ? Addition and Subtraction lowest precedence; ties broken left to right ex. 5 – 3 + 2 = ? CEFA CEFA  3.4.2 Unambiguous – requires no parenthesis Prefix Notation an elementary operand, or an operator, followed by its first operand in prefix notation, followed by its second operand in prefix notation ex. + 3 4 and * 2 + 3 4 Postfix Notation an elementary operand, or the first operand in postfix notation, followed by the second operand in postfix notation followed by the operator ex. 3 4 + and 2 3 4 + * CEFA CEFA  3.4.2 Infix expression: A + B / C – D * E Operator First Second Postfix highest to lowest Prefix equivalent precedence operand operand equivalent / B C * D E + A B/C – A+B/C D*E CEFA CEFA  3.4.2 Y[1..n] infixToPostfix ( X[1..n] : infix expression ) { 1 // X[1..n] contains the n items (operands and operators) 2 stack s = new(stack,100) 3 k=0 4 for i = 1 to n 5 if X[i] is an operand then Y[++k] = X[i] 6 else 7 while (not isEmpty(s) and X[i] has lower precedence than peek(S) ) 8 Y[++k] = pop(s) 9 push(s, X[i]) 10 while not isEmpty(s) 11 Y[++k] = pop(s) 12 return Y[1..n] } Ex: Convert “A + B / C – D * E” to “A B C / + D E * –” CEFA CEFA  3.4.2 Y[1..n] infixToPrefix ( X[1..n] : infix expression ) { 1 // X[1..n] contains the n items (operands and operators) 2 stack optr = new(stack,100) 3 stack rev = new(stack,200) 4 for i = n downto 1 5 if X[i] is an operand, push(rev, X[i]) 6 else, 7 while (not isEmpty(optr) and X[i] has lower precedence than peek(optr) ) 8 push(rev,pop(optr)) 9 push(optr, X[i] ) 10 while (not isEmpty(optr)) push(rev,pop(optr)) 11 k = 0 12 while (not isEmpty(rev)) Y[++k] = pop(rev) 13 return Y[1..n] } Ex: Convert “A + B / C – D * E” to “– + A / B C * D E” CEFA CEFA  3.4.2 Priority numbers determine if incoming operator has lower priority than operator on top of the stack In-Stack Incoming Operator Direction Priority Priority ^ right-to-left 5 6 * and / left-to-right 4 3 + and – left-to-right 2 1 ( 0 9 ) never in stack pop till matching ( CEFA CEFA  3.4.2 real evalPostfix(X[1..n] : postfix expression) { 1 // X[1..n] contains the n items (operands and operators) 2 stack s = new(stack,100) 3 for i = 1 to n 4 if X[i] is an operand push(s,X[i]) 5 else 6 B = pop(s) 7 A = pop(s) 8 push(s, evaluate( A, X[i], B ) ) 9 return pop(s) } Ex: Evaluate “ 7 9 3 / + 2 4 * – ” CEFA CEFA  3.4.2 real evalPrefix(X[1..n] : prefix expression) { 1 // X[1..n] contains the n items (operands and operators) 2 stack s = new(stack,100) 3 for i = n downto 1 4 if X[i] is an operand, push(s,X[i]) 5 else 6 A = pop(s) 7 B = pop(s) 8 push(s, evaluate( A, X[i], B ) ) 9 return pop(s) } Ex: Evaluate “ – + 7 / 9 3 * 2 4 ” CEFA CEFA  3.4.2 string postfixtoInfix(X[1..n] : postfix expression) { 1 // X[1..n] contains the n items (operands and operators) 2 stack s = new(stack,100) 3 for i = 1 to n 4 if X[i] is an operand, push(s,X[i]) 5 else 6 B = pop(s) 7 A = pop(s) 8 push(s, concat("(",A,X[i],B,")")) 9 return pop(s) } Ex: Convert “ 7 9 3 / + 2 4 * – ” to Infix Notation CEFA CEFA  3.4.2 string prefixToInfix(X[1..n] : prefix expression) { 1 // X[1..n] contains the n items (operands and operators) 2 stack s = new(stack,100) 3 for i = n downto 1 4 if X[i] is an operand, push(s,X[i]) 5 else 6 A = pop(s) 7 B = pop(s) 8 push(s, concat("(",A,X[i],B,")")) 9 return pop(s) } Ex: Convert “ – + 7 / 9 3 * 2 4 ” to Infix Notation CEFA CEFA  3.4.3 Call Stack To remember where to return after a procedure call push on call M() B() 1 call A(3) 1 print "Hi" pop on return 2 print "Bye" Example: A(n) C(n) 1 call B() 1 if n > 1 then call C(n-1) M() is main 2 call C(n) 2 print n B s=1 A A A s=1 s=1 s=1 n=3 n=3 n=3 M M M M s=1 s=1 s=1 s=1 CEFA CEFA Queues CHAPTER 4 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 last in firstout first in firstout Linked List CHAPTER 5 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 } }  Chapter Linked 5 Lists CEFA 1 5.1 List sequence of items linear structure static or dynamic finite lists ordered physically in data structures logical ordering (sorting) alphabetically ascending or descending representations array – space, time for static/dynamic operations? linked lists sequenceofdataare connected by a link secondmostused CEFA CEFA 2 1  5.2 SLL Node ADT Data Information of an item Pointer to next item  null – points to no node. (aka “/” or “\”) Operations new – allocates a new singly linked list node delete – deallocates a singly linked list node toString – returns a string describing the info in the node Information valueof on node datafield CEFA CEFA addresscontentsareawayandarephysicallyadjacent 3 node lastinthelist 5.2 nullwalanginturonaitem insertioncanhappenfrom Ietween CEFA CEFA 4 singlytraverseto onedirection 2  5.2 SLL Node Representation snode = record { info: integer; next: snode pointer; } Implementing the new operation snode new(singly linked list node; el: integer; p: snode) { 1 create instance of snode record 2 info = el; 3 next = p; 4 return this new singly linked list node } CEFA CEFA 5 5.2.2 Generic information class public class SLLNode { public T info; public SLLNode next; public SLLNode(T el) { info = el; next = null; } public SLLNode(T el, SLLNode ptr) { info = el; next = ptr; } public String toString() { return info.toString(); } } CEFA CEFA 6 3  num next nodedata field heads 4800 my false 4900 4800 true 10 15 5 20 thenumber ofnodes it 4  1,1 I 2 3 5 6 insertion 1 4 53 head I ctr new last 4800 4 1 4800 4800 2 4900 490 3 5000 4900 4900 T E 0  5.2.2 Instantiations: SLLNode snode1 = new SLLNode("Pedro"); SLLNode snode3 = new SLLNode(143); Printing the SLL Node: System.out.println(snode3); automatically calls toString method If info’s class does not override toString() of Object class, it will return the “address” of the info. Deletion by automatic garbage collection When an object is not referenced, it will eventually be deallocated by Java’s runtime environment CEFA CEFA 7 5.3 SLL ADT aka, “linked list” Data a linear sequence of SLL nodes head - a pointer to first node tail - a pointer to last node (optional) CEFA CEFA 8 4  5.3 new creates a new linked list determines if a linked list contains nodes isEmpty or not optionalnot required returns a string concatenating the info’s in toString a linked list returns a pointer to the first node find containing an info, if any. Operation has variations. findthe can name adds a new node containing an info into a add linked list. Operation has variations. deletes the first node containing an info delete from a linked list, if any. Operation has variations. CEFA CEFA 9 IdatalpointertdIT 5.3 headandtailareempty A CEFA CEFA 10 5  5.4 SLL of integers Representation slist = record { head, tail : snode pointers } SLL new operation slist new(singly linked list) { 1 create instance of slist record 2 head = tail = null 3 return this new singly linked list } SLL isEmpty operation boolean isEmpty(slist1 : an slist) { 1 if (slist1.head = null) then return true 2 else return false } CEFA CEFA 11 5.4 SLL toString operation string toString(slist1) { 1 string s = "" 2 snode p = slist1.head 3 while (p  null) 4 s=s + p.info + " “ 5 p = p.next 6 return s } SLL find operation snode find(slist1 : an slist; el : an integer) { 1 snode p = slist1.head 2 while (p  null and p.info  el) 3 p = p.next 4 return p } CEFA CEFA 12 6  5.4 SLL addToHead operation void addToHead(slist1, el) { 1 slist1.head = new (singly linked list node, el, slist1.head) 2 if (slist1.tail = null) 3 slist1.tail = slist1.head // only node of list } CEFA CEFA 13 5.4 SLL addToTail operation void addToTail(slist1, el) { 1 if (isEmpty(slist1)) 2 slist1.head = slist1.tail = new (singly linked list node, el, null) 3 else 4 slist1.tail.next = new (singly linked list node, el, null) 5 slist1.tail =slist1.tail.next } CEFA CEFA 14 7  5.4 SLL deleteFromHead operation integer deleteFromHead(slist1) { 1 if (isEmpty(slist1)) return -999 2 snode1 = slist1.head 3 el = snode1.info 4 if (slist1.head = slist1.tail) 5 slist1.head = slist1.tail = null 6 else 7 slist1.head = slist1.head.next 8 delete(snode1) 9 return el } CEFA CEFA 15 5.4 SLL deleteFromTail operation integer deleteFromTail(slist1) { 1 if (isEmpty(slist1)) return -999 2 snode snode1 = slist1.tail 3 el = snode1.info 4 if (slist1.head = slist1.tail) 5 slist1.head = slist1.tail = null 6 else 7 snode p = slist1.head 8 while (p.next  slist1.tail) 9 p = p.next 10 slist1.tail = p 11 slist1.tail.next = null 12 delete(snode1) 13 return el } CEFA CEFA 16 8  5.4 SLL delete operation CEFA CEFA 17 5.4 SLL delete operation integer delete(slist1, el) { 1 if (isEmpty(slist1)) return -999 2 if (el = slist1.head.info) 3 return deleteFromHead(slist1) 4 if (el = slist1.tail.info) 5 return deleteFromTail(slist1) 6 snode pred = slist1.head 7 snode t = slist1.head.next 8 while (t  null and t.info  el) 9 pred = pred.next 10 t = t.next 11 if (t = null) return -999 12 else 13 pred.next = t.next 14 delete(t) 15 return el } CEFA CEFA 18 9  5.4.2 Generic SLL class public class SLL { private SLLNode head, tail; // insert method definitions here } Instantiations SLL slist1 = new SLL(); SLL toString operation public String toString() { SLLNode p; String s = ""; for (p = head; p != null; p = p.next) s=s+p.info.toString() + " "; return s; } toString() invocation System.out.println(slist1); CEFA CEFA 19 5.4.2 more methods public void addToHead(T el) { head = new SLLNode(el,head); if (tail == null) tail = head; } public T deleteFromTail() { if (isEmpty()) return null; T el = tail.info; if (head == tail) head = tail = null; else { SLLNode p; for (p = head; p.next != tail; p = p.next) ; tail = p; tail.next = null; } return el; } CEFA CEFA 20 10  5.4.2 Find and Delete operations require comparison of info values Comparing objects Equality test p.info.compareTo(el) == 0 Less Than test p.info.compareTo(el) < 0 Greater Than test p.info.compareTo(el) > 0 Equality test with Generics ((Comparable)p.info).compareTo(el) == 0 CEFA CEFA 21 5.5 Traversed in only one direction from head to tail Difficulty deleting deleteFromTail and delete operations needs access to predecessor node What if a prev pointer is avaible? Each node is doubly linked results in doubly linked lists CEFA CEFA 22 11  5.5.1 with additional previous node pointer dnode = record { info: integer; prev, next: dnode pointers; } Operations: new – allocates a new doubly linked list node delete – deallocates a doubly linked list node toString – returns a string describing the info in the node CEFA CEFA 23 5.5.1 DLL Node new operation dnode new(doubly linked list node; el: integer; p,n: dnodes) { 1 create instance of dnode record 2 info = el; 3 prev = p; 4 next = n; 5 return this new doubly linked list node } DLL Node delete and toString operations similar to SLL Node counterparts CEFA CEFA 24 12  5.5.2 Example: dlist = record { head, tail : dnode pointers } The operations for doubly linked lists are similar to those for singly linked lists. CEFA CEFA 25 5.5.2 DLL new operation dlist new(doubly linked list) { 1 create instance of dlist record 2 head = tail = null 3 return this new doubly linked list } DLL addToHead operation void addToHead(dlist1 : a dlist; el : an integer) { 1 if (dlist1.head = null) 2 dlist1.head = new (doubly linked list node, el, null, null) 3 dlist1.tail = dlist1.head 4 else 5 dlist1.head = new (doubly linked list node, el, null, dlist1.head) 6 dlist1.head.next.prev = dlist1.head } CEFA CEFA 26 13  5.5.2 DLL deleteFromTail operation integer deleteFromTail(dlist1) { 1 if (isEmpty(dlist1)) return -999 2 d = dlist1.tail 3 el = d.info 4 if (dlist1.head = dlist1.tail) 5 dlist1.head = dlist1.tail = null 6 else 7 dlist1.tail = dlist1.tail.prev 8 dlist1.tail.next = null 9 delete(d) 10 return el } CEFA CEFA 27 5.6 What if the tail node points to the head node? Examples: No node points to null Nodes form a circle No head and tail pointers anymore, but a pointer to an arbitrary node CEFA CEFA 28 14  5.6 creates a new circular list (singly or new doubly linked) determines if the linked list contains isEmpty nodes or not returns a string of the info’s in the toString linked list returns a pointer to a first node with find an info, if any adds a node with an info value before add or after the node pointed to by cptr deletes node pointed by cptr or a node delete with info value The implementations of these operations are left as exercises. CEFA CEFA 29 5.7 The head is top. The tail is unnecessary. stack = record { stackL: slist; } stack new(stack) { 1 create instance of a stack record 2 stackL = new(singly linked list) 3 return this new stack } stack stack1 = new(stack) boolean isEmpty(s : stack) { 1 return isEmpty(s.stackL) } CEFA CEFA 30 15  5.7 more stack operations using lists void push(s : stack; el : integer) { 1 addToHead(s.stackL, el) } integer pop(s : stack) { 1 return deleteFromHead(s.stackL) } integer peek(s : stack) { 1 if isEmpty(s.stackL) 2 return -999 3 else 4 return s.stackL.head.info } CEFA CEFA 31 5.7 The head is front. The tail is rear. queue = record { queueL: slist; } queue new(queue) { 1 create instance of a queue record 2 queueL = new(singly linked list) 3 return this new queue } queue queue1 = new(queue) boolean isEmpty(q : queue) { 1 return isEmpty(q.queueL) } CEFA CEFA 32 16  5.7 more queue operations using lists void enqueue(q : queue; el : integer) { 1 addToTail(q.queueL, el) } integer dequeue(q : queue) { 1 return deleteFromHead(q.queueL) } integer peek(q : queue) { 1 if isEmpty(q.queueL) 2 return -999 3 else 4 return q.queueL.head.info } CEFA CEFA 33 17