程序代写代做代考 chain Java html data structure compiler ArrayList Stack Queue

ArrayList Stack Queue
Juan Zhai juan.zhai@rutgers.edu

java.util.ArrayList
• ArrayListisagenericarraythatcanresizeitself
automatically on demandàdynamic length
• capacityofArrayList:thenumberofarraylocationsfor
which memory space has been set aside.
• sizeofArrayList:thecurrentnumberofelementsinthe
list.àsize ≤ 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦
ArrayList al = new ArrayList(5);
for(int i=0; i<5; i++) al.add(new String(i)); //automatic resizing when one more item is added al.add(new String(5)) Juan Zhai, juan.zhai@rutgers.edu 2 java.util.ArrayList • When reach the full capacity: • Allocate a new array with a bigger capacity • Copy items in the old array to the new array • Worst case for adding an element at the end: àresize the array, O(n) • Append the new item to the new array • The original array is ready for garbage collection • Noguaranteethatthereisenoughspacefor extending array in the original space Juan Zhai, juan.zhai@rutgers.edu 3 java.util.ArrayList • ArrayListprovidesnumerousmethods • boolean add (E e): appends e to the end.àO(n) • Eremove(intindex):removestheelementatthespecified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).àO(n) • Eget(intindex):returnstheelementatthespecifiedposition in this list.àO(1) • https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList. html Juan Zhai, juan.zhai@rutgers.edu 4 Stack • Stack is a linear data structure which is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle • Elements are added and removed from the stack only at the top Juan Zhai, juan.zhai@rutgers.edu 5 Stack • Two fundamental operations • push: adds an item to the top of the stack • pop: removes and returns the item from the top Juan Zhai, juan.zhai@rutgers.edu 6 Stack operations • voidpush(Titem) • Tpop():returnsthetopentryandremovesit • Tpeek():returnsthetopentrywithoutremovingit If stack does not provide peek operation, how to get the top element? àFirst pop the top entry and then push the entry back • Utilitymethodstoimproveefficiency • intsize() • booleanisEmpty() • voidclear() Juan Zhai, juan.zhai@rutgers.edu 7 Implement a stack from scratch Juan Zhai, juan.zhai@rutgers.edu 8 Sakai Code Stack Implementation Using ArrayList • Thelastentryisusedasthetop Juan Zhai, juan.zhai@rutgers.edu 9 Juan Zhai, juan.zhai@rutgers.edu 10 Reuse ArrayList Sakai Code Stack Implementation Using Linked List • Thefrontnodeisusedasthetop • UseinsertFronttopushanddeleteFronttopop Juan Zhai, juan.zhai@rutgers.edu 11 Reuse LinkedList deleteFront takes care of whether there exists an item or not Juan Zhai, juan.zhai@rutgers.edu 12 Sakai Code Worst Case Running time Operation ArrayList Linked List push O(n)* O(1) pop O(1) O(1) peek O(1) O(1) isEmpty O(1) O(1) size O(1) O(1) *copy items in old array to new array when capacity is full Juan Zhai, juan.zhai@rutgers.edu 13 Applications of Stack • Reverse a word: push a given word to stack - letter by letter - and then pop letters from the stack • “undo” mechanism in text editors: a chain of undos erases actions in the sequence latest to earliest • Balanced parentheses: each opening symbol has a corresponding closing symbol and the pairs of parentheses are properly nested Juan Zhai, juan.zhai@rutgers.edu 14 Balanced parentheses • Acompilerchecksexpressionsinaprogramto ensure that all parentheses are matched – (a+b) – (a+b.)a+b(, – (a+b)*c-d*(c+a[2])/(x+y)) • Ifyouseeanopeningparenthesis,pushitintothe stack • Ifyouseeaclosingparenthesis,thetopelement in the stack must be an opening parenthesis Juan Zhai, juan.zhai@rutgers.edu 15 Juan Zhai, juan.zhai@rutgers.edu 16 Juan Zhai, juan.zhai@rutgers.edu 17 Sakai Code Queue • Queue is a linear data structure which is a container of objects that are inserted and removed according to the first-in first-out (FIFO) principle. • Example: any queue of consumers for a resource where the consumer that came first is served first. Juan Zhai, juan.zhai@rutgers.edu 18 Queue • Two fundamental operations • enqueue: adds an item at the rear of the queue • dequeue: removes and returns the item at the front of the queue Juan Zhai, juan.zhai@rutgers.edu 19 Stack v.s. Queue • Stack: remove the most recently added item • Queue: remove the least recently added item Juan Zhai, juan.zhai@rutgers.edu 20 Queue operations • voidenqueue(Titem) • Tdequeue():returnsthefrontentryandremovesit • Tpeek():returnsthefrontentrywithoutremovingit If queue does not provide peek operation, how to get the top element? àDequeue all entries and enqueue them • Utilitymethodstoimproveefficiency • intsize() • booleanisEmpty() • voidclear() Juan Zhai, juan.zhai@rutgers.edu 21 Applications of Queue • Service requests for shared resources • Print jobs Juan Zhai, juan.zhai@rutgers.edu 22 Queue Implementation • Anefficientimplementationistomaintaina reference to the rear and a reference to the front to make these positions accessible in one step, namely in O(1) time Juan Zhai, juan.zhai@rutgers.edu 23 Queue implementation using ArrayList • Lowerendofanarraylistasthefrontofthequeueand higher end as the rear • Enqueueanentry:advancetherearindexbyone • Dequeueanentry:0thpositionbecomesempty • Fortheemptyspot • Movingalltheentriesfromrighttoleft:O(n),inefficient • Increasethefrontindexbyone:O(1),butwastespace Increase the front index on a fixed-length array and recycle space (wrap around) Juan Zhai, juan.zhai@rutgers.edu 24 Bounded Queue: Queue implementation using circular array • Circulararray:adatastructurethatusedanarrayas if it were connected end-to-end Juan Zhai, juan.zhai@rutgers.edu 25 Queue implementation using circular array Juan Zhai, juan.zhai@rutgers.edu 26 Data field for a bounded queue • T[] items; • int rear; • int head; • int count; – Keep the total number of entries – Starting with 0 when the queue is created. – Each time an entry is enqueued or dequeued, increase or decrease the count by one respectively Juan Zhai, juan.zhai@rutgers.edu 28 Create a new bounded queue public BoundedQueue(int capacity){ if(capacity < 2){ the total number of items that can be stored in the array System.out.println(“insufficient capacity”); items = (T[]) new Object[10]; //items = new T[10]; will trigger a compile error } else items = (T[]) new Object[capacity]; rear = -1; // in an empty queue, rear equals to -1 head = -1; // in an empty queue, head equals to -1 count = 0; // in an empty queue, count equals to 0 } the total number of items that are already stored in the array Juan Zhai, juan.zhai@rutgers.edu 29 Utility methods public int size(){ return count; } public boolean isEmpty(){ return count == 0; } public boolean isFull(){ return count == items.length; } Juan Zhai, juan.zhai@rutgers.edu 30 public void enqueue(T item) { //1. check whether the queue is already full if(isFull()) { System.out.println(“full queue”); return ; } //2. check whether the queue is empty else if(isEmpty()){ rear = 0; head = 0; } //3. check whether rear points to end of the array else if(rear == items.length-1) rear = 0; //4. advance rear to the next spot else rear++; //5. enqueue item into the spot pointed by rear items[rear] = item; //6. increase the total number of items in the queue count++; } Juan Zhai, juan.zhai@rutgers.edu 31 public T dequeue() { //1. check whether the queue is empty if(isEmpty())throw new NoSuchElementException("empty queue"); //2. obtain the item being removed T item = items[head]; //3. check whether there is only one item in the queue if(head == rear){ head = -1; rear = -1; } //4. check whether head points to the end of the array else if(head == items.length - 1) head = 0; //5. advance head to the next spot else head++; //5. decrease the total number of items in the queue count--; //6. return the front item return item; } Juan Zhai, juan.zhai@rutgers.edu 32 public void traverse() { //1. check whether the queue is empty if(isEmpty()) return ; //2. rear is greater than head if(rear > head){
for (int i = head; i <= rear; i++) System.out.print(items[i] + " "); } //3. rear is smaller than head else { for (int i = head; i < items.length; i++) System.out.print(items[i] + " "); // the queue wraps around the end of the array for (int i = 0; i <= rear; i++) System.out.print(items[i] + " "); } } Juan Zhai, juan.zhai@rutgers.edu 33 Queue implementation using array • Circular array is still an array • The inherent space underestimation or overestimation problem • Linked list is more attractive Juan Zhai, juan.zhai@rutgers.edu 34 Queue Implementation • Anefficientimplementationistomaintaina reference to the rear and a reference to the front to make these positions accessible in one step, namely in O(1) time Juan Zhai, juan.zhai@rutgers.edu 35 rear Queue implementation using circular linked list Each operation can finish in O(1) time Juan Zhai, juan.zhai@rutgers.edu 36 Questions from students • Eachclasshasadefaultimplementationofthe method toString() which will be invoked in methods like System.out.println(). • Thedefaultimplementationwillusetheclassname and hash code to represent an object. • NeedtohaveyourownimplementationoftoString() in your class to display the object as you like. Juan Zhai, juan.zhai@rutgers.edu 37