With the linked implementation of a queue, what are the ramifications of; applic

Question

With the linked implementation of a queue, what are the ramifications of; application enqueuing the same object twice before dequeuing it? Asume that an integer requires 2 bytes of space and a reference requires 4 byte of space. Also assume the maximum queue size is 200. We define "overhead space as the space required by the structure that does not include the space usee by the elements the structure contains. How much overhead space is needed for: Our bounded array-based queue holding 20 elements? Our bounded array-based queue holding 100 elements? Our bounded array-based queue holding 200 elements? Our reference-based queue holding 20 elements? Our reference-based queue holding 100 elements? Our reference-based queue holding 200 elements? For what size queue do ihe array-based and reference-based approaches use approximately the same amount of overhead space?

Explanation / Answer

Answer 33.

Queue operations.

• enqueue() Insert a new item onto queue.

• dequeue() Delete and return the item least recently added.

• isEmpty() Is the queue empty

Enqueue: Linked List Implementation

First Last

X= new Node, x.item = item, x.next = null

First Last x= new Node

First Last   

Answer 34 :

A )

1 840

2. 1000

3. 1200

4. 80

5. 400

6. 800

B) Queue of 200 Elements

Note:

General formula for calculating memory usage

In general, the heap memory used by a Java object in Hotspot consists of:

Sizes of primitive types

In case you're not familiar with the byte size of the different Java primitive data types, here is the complete list:

You may have expected a boolean to take up a single bit, or an eighth of a byte, especially if an object had 8 boolean fields. In practice, Hotspot (and, I believe, VMs generally) allocate a whole byte to each boolean*.

* The reason is simply ease and efficiency of implementation: generally, we want to assign a "byte offset" to each field of a class and use a simple instruction to read/write an individual byte. It would be awkward if we had to cope with sub-byte offsets for certain fields, and it would require extra logic to read/write individual bits at a given position rather than just the whole byte each time the boolean was accessed.

Object size granularity

In Hotspot, every object occupies a number of bytes that is a multiple of 8. If the number of bytes required by an object for its header and fields is not a multiple 8, then you round up to the next multiple of 8.

This means, for example, that:

I am the Good

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.