next up previous contents index
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 up previous contents index
Next: Linear Lists ( list Up: Basic Data Types Previous: Bounded Stacks ( b_stack   Contents   Index
root 2008-01-09