TAOCP 2.2.2 Exercise 16

Section 2.2.2: Sequential Allocation

Exercise 16. [20] The text illustrates how two stacks can be located so they grow towards each other, thereby making efficient use of a common memory area. Can two queues, or a stack and a queue, make use of a common memory area with the same efficiency?

Verified: no
Solve time: 46s

Solution

No.

Two stacks can share a common memory area with complete efficiency because each stack has only one active end. If the stacks grow toward each other, every unused location lies between the two tops. Hence overflow occurs if and only if the total number of occupied locations equals the total available space.

A queue differs from a stack because insertions and deletions occur at opposite ends. In the circular representation of (6a) and (7a), a queue occupying $k$ locations may require an arbitrary interval of $k$ consecutive locations in memory, and the position of this interval changes as insertions and deletions take place.

Consider first two queues. Let the common memory area contain $M$ locations. Suppose queue 1 contains $a$ items and queue 2 contains $b$ items, with $a+b<M$. Condition (a) in the text requires that overflow must not occur, since free space still exists.

Assume that each queue occupies one contiguous block whose endpoints are fixed in advance, analogous to the two-stack arrangement. Let queue 1 grow from the left and queue 2 from the right. After a long sequence of insertions and deletions, queue 1 may have its front near the right end of its allotted region while queue 2 may have its front near the left end of its region. Large portions of memory behind the fronts of the queues become unavailable unless the contents are moved. Consequently, a configuration can arise in which both queues are unable to accept another insertion even though the total number of occupied locations is less than $M$.

For example, let the memory consist of locations $1,\ldots,M$. Suppose queue 1 occupies locations near the middle and queue 2 also occupies locations near the middle, while empty locations exist only at the extreme left and right ends. Neither queue can extend into those empty locations without relocating elements. Thus overflow would occur before the total capacity is exhausted. Condition (a) fails.

The difficulty is fundamental. A queue requires free space adjacent to its rear, but deletions create free space adjacent to its front. Therefore the free space generated by one queue is generally not located where that queue can reuse it. To guarantee that every free location can eventually be used by either queue, the queues must be allowed to move in memory, exactly as sequential allocation methods permit for several variable-size lists. Fixed boundary positions are insufficient.

The same argument applies to a stack and a queue. The stack can use any free location adjacent to its top, but the queue requires free space adjacent to its rear while deletions release space at its front. A configuration may occur in which free locations exist, and the total occupancy is below capacity, yet the queue cannot accept another item without relocating data. Hence overflow can occur before all memory is occupied.

Therefore neither two queues nor a stack and a queue can share a common memory area with the same efficiency as two stacks, if the structures are required to remain in fixed positions. Achieving the same efficiency requires relocation or repacking of stored elements, which abandons the fixed-base arrangement.

$$ \boxed{\text{Two queues: no; stack and queue: no.}} $$