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() 
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
Christian Uhrig
20170407