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/core/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

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

Iteration

forall(x, Q) { ``the elements of Q are successively assigned to x'' }

Implementation

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