next up previous contents index
Next: Bounded Stacks ( b_stack Up: Basic Data Types Previous: Stacks ( stack )   Contents   Index


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.


next up previous contents index
Next: Bounded Stacks ( b_stack Up: Basic Data Types Previous: Stacks ( stack )   Contents   Index
Christian Uhrig 2017-04-07