During our conversation about Stacks, Queues. and Deques, we talked about the circular array implementation of a queue. 1. Why didn't we need a circular array implementation of a stack? What quality, specifically, does a queue have that led to a need for the circular array implementation? (You need to be specific here, bu it shouldn't require more than a sentence of two to answer this.) 2. You've seen that the dynamically-allocated array underlying a std::vector is resized periodically. Propose an algorithm for resizing the array used in the circular array implementation of a queue when it comes time to enqueue an element and the array is full. How much larger is your new array? How do the contents of your queue look different than before? 3. Assuming your algorithm was used to solve the problem of resizing the array when it's full, what is the amortized running time of the enqueue operation? (You may want to refer back to the Amortized Analysis lecture while vou consider this.)

During our conversation about Stacks, Queues. and Deques, we talked about the circular array implementation of a queue. 1. Why didn't we need a circular array implementation of a stack? What quality, specifically, does a queue have that led to a need for the circular array implementation? (You need to be specific here, bu it shouldn't require more than a sentence of two to answer this.) 2. You've seen that the dynamically-allocated array underlying a std::vector is resized periodically. Propose an algorithm for resizing the array used in the circular array implementation of a queue when it comes time to enqueue an element and the array is full. How much larger is your new array? How do the contents of your queue look different than before? 3. Assuming your algorithm was used to solve the problem of resizing the array when it's full, what is the amortized running time of the enqueue operation? (You may want to refer back to the Amortized Analysis lecture while vou consider this.)

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Similar questions

11, 12, 13
Discuss the differences between the array implementation and the linked list implementation of queues. Describe the advantages and disadvantages of each implementation.
10, 11, 12
Question 3 a. "Queues and stacks are used in many real-life situations". In your own words, clearly distinguish between queues and stacks; and give one example of real-life situations in which each of them is used. b. In an array-based implementation of a stack, which end of the contents of the array represent the bottom of the stack and why? c. If the size of circular queue K is 4 with indices number from 0 to 3 what would be the state of the queue after the following set of 8 operations below. Show in a diagram the state of queue K after each of the 8 operations. K. enqueue (“F"), K. enqueue (“R"), K. dequeue(), K. enqueue (“P"), dequeue(), K.front(), K. enqueue (“Z"), K. enqueue (“G") d. Why are insertions and deletions at the logical end of the array more efficient than insertions and deletions in the interior of the array?
We discussed several Linked List Variations, each of which was more complex than the one preceding it, but that was able to do certain things asymptotically faster than the simpler variants could. This is one of many examples we'll see this quarter where we make a classic tradeoff in computing: using more memory (and, correspondingly, more complexity for managing what it's in it) in an effort to spend less time. While it's not always true that we can make things faster by using more memory, it's not at all uncommon to see these two things be on opposite sides of a tradeoff. One of the linked list variants we saw was a singly-linked list with head and tail pointers. Let's consider where this variant fell short and whether there are other ways to improve it besides what we saw. 1. Why isn't the presence of a tail pointer enough to allow us to remove the last node in the list in O(1) time? 2. Suppose that we added a third list-level pointer (i.e., outside of the nodes) called before Tail,…
Let's say your current programming project is using a circular queue implementation which uses a simple modulus operation for moving the head and tail forward: p = (p+1)%n. But the queue isn't a purely traditional one and you sometimes have to move backwards during a search. When this search wraps from the front to the rear, you must use this code: p = (p==0?n-1:p-1). One day programmer Sam comes up with this little gem: p=(p+d)%n. Here d is filled in with 1 when moving forward and n-1 when moving backwards. Can Sam's simple solution be correct? Prove or disprove Sam here.
1. consider an array based queue implementation. suppose we wish to use an extra bit in the queue records to indicate whether a queue is empty. a. Modify the declarationsand operations for a circular queue to accomodate this feature. b. Would you see the change to be worthwide.
The circular array queue implementation increased the dequeue operation's performance from O(n) to O(1) by doing away with the requirement to move array items. Adding or removing members from a list can occur anywhere along its length, not simply at the front or back, thus this is not true.
In a programming language (Pascal), the declaration of a node in a singly linked list is shown in Figure P6.7(a). The list referred to for the problem is shown in Figure P6.7(b). Given P to be a pointer to a node, the instructions DATA(P) and LINK(P) referring to the DATA and LINK fields, respectively, of node P are equivalently represented by P↑. DATA and P↑. LINK in the programming language. What do the following commands do to the logical representation of the list T? i) ii) TYPE POINTER=NODE; NODE RECORD DATA: integer; LINK: POINTER END; VAR P, Q R: T POINTER (a) Declaration of a node in a singly linked list T 31 TE 57 12 (b) A singly linked list T iii) R₁.LINK: = Q iv) R₁.DATA: = P₁.DATA: Q₁.DATA + R₁.DATA Q: = P |R Figure P6.7. (a and b) Declaration of a node in a programming language and the logical representation of a singly linked list T Q.LINK.DATA + 10 91 Linked Lists 189
Your crazy boss has assigned you to write a linear array-based implementation of the IQueue interface for use in all the company's software. You've tried explaining why that's a bad idea with logic and math, but to no avail. So - suppress your inner turmoil and complete the add() and remove() methods of the AQueue class and identify the runtime order of each of your methods. /** A minimal queue interface */ public interface IQueue { /** Add element to the end of the queue */ public void add(E element); /** Remove and return element from the front of the queue * @returns fırst element * @throws NoSuchElementException if queue is empty */ public E remove(); /** Not an ideal Queue */ public class AQueue implements IQueue{ private El) array: private int rear; public AQueue(){ array = (E[)(new Object[10]): rear = 0: private void expandCapacity) { if (rear == array.length) { array = Arrays.copyOf(array, array.length 2): @Override public void add(E element) { / TODO @Override public E…