Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Lab 5B: Queues Q1 Queues 5 Points A queue is an ADT in which items are inserted at the end of the queue using
Lab 5B: Queues Q1 Queues 5 Points A queue is an ADT in which items are inserted at the end of the queue using an enqueue () method and removed from the front of the queue using a dequeue () method. Q1.1 Queue Implementation with LinkedList 5 Points For this queue, how many dequeue() calls will it take for: head tail 12. a. 99 to be removed? Enter your answer here b. 12 to be removed? Enter your answer here c. head to be null? Enter your answer here d. is Empty() to return true? Enter your answer here Save Answer 99 37 e. a QueueUnderflowException to be thrown? Enter your answer here Q2 Array implementation of Queue 4 Points Q2.1 1 Point What is the array equivalent to the Queue created by the following operations: enqueue (121); enqueue (187); enqueue (230); enqueue (220); enqueue (250); enqueue (240); O 240 250 220 230 187 121 O 121 187 230 220 250 240 O 121 230 187 220 240 250 Save Answer enqueue (121); enqueue (187); enqueue (230); enqueue (220); enqueue (250); enqueue (240); O 0(1) O O(N) Array: O O(log N) OO(N) 0 0(2) Save Answer Q2.2 1 Point What is the O() cost for the last call enqueue (240) ? 0 Array: 1 2 0 1 3 2 3 5 5 Q2.3 1 Point What is the O() cost of enqueue (311) after the code has been executed? enqueue (121); enqueue (187); enqueue (230); enqueue (220); enqueue (250); enqueue (240); O 0(1) O O(N) O O(log N) OO(N) OO (2N) Save Answer Q2.4 1 Point Array: Save Answer 01 2 3 4 5 What would the O() cost of enqueue (311) be if we use a linked list with tail insertion? 0(1) O O(N) O O(log N) OO(N) 0 0(2N) Q3 Implementing a Deque with LinkedList 20 Points A deque (pronounced "deck" and short for double-ended queue) is an ADT in which items can be inserted and removed at both the front and back. Study the difference between a queue and deque using a linked list in the figure below. Out Queue X X In and Out Deque X X X X Please download the Queue starter code. It has a Node and DequeDblLinked List class. In and Out Your task is to complete the implementation of the enqueueFront, enqueue Rear, dequeueFront, and dequeueRear methods. enqueueFront(T item): Adds an item at the front of Deque. enqueueRear(T item) : Adds an item at the rear of Deque. dequeueFront(): Deletes an item from front of Deque. dequeueRear() : Deletes an item from rear of Deque When traversing the list, be aware of possible infinite loops or null pointer exceptions. If you run into any of this, USE THE DEBUGGER! class DequeDblLinkedList { private Node front; private Node rear; Q3.1 5 Points /* * Adds element at the beginning of the queue */ public void enqueueFront (T item) { System.out.println("adding at front: "+item); //TODO 1: write your code here Enter your answer here Save Answer Q3.2 5 Points /* * Adds element at the end of the queue */ public void enqueueRear (T item) { System.out.println("adding at rear: "+item); //TODO 2: write your code here Enter your answer here Save Answer Q3.3 5 Points /* * Remove an item from the beginning of the queue */ public void dequeueFront () { if (front == null) { Save Answer Q3.4 5 Points System.out.println("Deque underflow!! unable to remove."); } //TODO 3: write your code here Enter your answer here return; /* * Remove an item from the rear of the queue */ public void dequeueRear() { if (rear == null) { System.out.println("Deque underflow!! unable to remove."); return; } //TODO 4: write your code here Save Answer Enter your answer here
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started