Queues ( queue )

Definition

An instance Q of the parameterized data type queue<E> is a sequence of elements of data type E, called the element type of Q. Elements are inserted at one end (the rear) and deleted at the other end (the front) of Q. The size of Q is the length of the sequence; a queue of size zero is called the empty queue.

#include < LEDA/core/queue.h >

Types

queue<E>::value_type

the value type.

Creation

queue<E>

Q

creates an instance Q of type queue<E>. Q is initialized with the empty queue.

Operations

const E&	Q.top()	returns the front element of Q. Precondition Q is not empty.
E	Q.pop()	deletes and returns the front element of Q. Precondition Q is not empty.
void	Q.append(const E& x)	appends x to the rear end of Q.
void	Q.push(const E& x)	inserts x at the front end of Q.
int	Q.size()	returns the size of Q.
int	Q.length()	returns the size of Q.
bool	Q.empty()	returns true if Q is empty, false otherwise.
void	Q.clear()	makes Q the empty queue.

Iteration

forall(x, Q) { ``the elements of Q are successively assigned to x'' }

Implementation

Queues are implemented by singly linked linear lists. All operations take time O(1), except clear which takes time O(n), where n is the size of the queue.