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
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