Next: Linear Lists ( list
Up: Basic Data Types
Previous: Bounded Stacks ( b_stack
Contents
Index
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(const E& x) 
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.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).
Next: Linear Lists ( list
Up: Basic Data Types
Previous: Bounded Stacks ( b_stack
Contents
Index
root
20080109