Bounded Queues (b_queue)

Definition

An instance Q of the parameterized data type b_queue<E> is a queue (see section Queues) of bounded size.

Creation

b_queue<E>	Q(int n);	creates an instance Q of type b_queue<E> that can hold up to n elements. Q is initialized with the empty queue.

Operations

E	Q.top()	returns the front element of Q. Precondition: Q is not empty.
E	Q.pop()	deletes and returns the front element of Q. Precondition: Q is not empty.
void	Q.append(E x)	appends x to the rear end of Q. Precondition: Q.size() < n.
void	Q.clear()	makes Q the empty queue.
int	Q.size()	returns the size of Q.
bool	Q.empty()	returns true if Q is empty, false otherwise.

Implementation

Bounded queues are implemented by circular arrays. All operations take time O(1). The space requirement is O(n).