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.

#include < LEDA/b_queue.h >

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).