Most of the data structures described in this chapter are folklore. They
can be found in implementations dating back over 30 years. For example,
implementations of stacks, queues, and deques, which generalize easily
to the
,
and
structures described
here, are discussed by Knuth [46, Section 2.2.2].

Brodnik et al. [13] seem to have been the first to describe
the
and prove a lower-bound like that
in Section 2.6.2. They also present a different structure
that uses a more sophisticated choice of block sizes in order to avoid
computing square roots in the
method. Within their scheme,
the block containing
is block
, which
is simply the index of the leading 1 bit in the binary representation
of
. Some computer architectures provide an instruction for
computing the index of the leading 1-bit in an integer.

A structure related to the
is the two-level
tiered-vector of Goodrich and Kloss [35].
This structure
supports the
and
operations in constant time and
and
in
time. These running times
are similar to what can be achieved with the more careful implementation
of a
discussed in Exercise 2.10.

**Exercise 2..1**
The

method

inserts all elements of the

into the list at position

. (The

method is a special
case where

.) Explain why, for the data structures
in this chapter, it is not efficient to implement

by
repeated calls to

. Design and implement a more efficient
implementation.

**Exercise 2..2**
Design and implement a

.

This is an implementation
of the

interface in which the

operation removes
an element that is chosen uniformly at random among all the elements
currently in the queue. (Think of a

as a bag in which
we can add elements or reach in and blindly remove some random element.)
The

and

operations in a

should run
in constant time per operation.

**Exercise 2..3**
Design and implement a

(triple-ended queue).

This is a

implementation in which

and

run in constant time
and

and

run in time

In other words, modifications are fast if they are near either
end or near the middle of the list.

**Exercise 2..4**
Implement a method

that ``rotates'' the array

so that

moves to

, for all

.

**Exercise 2..5**
Implement a method

that ``rotates'' a

so that
list item

becomes list item

. When run on
an

, or a

,

should run in

time.

**Exercise 2..6**
Modify the

implementation so that the shifting
done by

,

, and

is done using
the faster

method.

**Exercise 2..7**
Modify the

implementation so that it does not use the

operator (which is expensive on some systems). Instead, it
should make use of the fact that, if

is a power of 2,
then

(Here,

is the bitwise-and operator.)

**Exercise 2..9**
Design and implement a version of a

that has
only

wasted space, but that can perform

and

operations in

time.

**Exercise 2..10**
Design and implement a version of a

that has
only

wasted space, but that can perform

and

operations in

time. (For an idea on how to do this, see Section

3.3.)

**Exercise 2..11**
Design and implement a version of a

that has
only

wasted space, but that can perform

and

operations in

time.
(See Section

3.3 for ideas on how to achieve this.)

**Exercise 2..12**
Design and implement a

.

This three level structure
implements the

interface using

wasted space.
In this structure,

and

take constant time; while

and

take

amortized time.

opendatastructures.org