     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 Q(int n) creates an instance Q of type b_queue 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