Java Peer Instruction Materials on Queues and Data Structures
Java Peer Instruction materials by Cynthia Lee covering topics like queues, basic data structures, and implementation examples. Engage in reading quizzes and understand key concepts related to queue behavior and design decisions. Dive into Java code snippets for implementing a Queue class using LinkedList in Java.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Creative Commons License CS2 in Java Peer Instruction Materials by Cynthia Lee is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Based on a work at http://peerinstruction4cs.org. Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org. CSE 12 Basic Data Structures Cynthia Bailey Lee Some slides and figures adapted from Paul Kube s CSE 12
2 Today s Topics 1. Queues 2. Midterm review
Reading Quiz! A queue is also called a...? A. LIFO B. FILO C. FIFO D. LILO
Reading Quiz! When an item is removed from a queue, it is...? A. The one that has been in the queue for the longest time B. The one that has been in the queue for the shortest time C. The smallest one in the queue D. The largest one in the queue E. Other/none/more
Reading Quiz! When using enqueue() to place the following items into a queue: enqueue(32) enqueue(65) enqueue(0) enqueue(23) enqueue(-1) the output when dequeueing from the queue is: A. -1, 23, 0, 65, 32 B. -1, 0, 23, 32, 65 C. 65, 32, 23, 0, -1 D. 32, 65, 0, 23, -1 E. Other/none/more
Queue Design Which of the following are behaviors inherent in queues, which are decisions we'll make in specifying the behavior of our queue, which are decisions we'll make when implementing our queue. 1. When you dequeue, you get out the oldest element in the queue 2. When you insert, the element is inserted at the beginning of the linked list. 3. When you dequeue an empty queue, it throws an exception. A. B. C. D. E. None of these is correct Inherent 1 2 1 2 Specifying 2 1 3 3 Implementing 3 3 2 1
Consider the following implementation of a Queue that extends LinkedList and inherits all of its methods. public class Queue<E> extends LinkedList<E>{ private int size=0; public int size(){ return size; } public void enqueue(E e){ add(e); size+=1; } public E dequeue() { size-=1; return removeFirst(); } } What does this code output? Queue<Integer> q= new Queue<Integer>(); q.enqueue(10); q.enqueue(20); q.clearAll(); System.out.println(q.size()); A: 0 B: 2 C: throws a runtime exception (probably NoSuchMethodException) D: throws a checked exception; this block should have a try-catch block E: it won't even compile!
Consider the following implementation of a Queue that extends LinkedList and inherits all of its methods. public class Queue<E> extends LinkedList<E>{ private int size=0; public int size(){ return size; } public void enqueue(E e){ add(e); size+=1; } public E dequeue() { size-=1; return removeFirst(); } } What does this code output? Queue<Integer> q= new Queue<Integer>(); q.enqueue(10); q.enqueue(20); q.clearAll(); System.out.println(q.size()); A: 0 B: 2 C: throws a runtime exception (probably NoSuchMethodException) D: throws a checked exception; this block should have a try-catch block E: it won't even compile!
Queue should not extend LinkedList A Queue IS NOT a LinkedList! There are things you can do to a LinkedList, such as call clearAll() to remove all elements, that you should not be able to do with a Queue. You should encapsulate both the LinkedList and the size variable as instance variables inside your Queue class.
Consider the following approaches to determine whether the size() method in LinkedList is O(1) A: Insert one element and time how long the size method takes; compare this to how long the size method takes if you had inserted 100 elements. O(1) means they should be about equal. B: Insert a million elements and time how long the size method takes; compare this to how long the size method takes if you had inserted 10 million elements. O(1) means they should be about equal. C: Insert 10 billion elements and time how long the size method takes; compare this to how long the size method takes if you had inserted 100 billion elements. O(1) means they should be about equal.
public E dequeue(){ // potential issue if empty, for now, assume not empty E e = array[front]; <YOUR CODE HERE> return e; } Select the correct code to insert from below: C for(int i= 0; i<rear; i++) { array[i] = array[i+1]; } rear = rear -1; A front+ +; B rear = rear-1; D None of these are correct
public void enqueue( E element){ // potential issue if full, for now, assume room <YOUR CODE HERE> front++; } Select the correct code to insert from below: C for(int i= 0; i<front; i++) { array[i+1] = array[i]; } array[front] = e; A array[0] = e; B array[front] = e; D None of these are correct
public E dequeue(){ // potential issue if empty, // for now, assume not empty size--; E e = array[front]; <YOUR CODE HERE> return e; } Select the correct code to insert from below: A C for(int i= 0; i<rear; i++) { array[i] = array[i+1]; } rear = rear -1; if(rear < 0) rear = array.length-1; D None of these are correct front+ +; if(front == array.length) front = 0; B rear = rear-1; if(rear <0) rear = array.length-1;
public void enqueue(E e){ // potential issue if full, // for now, assume not full <YOUR CODE HERE> size++; } Select the correct code to insert from below: C for(int i= front; i<rear; i++) { array[i] = array[i+1]; } array[rear] = e; front--; A rear+ +; if(rear == array.length) rear = 0; array[rear] = e; B rear++ array[rear] =e; D None of these are correct
Suppose our array is full and you try to enqueue, your coworker suggests just throwing an exception because it would be easy to implement? A. Sounds like a good idea. B. No, you need to resize and copy, fixing front and rear pointers. C. I have a better idea.
Suppose we have a Queue implemented with a circular array. The capacity is 10 and the size is 5. Which are not legal values for front and rear? front rear A 0 5 B 5 9 C 7 2 D 9 4 E All are legal values
Suppose we have a Queue implemented with a circular array. The capacity is 10 and the size is 5. Which are not legal values for front and rear? front rear A 0 5 B 5 9 C 7 2 D 9 4 E All are legal values
Which of these could be the body of the size() method for a Queue that uses a circular array implementation? A if (front==rear) return 0; return rear-front; B if (rear>front) return rear-front; return front-rear; C if (front==0 && front==rear) return 0; if (front>rear) return front-rear; return rear-front; D if (front>rear) return front-rear; if (front==rear) return 0; return rear-front; E if (front==rear) return 0; if (front>rear) return front-rear; if (rear>front) return rear-front;
Which of these could be the body of the size() method for a Queue that uses a circular array implementation? A if (front==rear) return 0; return rear-front; B if (rear>front) return rear-front; return front-rear; C if (front==0 && front==rear) return 0; if (front>rear) return front-rear; return rear-front; D if (front>rear) return front-rear; if (front==rear) return 0; return rear-front; E if (front==rear) return 0; if (front>rear) return front-rear; if (rear>front) return rear-front;
