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

     
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/queue.h >

Creation

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

Operations

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(E x) appends x to the rear end of Q.
int  Q.size() returns the size of Q.
bool Q.empty() returns true if Q is empty, false otherwise.
void  Q.clear() makes Q the empty queue.

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 )
LEDA research project
1999-04-23