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.