Bounded Queues ( b_queue )

Definition

An instance Q of the parameterized data type b_queue<E> is a (double ended) 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.front()	returns the first element of Q. Precondition Q is not empty.
const E&	Q.back()	returns the last element of Q. Precondition Q is not empty.
const E&	Q.pop_front()	deletes and returns the first element of Q. Precondition Q is not empty.
const E&	Q.pop_back()	deletes and returns the last element of Q. Precondition Q is not empty.
void	Q.push_front(const E& x)	inserts x at the beginning of Q. Precondition Q.size()< n.
void	Q.push_back(const E& x)	inserts x at the end of Q. Precondition Q.size()< n.
void	Q.append(const E& x)	same as Q.push_back().
void	Q.clear()	makes Q the empty queue.
int	Q.max_size()	returns the maximal size of Q (given in constructor).
int	Q.size()	returns the size of Q.
int	Q.length()	same as Q.size().
bool	Q.empty()	returns true if Q is empty, false otherwise.

Stack Operations

const E&	Q.top()	same as Q.front().
const E&	Q.pop()	same as Q.pop_front().
void	Q.push(const E& x)	same as Q.push_front().

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