
Data Structure

This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.
 Illustration of FIFO behavior
Task

Implement a FIFO queue.

Elements are added at one side and popped from the other in the order of insertion.



Operations:

   push   (aka enqueue)    - add element
   pop     (aka dequeue)    - pop first element
   empty                             - return truth value when empty


Errors:

   handle the error of trying to pop from an empty queue (behavior depends on the language and platform)


See

   Queue/Usage   for the built-in FIFO or queue of your language or standard library.


See also

 Array
 Associative array: Creation, Iteration
 Collections
 Compound data type
 Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
 Linked list
 Queue: Definition, Usage
 Set
 Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
 Stack


namespace rosettacode
{
  template<typename T> class queue
  {
  public:
    queue();
    ~queue();
    void push(T const& t);
    T pop();
    bool empty();
  private:
    void drop();
    struct node;
    node* head;
    node* tail;
  };
 
  template<typename T> struct queue<T>::node
  {
    T data;
    node* next;
    node(T const& t): data(t), next(0) {}
  };
 
  template<typename T>
   queue<T>::queue():
    head(0)
  {
  }
 
  template<typename T>
   inline void queue<T>::drop()
  {
    node* n = head;
    head = head->next;
    delete n;
  }
 
  template<typename T>
   queue<T>::~queue()
  {
    while (!empty())
      drop();
  }
 
  template<typename T>
   void queue<T>::push(T const& t)
  {
    node*& next = head? tail->next : head;
    next = new node(t);
    tail = next;
  }
 
  template<typename T>
   T queue<T>::pop()
  {
    T tmp = head->data;
    drop();
    return tmp;
  }
 
  template<typename T>
   bool queue<T>::empty()
  {
    return head == 0;
  }
}