Lab 5B: Queues Q1 Queues 5 Points A queue is an ADT in which items are...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
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 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
Expert Answer:
Related Book For
College Accounting A Contemporary Approach
ISBN: 978-0077639730
3rd edition
Authors: David Haddock, John Price, Michael Farina
Posted Date:
Students also viewed these programming questions
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...
-
True or False? Azure files can be accessed from anywhere in the world using a URL that points to the file. True False
-
Data showing the population by state in millions of people follow (The World Almanac, 2012). a. Develop a frequency distribution, a percent frequency distribution, and a histogram. Use a class width...
-
Discuss how a community can use social capital theory to address the lack of sidewalks in a neighborhood. Explain how bridging social capital can positively or negatively impact a community when...
-
Lynch Brothers manufactures conveyor belts. Early in January 2011, Lynch Brothers constructed its own building at a materials, labor, and overhead cost of $900,000. Lynch Brothers also paid for...
-
Helen Murvis, hospital administrator for Portland General Hospital, is trying to determine whether to build a large wing onto the existing hospital, a small wing, or no wing at all. If the population...
-
Determine whether the equation defines y as a function of x. y=- 8 x Does the equation define y as a function of x?
-
A ladder of length L and mass M has its bottom end attached to the ground by a pivot. It makes an angle ? with the horizontal, and is held up by a massless stick of length ? which is also attached to...
-
A double external long shoe drum brake is illustrated in Figure 10.37. The face width of the shoes is 50 mm and the maximum permissible lining pressure is 1MPa. If the coefficient of friction is 0.32...
-
In a virtualized environment running multiple guest operating systems on a single host machine, how would you design a memory management scheme that balances efficient resource allocation among...
-
A company began January with 9,000 units of its principal product. The cost of each unit is $4. Inventory transactions for the month of January are as follows: Check Date of Purchase 5 Units January...
-
Tissue engineering is the use of a combination of cells, engineering, and materials methods, and suitable biochemical and physicochemical factors to improve or replace biological tissues. In the...
-
Culture is known to shape many aspects of human behavior, including social norms, values, and even perception. Can cultural influences also interact with our biological predispositions, such as those...
-
To what extent did the economic and political compromises made during the creation of the United States Constitution (1787) lay the groundwork for the future sectional conflicts (particularly over...
-
22. (9 points) For each of the compounds below illustrated as line structures, provide (1) condensed formulas, (2) Lewis structures, and (3) identify the compound as either an alkane, alkene, alkyne,...
-
An auto-parts manufacturer is considering establishing an engineering computing center. This center will be equipped with three engineering workstations each of which would cost $25,000 and have a...
-
The Green Thumb Gardener is a retail store that sells plants, soil, and decorative pots. On December 31, 2016, the firms general ledger contained the accounts and balances that appear below. ACCOUNTS...
-
Fun Depot is a retail store that sells toys, games, and bicycles. On December 31, 2016, the firms general ledger contained the following accounts and balances. ACCOUNTS AND BALANCES INSTRUCTIONS 1....
-
Healthy Eating Foods Company is a distributor of nutritious snack foods such as granola bars. On December 31, 2016, the firms general ledger contained the accounts and balances that follow. ACCOUNTS...
-
Form small groups for this exercise on claim and adjustment letters. Have each member of your group study the following two letters. Meet and discuss your reactions to the two letters. How...
-
You work in the customer relations department of a company that makes plumbing supplies. The head of product development has just handed you the draft of installation instructions for a sliding tub...
-
Study the excerpt from the Micron data flyer (2010, p. 9). Describe the designers use of alignment as a design principle. How effective is it? How would you modify it? Present your analysis and...
Study smarter with the SolutionInn App